communication efficient private lookup I have a scenario where a client has a private set and the server has a large public set, we would like an estimate of the intersection size or more specifically the percent of the private set covered by the public set.

However we do not want to send anywhere near the entire public set over the wire, even a bloom filter would seem rather large.

It's OK for the server to discover the size of intersection but should not gain much about specific keys the client has.

Is this possible?
With priorities being minimizing communication, client compute, server compute in that order.

Here are some recent papers that study optimizing PSI for the case of significantly unequal set sizes. In all of these papers the primary goal is to reduce communication.

These two papers save on communication by having an offline phase with high communication. When it comes time to actually compute the intersection, the online communication is low:

Unbalanced Approximate Private Set Intersection; Amanda Cristina Davi Resende, Diego F. Aranha
Private Set Intersection for Unequal Set Sizes with Mobile Applications; Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas

This paper saves on communication by assuming that the server's large set is held by two (or more) noncolluding parties. That way, it is possible to leverage techniques of private information retrieval:

PIR-PSI: Scaling Private Contact Discovery; Daniel Demmler, Peter Rindal, Mike Rosulek, Ni Trieu

You could argue that the previous papers are "cheating" in the sense that they are not in the standard 2-party setting with a one-off computation.

There are a few papers that achieve low communication without such "cheating", and these all use expensive public-key crypto operations (proportional to the size of the large set). The most efficient one that I know of is this, which uses somewhat homomorphic encryption:

Fast Private Set Intersection from Homomorphic Encryption; Hao Chen, Kim Laine, Peter Rindal

I happen to know a followup to this work will appear at CCS 2018, but it is not available online yet.

You cannot avoid having the protocol "touch" every part of the large set, so the server cost will always be somewhat high. In PIR-PSI the cost is some number of very cheap AES operations for each item in the large set. Hence this one is the fastest that I know about (if you include the cost of the offline pre-computation in other work). The FHE-based scheme is surprisingly fast though a little slower than PIR-PSI as far as I know.

The state of the art for all of these supports 10-100 million server items and 500-5000 client items, with costs on the order of a few seconds and maybe 5-20 MB of communication.


Differential or Truncated Differential Attack On Small Cipher The cipher given below is a  16-bit toy cipher which uses 8-bit sbox and 2x2 byte Matrix. The Key $k_0$ and $k_1$ are $\oplus$ with the data. The multiplication with matrix is performed in $GF(2^8)$ with irreducible polynomial of $x^8+x^4+x^3+x+1$

The differential probability (DP) of the sbox for input difference of $0x01$ and output difference of $0x01$ is $40/256$.

For simplicity, it is assumed that $k_0$ and $k_1$ both are same, so guessing $k_1$ is enough.

A Brute force attack will take an effort of $2^{16}$ keys to be tested. How differential attack can be mounted with effort less than brute force.

I tried to mount attack differential attack with input pairs which has a difference of {$0x01$,$0x00$} but this required doing an effort of $2^{16}$. I did following

Get ciphertext of 256 chosen plaintext pairs which has difference of
{$0x01$,$0x00$}.
For all values of $k_1$ , Xor $k_1$  with Ciphertext pair, run it through invMatrix, pass it to inv of sbox and then Compare the difference
If difference if equal to  {$0x01$,$0x00$}, increment the count for this value of K1
The Key with highest increment is valid value of $k_1$

The content of Sbox is

6A, 3F, BF, 3D, BA, 2F, 91, B3, 1A, 52, F4, DE, 9B, D4, 7D, 7A,
72, 5A, 11, 36, A7, F5, E0, A0, E4, AC, 08, 1B, 50, F3, DC, 9A,
D7, 8B, AB, 09, 1D, 54, FE, FC, F8, EB, C9, 68, 44, CE, 78, 73,
62, 31, 98, D3, 87, A1, EC, C8, 67, 47, E2, AE, 16, 46, DD, A3,
FB, F6, E7, BE, 51, 0A, 20, 5E, 29, 81, 8E, BB, 42, D2, 8C, B7,
39, B9, 40, CD, 7B, 83, 9C, ED, CA, 6F, 66, 4E, 07, 1E, 5C, 27,
80, 90, C0, 49, EF, D1, 85, A4, 02, 0B, 1C, 57, 15, 43, D9, 95,
CF, 7C, 89, AF, 1F, 58, 18, 4D, FF, 00, 01, 03, 04, 05, 06, 0C,
0D, 0E, 0F, 10, 12, 13, 14, 17, 19, 21, 22, 23, 24, 25, 26, 28,
2A, 2B, 2C, 2D, 2E, 30, 32, 33, 34, 35, 37, 38, 3A, 3B, 3C, 3E,
41, 45, 48, 4A, 4B, 4C, 4F, 53, 55, 56, 59, 5B, 5D, 5F, 60, 61,
63, 64, 65, 69, 6B, 6C, 6D, 6E, 70, 71, 74, 75, 76, 77, 79, 7E,
7F, 82, 84, 86, 88, 8A, 8D, 8F, 92, 93, 94, 96, 97, 99, 9D, 9E,
9F, A2, A5, A6, A8, A9, AA, AD, B0, B1, B2, B4, B5, B6, B8, BC,
BD, C1, C2, C3, C4, C5, C6, C7, CB, CC, D0, D5, D6, D8, DA, DB,
DF, E1, E3, E5, E6, E8, E9, EA, EE, F0, F1, F2, F7, F9, FA, FD

How differential attack can be mounted with effort less than brute force.

Was the homework specifically to use a differential attack against this cipher?

Well, part of the problem you're having is that the cipher is, in some sense, too simple to use differential cryptanalysis against; the standard approach of "use DC to find a distinguisher in $N-1$ rounds, and then use that distinguisher to recover the subkey for the last round" doesn't apply.

The other issue is that you're still learning how to use differential cryptanalysis, and it certainly doesn't help that the standard approaches to use DC against this cipher doesn't work.

If you have to use DC, the first thing to do is look for high-probability differentials through the sbox; that is, values $\delta_i, \delta_o$ such that $sbox(x) \oplus sbox(x \oplus \delta_i) = \delta_o$ happen for lots of different values $x$; eyeballing the sbox, it would appear you can find such values which this happens far more often than a well-chosen sbox.

On the other hand, if you don't have to use DC, well, there's an easier approach to attack this cipher.  To start, we note that MDS matrices are bit-wise linear, and bit-wise linear functions have this property:

$$MDS(x \oplus y) = MDS(x) \oplus MDS(y)$$

for all values $x, y$.

Hint: how can you use this relation against the cipher?  How will this drastically reduce the work involved with attacking it?


Reveal a plaintext with 3 encryptions of Textbook RSA Assume we using Textbook RSA encryption with the public key $(N,3)$.
How can I learn message $m$ if I have the encryptions of $m,m+1,m+2$ in an efficient way?
I'm studying for a test and it's a question from one of the tests of the past


Security of XORing hashes vs concatenating On this question https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes a couple of the answers say that xoring is a bad/insecure choice for combining hashes. However, most of them say that in regards to xoring two identical hashes.

If I want to combine a Keccak-256, Skein-256-256, Blake2b-256, and Groestl-256 hash, would it be more secure to concatenate parts of the hash, or to xor the hashes together?

The answer is (as always): It depends. If you want pseudorandomness, then XOR is a good combiner (actually even optimal). However, if you want collision resistance then XOR is a really bad combiner because afaik you cannot show that collision resistance of the two hash functions implies collision resistance of the combiner. If you think about it, a collision for that combiner does not imply a collision for either of the hash functions. The same argument applies to second-preimage resistance. On the contrary, for the concatenation combiner a collision of the combiner contains a collision for both hash functions.

For one-wayness the situation is a bit more complicated. However, you cannot use a preimage finder for the combiner to find preimages for one of the hash functions...


Asymmetric key derivation – Who derives the new pub key can't know the new private key? I'm looking for a peer reviewed protocol or algorithm that can do this, preferentially I need something based on elliptic-curves cryptography.

Alice know the main public key of Bob (B-PUB-1).
Alice want to derive a new public key (B-PUB-2) from Bob's public key (B-PUB-1) in an asymmetric way.
The new key correspond to a private key (B-PRIV-2) that only Bob can generate by deriving it from his original private key (B-PRIV-1). This is done with only one communication from Alice to Bob without reply.
The only important use of (B-PUB-1, B-PRIV-1) is to generate several different instances of key pairs (B-PUB-2, B-PRIV-2), to communicate Alice and Bob can use also other keys.

In this way Bob own a new private key corresponding to the public key created by Alice.
Bob now could produce some signature of a message m with B-PRIV-2 verifiable with B-PUB-2.
A fundamental request is that B-PUB-2 and the signatures produced with B-PRIV-2 couldn't be related to B-PUB-1 by no one but Alice.

The purpose is not to allow Alice to be the only one able to verify the signature of the message.
At the contrary Alice will publish B-PUB-2 so everyone will be able to verify that m has a signature corresponding to B-PUB-2 but no one will be able relate this signature to B-PUB-1 and Bob.

The idea under this is that Bob trust that Alice has no interest in reveal his identity ( the fact that B-PUB-2 was derived from B-PUB-1) but Bob can't trust Alice  completely.
She could try to use the generated keys to create fake signatures. So Bob can't simply ask Alice to generate a keypair, publish the B-PUB-2 and send to him the B-PRIV-2.

A sketch of the way I think algorithm could work:

Alice choose some Random Secret
Alice do something with that secret and Bob's public key (B-PUB-1) to
create another key (B-PUB-2)
Alice send the Random Secret to Bob with an encrypted channel, this can be done with normal public key encryption. To send the key Alice can use B-PUB-1 or a completely different Bob's public key if the use of B-PUB-1 for encryption cause security flaw.
Bob obtain the Random Secret and do something with B-PRIV-1 to obtain
B-PRIV-2
Alice publish B-PUB-2
Bob create a message m and sign it with B-PRIV-2
Bob publish the message in anonymous way
Everyone can control the signature with B-PUB-2

I am afraid this answer is long overdue, but what you are asking for is actually possible. It is even easy if you use public key cryptography relying on the discrete logarithm problem to secure the private key, such as ECDSA (for signature) & ECIES (for encryption) for example. And it might probably be possible for other schemes as well, but not as easily (at least, not in a way that seems as straightforward as for the discrete logarithm).

You can go around your problem using something like the derivation of the "shared encryption key" in ECIES.

In both ECIES and ECDSA, the private key $k$ is a large integer, while the public key $P_{k}$ is a point on the elliptic curve $\mathrm{E}$ derived from $k$ by computing $P_k=k\cdot G$, for $G$ a generator of the curve with large prime order $n$ (which is generally standardized along with the curve you're using).

This means that you can actually derive another public key $k\cdot G$ just like what you are asking for by:

Alice picks a random secret integer $r$
She computes the point $R=r\cdot G$ on the curve $\mathrm{E}$
She can then compute the derived public key $P_{kr}$ by adding the public key point $P_k$ and the point $R$ together: $P_{kr}=P_k+R$

And now, the corresponding private key $k'$ is simply $k'=k+r$, because of the definition of the scalar multiplication, which make it distributive over the group law $+$, which means that $P_k+R = k\cdot G + r\cdot G = (k+r)\cdot G$.

So Alice can simply send $r$ to Bob, and Alice would still not be able to sign anything (in the ECDSA case) for this child public key $P_{kr}$.

Knowledge of $r$ merely allows to discover the "main" public key $P_k$. (So you might want to keep it secret, depending on your needs.)

If you want to adapt the scheme to something else than elliptic curves, you might, but you'll have to rely on the discrete logarithm problem to use the same trick. For instance, this specific method wouldn't work with RSA keys.

PS: I am also aware of a more intricate scheme used in certain Bitcoin wallets, but I haven't had time to study it yet and the scheme presented above is way simpler. But just in case, you might also want to check what's done in BIP32.


How to crack unknown 8-bit encryption algorithm? Can anyone tell me how to crack the encryption of 8 bit algorithm, when you have some clue that CBC mode is used, but the algorithm is secret. You also have some encrypted data (chosen plain text), which belong from 0 to 256.

How can you crack the encryption in that case?

Assuming that there are no collisions and there exists a 1 to 1 bijection between input and output, you could construct and store a table of assignments on a single round of encryption for all 256 possible bytes regardless of the key size. From there you can extend this to subsequent rounds by simply XORing the result of the previous round to the next 8 bit block, and plugging this result into your table.


Why haven't we proven many things computationally secure yet? Brute Force is infeasible for just about every algorithm we use today. Yet, attacks are feasible. This is because weaknesses keep coming up in our algorithms. Why?

We have proven lower bounds for things like sorts, the information security of things like OTP and Shamir's Secret Sharing, proven many problems as hard as any that can be checked in polynomial time (NP-complete), yet we haven't proven anything computationally secure.

Like, we can say that "if this assumption holds, this is secure" but the assumptions are obvious or definitional, like you would expect from axioms, but conjectures that are introduced just so they can be used to prove stuff, and are not in anyway self-evident. Are trust for them goes as far as "a bunch of people have tried to break it, but haven't." As far as I know, we don't even have many cryptographic algorithms for which breaking is NP-Complete.

Why is computational security so hard to prove? Why don't we have any, say, public-private key system that is NP complete to break?

I think @CortAmmon hit the nail on the head: cryptographic structures (hashes, ciphers, etc) are specifically designed to be hard for bad guys to analyse / reverse / find patterns in. It should come as no surprise that this is a double-edged sword: they are also hard for good guys to analyse in the form of mathematical proofs.

As @CortAmmon said: historically, conjectures in geometry and number theory often stood as open problems for hundreds of years before being either proven or disproven. The cannonical example of this is Fermat's Last Theorem which took 358 years, and the development of several new branches of mathematics, to solve.

Due to the nature of cryptography (hiding information inside structure with no discernible pattern), it contains some of the hardest conjectures in all of mathematics. It should not come as a surprise that in the mere 50 years that we have been studying modern cryptography (a spec in the history of mathematics), we still have open problems.

I'll give a few concrete examples:

As far as I know, it is an open problem whether hashes in the SHA family are surjective - ie does every possible string in the output space get mapped to? Why do we not know this? Because hash functions are intentionally hard to analyse.
Many cryptographic schemes do have formal proofs of security. For example, the 1979 paper by Merkle describing a hash-based signature scheme is full of proofs that the signature scheme is as strong as the underlying hash function. It turns out that despite understanding the security of Merkle-signatures very well, we didn't like the idea of huge, slow signatures, so opted for faster / smaller algorithms that are more mathematically complex and we don't understand as well.
As an example: Lattice-based cryptography is one of the leading candidates for quantum-resistant encryption. Steven Galbraith recently gave a talk at the PQCrypto2016 conference where he listed all the branches of mathematics that are involved in understanding lattice-based schemes. He estimated that there are about a dozen people on the planet who are experts in all of those areas of mathematics. How can you hope to find subtle and complex weaknesses when there are so few experts working on the problem?

Bottom line: Math is hard, cryptographic algorithms are specifically designed to be hard to analyse, and modern cryptography is still very young in the history of mathematics.


Can I derive an IV as a segment counter for AES256-GCM? I'm writing a software that will be encrypting & authenticating segments of data, each 4096 bytes long. These segments are saved to disk in a sequential order that will never change. So I was thinking to encrypt each one of them using AES256-GCM, but before I code it I need to confirm a couple of points:

To conserve space for saving an IV for AES-GCM encryption/decryption, I was thinking to use each of my segments' sequential number as an IV. Would that pose an issue (in cryptographic sense)?
I decided to go with a 16-byte TAG (that is used by AES-GCM for authentication.) Is that an overkill for an encrypted 4096 byte segment?

To conserve space for saving an IV for AES-GCM encryption/decryption, I was thinking to use each of my segments' sequential number as an IV. Would that pose an issue (in cryptographic sense)?

No, it will not pose an issue because the (twelve byte) IV for GCM encryption is really a nonce; it is not directly used as counter for the underlying CTR encryption.

  I decided to go with a 16-byte TAG (that is used by AES-GCM for authentication.) Is that an overkill for an encrypted 4096 byte segment?

The security of GCM is rather dependent on the size of the authentication tag. If you can spare the few bytes I would strongly recommend keeping it set to 128 bits. You have overhead anyway and 16 / 4096 (1 / 256 if I'm not mistaken) is less than half of a percent of overhead.

And it seems like you will be handling large amounts of data, which increases the attack surface to an attacker. Better safe than sorry.


Merkle tree H(RBIT(X) ⊕ Y) instead of H(X || Y) I was reading Can XOR be used in a Merkle Tree instead of concatenation? and had the idea of reversing bits for either X or Y before the XOR combiner, to indicate the order. So instead of H(X ⊕ Y) we could use H(RBIT(X) ⊕ Y) (or H(X ⊕ RBIT(Y))).

The cost of both RBIT and XOR instructions are negligible on most modern CPUs compared to an additional hashing round, performance would (almost) double...

Assuming also that X and Y are mutually independent (which is the case in many constructions where the leafs of the merkle tree are pseudo-randomly generated, or randomized), would this make a secure combiner? Why (not)?

The problems mentioned in Can XOR be used in a Merkle Tree instead of concatenation? are just special cases of a fundamental problem: the construction is not second-preimage resistant. In fact, it is even worse in the sense that you can find a preimage with any $X$ value you like (similarly any $Y$ value you like).

You can open a Merkle-tree node $H( X \oplus Y)$ to any other values $X'$ and $Y'$ as long as $X \oplus Y = X' \oplus Y'$. If you can do this, then you can open a Merkle-tree leaf to literally any value. Flipping/inverting some bits (and indeed, any linear operation) won't make this attack any harder.


Validate per round rather than cycle-walking in FPE I was thinking about FPE specifically for numbers, CC, phone, SS #, etc. and I thought of some small "optimization" that could be implemented. Can I validate the string length after each round in the Feistel network, and repeating a round with the same tweak if the data is invalid, and continue until a set # of tweaks/successful rounds have been done.

For decryption, it would be much the same, since any invalid round could simply take the tweak of the preceding successful round.

Is there any downside to this approach (ie. security flaws, does not actually optimize run time, etc.)?

I don't think this would break correctness, but it's possible you might actually slow your algorithm down on average. You'd need a more rigorous combinatorial analysis of the expected number of repeated rounds vs. the expected number of full cycle walks. That really depends on the specific algorithm; are you using FFX?

You'd also need to show that doing this doesn't alter the distribution of ciphertexts in a way that breaks SPRP security. It's possible that it doesn't, but proving it seems nontrivial to me.


Is there a digital equivalent to the Great Seal of the United States? Since antiquity (and, for ceremonial purposes, up to the present day), physical documents have had seals affixed. In principle, these seals enable anyone, if he knows what he's looking for, to judge the authenticity of a document without consulting the authority that issued it. (In practice, there are ways of producing convincing forgeries, but leave that to one side for a moment.)
Is it possible, by affixing a string of characters, or suchlike, to a PDF, to achieve the same thing digitally?
I can think of a way of doing something similar:

Come up with a private key and a hashing function.
Hash the private key together with the timestamp for when the document was issued.
Affix the above hash, together with the timestamp, to the document.
When someone wants to authenticate a document, check that hashing the private key together with the timestamp produces the same hash as on the document.

However, the major difference between the above method and a physical Great Seal (e.g., The Great Seal of the United States) is the need to consult someone who has the private key. This check would have to come from a central authority since making the private key public would allow free reign to any forger.
Is there a way, then, of doing something like the above, but without the need for a central authority? If no, is it logically impossible, or is it an open problem?

Is there a way, then, of doing something like the above, but without the need for a central authority?

Why, yes, we do have a way to solve that problem - we refer to it as a 'digital signature'

Here's how it works:

Select a signature algorithm, and come up with a public/private key pair for a signature algorithm
With the private key, generate a signature of the document (possibly with the time stamp and anything else you find relevant).  Affix the above hash, together with the timestamp, to the document.
When someone wants to authenticate a document, simply get the public key, and check that the signature validation algorithm, together with the document and the timestamp, states that the signature verifies.

The fundamental property of a signature algorithm is that, while it is easy to sign any document you want with the private key, you cannot sign any document (where "sign" means generate a signature that verifies with the signature validation algorithm and the public key).

Common signature algorithms in use today are RSA, ECDSA and EdDSA

Of course, one step I didn't go into is "how, in step 3, does someone get the public key" and "how do they know that the public key they get is actually the signer's, and not some attackers"?  These are valid questions, with good answers; but I think I'll leave the exploration of that for another question...


Homomorphic Encryption Homomorphic Encryption (HE) which supports any function on ciphertexts is known as Fully Homomorphic Encryption (FHE), while Partially Homomorphic Encryption (PHE) includes encryption schemes that have homomorphic properties, with respect to one operation (e.g., only addition or only multiplication, but not both).

Are symmetric homomorphic encryption schemes (like Domingo-Ferrer, Castelluccia, etc.) also considered to be PHE?

It will depend on the exact system.

The cryptosystem of Castelluccia is additively homomorphic and is thus a PHE cipher.

The cipher of Domingo-Ferrer was broken by Wagner and others. Thus, I wouldn't classify it as either.

The cipher of Xiao, et al. is fully homomorphic.

To determine if a symmetric scheme is a PHE or FHE, just look at what operations it supports. If it supports a single operation (say addition), then it is PHE. If it supports both operations (addition and multiplication), then it is FHE.

Update
A recent trend in the HE encryption literature has been something called Somewhat Homomorphic Encryption (SHE). These are ciphers which support both addition and multiplication but not unlimited numbers of operations. E.g., BGN is a SHE cipher as it supports unlimited additions and one multiplication. The current FHE ciphers are all built using SHE ciphers plus a bootstrapping operation (or generating the keys such that enough of each operation can be supported to compute the desired function, making bootstrapping unnecessary).


What are the advantages of TOTP over HOTP? HMAC-based One Time Password (HOTP) was published as an informational IETF RFC 4226 in December 2005. In May, 2011, Time-based One-time Password Algorithm (TOTP) officially became RFC 6238. What advantages does it introduce?

One of the advantages is purely on the human side of security. From RFC 6238's abstract:

  The
     HOTP algorithm specifies an event-based OTP algorithm, where the
     moving factor is an event counter.  The present work bases the moving
     factor on a time value.  A time-based variant of the OTP algorithm
     provides short-lived OTP values, which are desirable for enhanced
     security.

(Emphasis mine.)

The TOTP passwords are short-lived, they only apply for a given amount of human time. HOTP passwords are potentially longer lived, they apply for an unknown amount of human time.

The reference to "enhanced security" is referencing (at least) two areas: The value of a compromised key, and ability to attack one.

First, should a current HOTP password be compromised it will potentially be valid for a "long time". Ensuring frequent use of the HOTP in human time is not a part of the HOTP design, so it is unknown how long the current HOTP password will be valid for and we have to assume the worst case, namely, that it will be a "long" time. This allows the attacker to use a compromised password at their leisure. But should the current TOTP be compromised, it will not be useful for very long because in one TOTP time increment it will be invalidated. Of course, in theory the attacker could grab and use the password in negligible time, but it does prevent a practical human aspect. For example, someone who gets a look at your current Paypal key (which rotates every 30 seconds, IIRC) can't go home and try to use it later, they would have to lunge for a computer in the moment. Someone who compromises they key may not realize it until after the key has expired. Etc.

Second, if you are attacking a key, your work is potentially invalidated or set back every time increment of the TOTP because the target has moved. Perhaps an attacker has discovered an attack against an OTP scheme that allows them to predict the next password only if they have some number of the last 10 passwords, but it takes about 2 hours of computing time to do so. If the OTP changes every minute, their attack is pretty much useless. Brute-force attacks are inhibited as well, because the next password is chosen the same distribution each time; it is possible to brute-force exhaust the password space and not find the password. TOTP doesn't eliminate those sorts of attacks, but hopefully it limits which ones have the ability to be effective.


How can I store a combination of multiple pass phrases? Let's assume we have 2 phrases, one is the real password from a user, and the other is generated from the real password and almost impossible to guess. You would need both to authenticate a user. What would be the best theoretical way to store them, or how to encrypt them so that if attacker somehow gets encrypted pass phrase wouldn't be able to decrypt both phrases? I know with brute force, attacker can eventually break the encryption, but what would be best to do to not make it easier for attacker to break it?:)

If we encrypt (with symmetric algorithm) them separately and store them somewhere (doesn't really matter where), first phrase could be vulnerable to dictionary attack. We could combine them, for example p1f1p2f2… (phrase1=p1p2p3…, phrase2=f1f2f3…) and then encrypt them. That way the combined phrase shouldn't be vulnerable to dictionary attack, and attacker could only use brute force.

But I'm not sure how the way we combine them affects encryption algorithm. Is there any specific encryption algorithm that would be better than the other? Could there be vulnerabilities regarding how we combine them, because they could get discovered if we statistically analyse many examples of encrypted combined pass phrases (I'm guessing here)?

Or is there no way to know before actually analysing the algorithm, encryption algorithm and encrypted pass phrases?

If you are asking "how can the server verify that the password (or passwords in your case) that the user enters are valid", the standard answer to that is not to have the server encrypt the passwords at all.  Instead, what we have the server do is store one hash of the two passwords.  That way, if someone manages to break into the server and get the hashes, that doesn't tell him anything about what the passwords are.

One simple implementation would to be to take a standard hash function (SHA256, for example), and when registering the user, compute the hash of the user-selected password concatenated with the one generated from the real password; the server would store this hash in the database (or forget the actual passwords).  Then, when authenticating a user, the user would supply the passwords, the server would concatinate them, hash them, and compare that hash to what's in the database (and, of course, allow the user only if the hashes are exactly the same).

One advantage of this over encrypting the passwords is that hashing is a one-way operation; no one can reverse the hash (this is actually one of the security properties of a cryptographical hash, that give a hash, no one can find that hashes to that value).  In addition, if the user enters the wrong data, it well detect that as well (as that's another of the security properties, that no one can find two values that hash to the same).

Now, if your second password is as good as you expect, that it is "almost impossible to guess", well, that's actually good enough.  Even if someone broke into the server and recovered the hash, well, all they could do is make guesses for both passwords, hash them, and seeing if both guesses were correct; if one of the passwords is unguessable, well, they can't do that.

However, I rather suspect that the password might be a bit more guessable than that (after all, if it were truly unguessable, why bother with the user-chosen password at all?).  If that is likely to be the case, it might be wiser to do the same approach, but with a password derivation function (such as PBKDF2); it's pretty much like a hash, but it does these nice things:

It makes provision for a "salt" (which is an additional value that is hashed in); it won't make a brute force attack on a single hashed password any harder, but it does mean that the attacker cannot attack several hashed passwords at once (because each of them will have a different salt).  The server would choose a random salt when registering the user, and include it along side the hash.
It's slower to evaluate than SHA256 (and in this context, that's not a bad thing; it means that an attacker will take longer to go through his dictionary).
It also provides a "key" that's needed to do the hash evaluation; if the server stores the key separately, well, the hash doesn't do the attacker any good unless he gets the key as well.

Oh, and one thing; about your specific question about how to combine the two passwords; well, hash functions and password derivation functions don't really care; they'll work with just about anything.  The only thing you need to be careful is to make sure that you combine them in a way that doesn't lose information.  For example, you wouldn't want to exclusive-or them together, otherwise (as a trivial example, the two passwords "A" and "1" would hash the same as the two passwords "B" and "2").  One easy and safe way to combine them is simply concatenate the two (of if the two passwords are "Alpha" and "Omega", you'd actually hash "AlphaOmega".  (Note: if both passwords are variable length, you make also want to concatinate the length of one of them if you want to be pedantic; otherwise the two passwords "AB" and "C" would hash the same as the two passwords "A" and "BC").


How to attack a two time pad if the plain text is randomized? As an extension to this quesiton, or this one how would you go about attacking a re used pad if the plaintext was randomized before being encrypted?

  0 0 0 1...         Plaintext

  0 1 1 1            seed(truly random number)
  0 1 0 1            Key1
  0 0 1 0            seed + Key1 mod 2 (=Cipher1)

  0 1 1 0...         Plaintext + PRNG(seed) mod 2 (=CipherR)
  1 0 1 0...         Key2(repeating 2 bit key "1 0")
  1 1 0 0...         CipherR + Key2 mod 2 (=Cipher2)

  0 0 1 0 1 1 0 0... Cipher1 & Cipher2 → ciphertext

This is using a OTP cipher to transmit the seed of a PRNG, then using a Vernam cipher with a repeating key to transmit the plaintext XORed with the PRN. Increasing the message length a little, hopefully to avoid cribbing.

How do you decode the Vernam cipher after the plain text has been randomized?

If your PRNG is good and your seed unknown $C_R = pt \oplus PRNG(seed)$ is essentially already an encryption of the plaintext using a stream cipher constructed from a PRNG.

Specifically it is indistinguishable from random.

Therefore $K_2 \oplus C_R$ can be viewed as an encryption of $K_2$. This is not useful but it also doesn't help an attacker.

I would conclude that this scheme is just as secure as constructing a stream cipher from a PRNG.


Secure MAC and secure encryption schemes combined to form insecure Authenticated Encryption? I'm reading up on Authenticated Encryption and can't really wrap my head around how a generally secure MAC and a generally secure encryption scheme can be combined into an insecure AE scheme, such as in MAC-and-Encrypt.
I'd be fine with just having links to sources so that I may read up more about it on my own.

Consider MAC-and-encrypt with a cipher of AES-CTR using sequential nonces, and a MAC of HMAC-SHA256 on the plaintext of the message.

Obviously these are respectively a secure cipher and MAC, but send the same plaintext twice, and the adversary learns that it's the same plaintext.  (Authenticate the nonce too, and this particular problem goes away, though.)
For a 128-bit string $m$, define $E_{k_1}(m) = \operatorname{AES}_{k_1}(m)$, and $M_{k_2}(m) = \operatorname{AES}_{k_2}(m)$.

Obviously these are respectively a secure cipher and (as a PRP approximation to a PRF) a secure MAC, but if $k_1 = k_2$, rather than using independent keys for MAC and encrypt as you should (or keys apparently independent, derived from a master key by a PRF, e.g. HKDF), bad things will happen when you try to compose these.

The standard reference on the security of generic composition of ciphers and MACs is Bellare and Namprempre 2004.  There are various standard security notions for a putative authenticated cipher: indistinguishability (IND-) or nonmalleability (NM-), under chosen-plaintext attack (-CPA) or adaptive chosen-ciphertext attack (-CCA2); unforgeability of plaintexts (INT-PTXT) or of ciphertexts (INT-CTXT).

Bellare and Namprempre prove or provide counterexamples for all implications and nonimplications between these security properties.  They also prove or provide counterexamples for the security properties generically attained or not by MAC-then-encrypt (MtE), encrypt-and-MAC (E&M), and encrypt-then-MAC (EtM), composed out of a cipher indistinguishable under chosen-plaintext attack (IND-CPA) and a MAC unforgeable or strongly unforgeable under chosen-message attack (UF-CMA, SUF-CMA).*  The results hold for any deterministic or stochastic, stateless or stateful, cipher and MAC, as long as decryption and verification are deterministic and stateless.

If, like me, you find this menagerie of security notions dizzying, you may find it reassuring that they can be gathered into a single notion of authenticated encryption meaning IND-CCA2 and INT-CTXT (which collectively imply all the others, and are equivalent to another notion of IND-CCA3), which in turn can be extended to authenticated encryption with associated data.  But the Bellare and Namprempre paper is helpful for studying the relations between the notions, and counterexamples for generic compositions where intuition might lead us astray into a false sense of security not provided by the standard definitions.

Beware that the story may be a little more complex than simply choosing a ‘mode of operation’ for a block cipher and choosing a MAC, as everything is in the misbegotten nonsense paradigm that is choosing modes of operation for a block cipher, a confusing paradigm that should have been left in the dumpster of history out back.

Example.  If you pick CBC mode, then you need to decide what to do with messages that are not exactly multiples of 128 bits long.  You might choose AES-CBC-PKCS7.  But if you try to apply that in (say) MAC-then-encrypt, you effectively have MAC-then-format-then-encrypt, and the reverse procedure is decrypt-then-parse-then-verify.  A lot happens before the verify stage, so this exposes opportunities for padding oracle attacks, because the adversary may have more than just a decryption oracle as is posited in the adaptive chosen-ciphertext attack model.

Even if you had only a UF-CMA MAC and not an SUF-CMA MAC, you are better off remembering encrypt-then-MAC as your go-to composition than you are with MAC-then-encrypt.  Although perfectly safe use of EtM and MtE give the same security properites (IND-CPA and INT-PTXT), anything other than EtM exposes you to the cryptographic doom principle, because you are tempted to touch unauthenticated data, which is pure evil.

* Spoiler alert: Only EtM with IND-CPA cipher and SUF-CMA MAC generically provides all the security properties.  EtM and MtE with IND-CPA cipher and UF-CMA MAC generically provide IND-CPA and INT-PTXT.  With SUF-CMA instead of UF-CMA, MtE still doesn't provide IND-CCA2 or INT-CTXT because the cipher may be malleable.  E&M doesn't even generically provide IND-CPA.


collision resistance of a composed hash function Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$.

Is the new hash function $H'(x)$ still collision resistant? How hard is it to find a collision? Any advice would be greatly appreciated!

Counterexample [from poncho in comments]: let $H_0\colon \{0,1\}^* \to \{0,1\}^{256}$; then $H(x) := p \cdot H_0(x)$, where $H_0(x)$ is interpreted as an integer in little-endian, is obviously collision-resistant but $H'(x) := \sum H(\cdots) \bmod p$ is identically zero and therefore very much not collision-resistant no matter what goes in the ellipsis.


Security of a sha-256 based stream xor cipher? Provided that I have some data I want to cipher and a password to do it:

I generate a random IV
I define c = sha256(password)
I generate an infinite stream where x0 = sha256(IV xor c) and xi = sha256(xi-1 xor c). This produces blocks of 32 bytes and I yield them byte by byte
output = data xor stream

Would this be secure? In case it's not, how insecure is it?

Note: The NSA isn't going to crack it, I just need it to be secure for a user with average-high cryptographic knowledge.

I know it may look similar to Is it feasible to build a stream cipher from a cryptographic hash function? but it has some differences:

I use a random IV instead of starting with hash(data)
Im xoring c in each phase of the stream generator, so even knowing xi you can't guess xi+1

The stream cipher part is cryptographically fine given a uniform random key and a unique nonce per message, since SHA-256 shows no evidence of failing preimage resistance, but it's stupidly slow because SHA-256 is designed for the much more expensive collision resistance.  There's no reason to prefer it over, for example, XSalsa20.

The password-based key derivation function is problematic if you ever use passwords chosen by a process with entropy much below 128 bits, like most people do, because the cost to the adversary of testing a guess for the password is negligible.  You should use a modern password-based key derivation function like scrypt or argon2 to derive the key.

Overall, when you're composing things like this, you should be concerned more with what you're actually trying to protect here.  Don't mess with inventing your own stream cipher—that's a solved problem.  To do this you need to articulate what you're trying to do in your application with what resources, how the adversary can manipulate those resources, and what you want to make sure the adversary can't do in spite of that.  Then you can decide how to use crypto to prevent the adversary's shenanigans—and you'll almost certainly need some authentication in there beyond encryption.


random mask reversible after homomorphic encryption I would like to know if this process is feasible under homomorphic encryption, ideally under paillier or any other additive scheme

Apply a mask X to obfuscate a message A ie. Am = A (op) X where (op) can be +, x, ...
Homomorphically encrypt Am => E(Am)
Remove X from E(Am) in order to obtain E(A) without any decryption (without knowing the private key)

A can be a matrix, vector, ...etc.

It sounds like you're looking for a way to do blinded encryption (that is, encryption in such a way that the encryptor does not know what he is encrypting).
It is certainly possible with Paillier.  Here is one way:

The (op) will be multiplication modulo $n$ the Paillier modulus (which is in the public key).

To mask, we pick a random $r$ relatively prime to $n$, and compute $Am = A \cdot r \bmod n$.  We can see that, if we selected $r$ uniformly, then $Am$ is distributed independently of $A$ (except for values not relatively prime to $n$)

We ask the encryptor to take $Am$ to compute $E(Am)$

To unmask, we compute $rinv = r^{-1} \bmod n$, and then homomorphically compute $E(rinv \cdot Am)$; this Paillier, this is done by computing $E(Am)^{rinv} \bmod n = E(A)$.

One drawback to this is that it doesn't actually mask the value $A=0$; is that a concern?
If it is, you can still do it by asking the encryptor to perform two masked encrypted operations.
First, you generate two random values $r, s$, making sure that neither is $0$
Then, you have the encryptor encrypt the values $A-s$ and $r\cdot s$, producing $E(A-s)$ and $E(r \cdot s)$.  Then, you use the above procedure to recover $E(s)$ from $E(r \cdot s)$.  Then, you homomorphically add $E(s)$ to $E(A-s)$, producing $E(A)$
You could just generate $E(s)$ yourself with $s$ and the public key.  However, if you could perform encryption yourself, you could just generate $E(A)$ from $A$, and it would appear you wanted to avoid that...


Addition with Shamir secret sharing? When performing Shamir secret sharing I'm trying to find $z_i$, such that $z = x + y$. Where $n = 6$ and $t = 3$.

I believe this would be the correct solution (correct me if I'm wrong):

Each party computes $x_i + y_i = z_i$
Each party shares $z_i$ with the other 2 parties
Each party uses Lagrange basis polynomials to compute the secret (using the 2 obtained values).

My question is this: if the shares are in the form $(i, f(i))$  (for $1$ to $i$) my assumption is that the involved parties can use Lagrange basis polynomials because they will know the "$i$" of the other parties that sent them their computed $z_i$. Is that correct?

You really only need to do step 1. If each party has shares of x and y (say $x_i,y_i$) then $z_i=x_i+y_i$ is a valid sharing of $z=x+y$.

What you are doing is used to multiply shares. Multiply, share the shares, reconstruct. In that case everything you said is correct. The reason this is needed in multiplication of shares and not addition can be seen by looking at the polynomials that were used for sharing. In the case of additions, the coefficients add pairwise, thus the individual coefficients of the resulting polynomial which shares $z$ has independent coefficients and has the same degree. In the case of multiplication, the degree goes from $t$ to $2t$ and the coefficients are not not pairwise independent.


Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3? The traditional brute force collision attack is generate $2^{N/2}$ (unique) random strings, hash them and this results in ~50% chance for collision.
The attack talked in the question's title is generate hashes by the sequence $H_0 = F(S), H_n = F(S||H_{n-1})$, where $S$ is a string to make collision with, $F$ is the hash function, and the sequence stops at $2^{N/3}$.

The above attack needs less calls to the hash function because it relies on the fact that each sequential hashing reduces the number of possible hashes. When hashing $2^N$ random strings, there will be $(1-(1-\frac{1}{2^N})^{2^N})2^N$ possible hashes because of all the collisions.

The sequence that tells the fraction of the possible hashes for each hash in the sequence is $P_0 = 1, P_n = 1 - (1-\frac{1}{2^N})^{2^NP_{n-1}}$, which roughly approximates to $P_n = P_{n-1} - \frac{P_{n-1}^2}{2}$ as $\lim_{P_{n-1}\to 0}$, which can be approximated into a function $P(n) = \frac{2}{n + 2}$. (these reductions in precision make it easier for future calculations)

The chance for a collision to NOT happen for a hash in the sequence against all of it's following hashes is $C_n = (1 - \frac{1}{P_n2^N})^{M - n - 1}$ where $M$ is the sequence's length, because the fraction is so close to $1$, it can be approximated to $C_n = 1 - \frac{M - n}{P_n2^N} = 1 - \frac{Mn - n^2}{2^{N + 1}}$. Now to approximate the multiplication of all $C$s ($C_0C_1...C_M)$ to get the chance for collision for all hashes combined, we can discard the multiplication (because again, $C_n$ is very close to $1$) and add all the subtracted parts and subtract them from $1$, which results in $1 - \frac{M^3/2-M^3/4}{2^{N+1}} = 1 - \frac{M^3/4}{2^{N+1}}$, and to reach ~50% collision rate $M = 2^{(N+3)/3-1}$, which is just $2^{N/3}$.

Is there a reason why this won't work?

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, \dots, X_M$.  The probability of a repeated value $F(X_i) = F(X_j)$ for $i \ne j$ is at most $M^2\!\big/2^N$ by the birthday paradox.  For $M = 2^{N/3}$, this is $2^{2N/3}\!\big/2^N = 1\big/2^{N - 2N/3} = 1\big/2^{N/3}$.  If your calculation doesn't fit this bound, there's an error in your calculation.

‘But what if we come upon a short cycle in $H \mapsto F(S \mathbin\| H)$?’, you ask.  The expected number of points before a repeat in a uniform random function on a domain of $2^N$ elements is $\frac12\sqrt{2\pi\,2^N} - 1 \approx 2^{N/2}$ (Harris 1960 Eqs. 3.4 & 3.11, see paper for more details of distribution; paywall-free).  So no, this method doesn't improve the expected cost.

Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!


Efficiently show/prove knowledge of third party secret without leaking information Say Alice publishes (i.e. all parties in the universe) a key or certificate $x$ and sends a secret $s$ to Bob.
Bob then publishes some data $d$ (his identity or a message or smt.) and an authentication of the data using the secret, $auth = mac(d,s)$.
Dave can now verify the authenticity of $d$, $verify(auth,x)$, and must not be able to extract substantial information about $s$, even when Bob reuses $s$ for different messages.
Furthermore, Alice may produce many $(x_i,s_i)$ pairs and all parties have limited computing resources.
Finally, the identities of all parties are known and private sidechannels are possible (so $s$ can safely be transmitted to Bob).

This can be implemented using public-key cryptography with $x$ being the public key and $s$ the private key. However, the (public key) algorithms I know of rely on large prime generation (or other costly operations), which I presume is too costly when in practice Alice produces lots of unused key pairs.

Is there a cheap solution to the scenario above?

(the title may be a bit off — if only I knew what I was looking for)

Public-key cryptography is not sufficiently computationally burdensome to where other approaches must be used for authentication protocols. Note though that what you describe is not actually public-key based. The verification of the MAC requires Dave and Bob to both have a shared key. Also, note that a random component must be included in some manner in all authentication protocols, else an attacker will be able to mount a man-in-the-middle attack and/or reuse the authentication string in the future. However, similar schemes that are based purely on public-key algorithms do exist, and are more commonly used. Either way, Alice is acting as a $TA$, verifying Bob's identity through some secondary channel and publishing a mechanism by which Dave can confirm that the owner of Bob's private signature algorithm (presumably Bob) is in fact Bob.

In this case, the computationally burdensome process, generating public-private key pairs, occurs not every time authentication takes place, but only when Bob asks Alice for a certificate. Also note that generating public-private key pairs is not particularly expensive, provided access to either an efficient cryptographically secure random number generator or a large pool of entropy, both of which are relatively easy to have.

Beyond that, public-key algorithms are designed so that the encryption and decryption processes can be computed efficiently. For instance, RSA and other Discrete Logarithm based problems have square-and-multiply or some variant. As such, the actual signing and verification step for Bob and Dave is quite simple and efficient, and there are a number of schemes which require only the limited computing power of say, smart cards.


Is there a security problem with this prime generation algorithm? I am facing the following algorithm to generate an RSA public key:

e = 0x10001

def generate_p():
    r := random odd 128-bit number
    p := (3*r^4 + 1)/4
    if is_prime(p) and gcd(p-1, e) = 1:
        return p
    else:
        return generate_p()

def generate_q():
    r := random odd 128-bit number
    q := (11*r^4 + 1)/4
    if is_prime(q) and gcd(q-1, e) = 1:
        return q
    else:
        return generate_q()

p = generate_p()
q = generate_q()
N = p*q
d = modinv(e, (p-1)*(q-1))

So essentially $s$ and $t$ are random 128-bit integers, $4p = 3s^4 + 1$ and $4q = 11t^4 + 1$ with $p$ and $q$ prime. Does the way $p$ and $q$ are generated give us information that helps factor $N$ (which is 1024 bits in size)?

I considered Coppersmith's attack to compute $s$ and $t$ as small roots mod p/q, but they are not small enough for the algorithm to be applicable.

This is the approach that finally let us factor $N$ for the competition. I believe it completely breaks the given scheme. Let's write down the formula for $N$:

$N = pq = \frac{3s^4+1}{4}\cdot\frac{11t^4+1}{4}$ for some $s, t \in [2^{128}, 2^{129})$

After some rearranging:

$\frac{16}{33}N = (st)^4 + \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33}$

In our case, we had $\frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} < (st)^2$ and thus after we substitute $x := (st)^2$:

$x^2 \le \frac{16}{33}N < x^2 + x = x(x+1) < (x+1)^2$

So we could compute $x = \lfloor\sqrt{\frac{16}{33}N}\rfloor$ and then factor $\sqrt x$ (which has only 256 bits) to get $s$ and $t$.

I feel like the above inequality holds generally if $s$ and $t$ have somewhat similar value, but I haven't tried to prove this.


Is RSA secure enough to protect bitcoin private keys? Suppose my very trusting friend has a bitcoin private key with a large balance (let's say $1B USD worth of Bitcoin) and wishes to keep a backup copy with me as a trustee.
He doesn't want to transfer the raw key over an internet connection for obvious reasons, so he asks me to generate an RSA key and send him the public key so he can encrypt his bitcoin private key and then I can decrypt it on my end offline and store my backup of his bitcoin private key.
Is there a realistic risk that someone could brute force the encrypted key that we transferred plaintext over the internet?

2048 bit RSA is currently and for the foreseeable future secure.
512 bit is currently not considered useful.
1024 bit RSA though not currently known to be cracked doesn't have enough security margins for comfort. Definitely not for securing $1B USD. Several years ago the cost of a machine which could break 1024 bit RSA in a year was a few million. Cost presumably went down. And it is likely certain 3 letter organizations have such machines.
The best way to attack RSA is by factorizing the composite $n$ using Number Field Sieve. and though $1B is a lot of money I don't believe there is a known design which will break 2048 bit RSA for that budget.
However, there are other attacks to think of. Starting with how you share your public key. How does your friend know your public key is indeed yours.
Then there are various side channel attacks on RSA, if the attacker has timing or power or noise measurements of you computing stuff with the private key that can help.
Then of course to protect a $1B secret there better be plenty of physical security around your key.
Should large quantum computers become available RSA may be broken also for significant key sizes. Personally I don't expect this any time soon but plenty of smart people disagree.


Can a book cipher be cracked without key? Book cipher works this way :

Choose a reference book.
For each word find its position in the book.
replace each word by its coordinates (ie: 2,3,4 = page 2, 3rd line, 4th word).

How would somebody go about cracking a book cipher without the knowing what the key [or book used in this case] is?

Finding the key is either impossible or would take a impractical amount of time.
Given a known plain text and a cipher text, finding the right key [or book] is impractical because all possible keys that match the plain text would require
40 billion years using modern day technology to go through.

Example of a book cipher : Beale ciphers, it used the United States Declaration of Independence as a key.

First things first, finding the key (book) is not impossible, but just tough. If someone, like Google for example, has scanned millions of books into digital formats then it won't take long for them to figure out which book (simply try decrypting the first sentence only until the key is found, should be feasible for a mainframe).

Also, there is a lack of randomness. As the book you choose might not have random sequences the substitution will not decorrelate anything, which is another drawback. The best way to improve this is by choosing random references for each character by using a random number generator, which is tedious.


Is it possible: Derived key based on variable number of private keys? I have a MySQL database that I want to encrypt with AES_ENCRYPT() and have to provide access to a variable and possibly changing number of users.

Is it possible to derive an encryption key based on a variable number of users such that each user can access the data with their unique private password, but no attacker can access the data without such a password?

The original process encrypted the database with a key held on the server. I proposed as one step better to do so with a shared key held by all users with access to the system, but not stored on the server.

This would be better but ideally each user would access the data with individual private keys such that

Any given key(s) could be revoked
New key(s) could be issued
No access would be possible without a valid key

Is such a system possible?

Yes it is possible and already in use in multiple way (LUKS for example). The way it works:

Have a master key that encrypts the whole data
Append a header in front that contains the master key encrypted by the password you want
To add a password add a keyslot (master key encrypted by another password)
To revoke a password remove said keyslot (the user cannot decrypt the master key anymore)

A crude implementation could be that your put your db in a LUKS partition (it could be a file) and add or remove password as wanted.


Can you help me understand this (old) school question related to RSA usage? An old question I am preparing for a security / cryptography class has an example of an RSA chiper.

This is almost the same as "RSA by hand - did I do something wrong? (c = m on encryption)" but with some other question following up.

  Let $p=3$, $q=5$ giving $N=15$ and $\phi=8$
  Let $e=7$. Find $d$.

Fair enough, $e\times d = k\times \phi+1$ can be rather quickly evaluated to $d=7$. $k$ would be $6$ in this case.

Encryption of messages $m$ in the range $1 < m < n$ work fine with $e=d=7$. Not very helpful to have $e=d$, but it works. Well, kind of, as some messages get encoded to the same value (4, 5, 6 and 9 for example). So the target of encryption is reached only partly but the answer for the test $d=7$ is correct and complete.

This was the easier part.

Now… could you have chosen $5$ for $e$? And follow-up question: Why not? The solution provided has

  no

and

  because $5$ has a common divisior with $n$

Our lecture script and every page I found regarding RSA demands $e$ and $d$ to not share a divisior (except $1$, of course) with $\phi$. I never found a remark regarding sharing with $n$.

Problem is this: What happens if you use $e=5$ (and in turn get $d=13$) is that you get no encrytion at all. $c = m^e\ mod\ n$ stays $= m$ for all $m$.

So the mathematics "work", no information is messed up, but the desired encryption is not reached at all. Is there a reason why $5$ is kind of "neutral exponent"? Does such a thing also happen for "real" rsa values?

In this example $e=5$ is equal to $q$, is that what makes the encryption become an "Involution Mathematics" (wikipedia)?

How would one word his reasoning why $5$ is an unsuitable value for $e$? More important, how can one see this in a exam situation without excel spread sheet to quickly run some numbers (without any calculator, in fact)?

As in the other questions: Such low numbers can lead to curious-and-misleading effects. For example in this case: you choose $q=5$, and it happens that this is equal to $\lambda(15) + 1 = 5$. And that is a coincidence of this example, not a general relation.

Now… could you have chosen 5 for e? And follow-up question: Why not? The solution provided has

no

and

because 5 has a common divisior with n

Which question ans answer are you quoting here? Because it's not the one you linked to.
And I would actually say, there is no reason that $e$ has to be coprime to $N$ - except that it would be really terrible if anyone just tried to calculate $gcd(e,N)$. However, the encryption and decryption still work in the sense that you can retrieve the plaintexts (injective function).
Regarding the coincidence in th example: For every modulus, you have that $m^{\lambda(N)} = 1 \mod N$ with Carmichael function $\lambda$, and in turn $m^{\lambda(N) + 1} = m \mod N$.
And then, for two different primes $p,q$ this can be calculated as $\lambda(pq) = lcm(p-1,q-1)$. Alternatively, this is $\lambda(N) = (p-1)(q-1) / g$ for $g = ggt(p-1,q-1)$.
From that, we can see that if $\lambda(N) + 1 = q$, then we know immediately $p-1$ is a divisor of $q-1$.

So the mathematics "work", no information is messed up, but the desired encryption is not reached at all. Is there a reason why 5 is kind of "neutral exponent"? Does such a thing also happen for "real" rsa values?

Yes, it does, but not for either $p$ or $q$. It happens for $k \lambda(N)+1$ for any arbitrary integer $k$.

In this example e=5 is equal to q, is that what makes the encryption become an "Involution Mathematics" (wikipedia)?

Since this is taken from the linked question - this is something similar, but not the same. An involution happens whenever $e=d \mod \lambda(N)$, because then you have that $ed = e^2 = 1 \mod \lambda(N)$. And again, it's pure coincidence in this number example, that it is equal to $q$. That is wrong in general.


Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)? Related to "Is it possible to derive the encryption method from encrypted text?".

Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts be distinguished from random noise? Justify why, why not?

That is do the major asymmetric ciphers have any statical bias?

If you knew which asymmetric algorithm was used and you had a ciphertext of a random plaintext number and the public key that generated that ciphertext. Would it be easier than random chance to find the plaintext? Doesn't the fact that RSA requires extremely large keys imply that finding the plaintext is easier than guessing? If it is the case that finding a random plaintext is easier than randomly guessing a plaintext does this fact have any implications for the case in which the public key is not known and the attacker only has the ciphertext?

Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo $n$ (the modulus, from the public key), and thus in the range $0$ to $n-1$. This implies that values for the first byte will be quite biased (RSA uses big-endian encoding, so the first byte is the most significant byte). For anything with elliptic curves, this is even easier, since the usual representation of a curve point will be a pair of coordinates $(X,Y)$ in a finite field, matching the curve equation. Random noise has almost zero chance of producing values which will match the curve equation.

It is normally assumed that everybody knows which algorithm was used and with what encryption key (this is a public key and we mean it). The algorithm exists as software in many places (on every machine which uses that application, as source code on the developers' systems, ...) so it seems quite hard to conceal that information anyway. Asymmetric encryption algorithms are thus designed so that this is not a problem.

In particular, asymmetric encryption includes random data. Indeed, since the public key is public, an attacker could try to guess the plaintext by encrypting potential plaintexts until one matches the actual ciphertext. The random data defeats that: even if he has guessed the right plaintext, the attacker will get something different and will not know that he has guessed correctly.

Note that in practice, an asymmetric encryption algorithm has a lot of overhead (computational cost, enlarged ciphertext...) so nobody encrypts a large file with that; instead, we encrypt a random symmetric key (aka "a bunch of random bytes") with the asymmetric encryption algorithm, and then we use that symmetric key to actually encrypt the file with a fast and lean symmetric encryption algorithm like the AES -- and that will give you a sequence of bytes indistinguishable from random noise.


Hash collision resistance of $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$ So far as I can find, every method better at producing hash collisions in cryptographic hashes than generic collision search involves finding some metric for the distance between two messages' hashes and calculating alterations to each that will iteratively reduce that distance.

And further, unless I'm misreading it, none of the existing attacks is a "forgery" attack, allowing the attacker to converge on a known hash; they all work by iteratively altering multiple messages, eventually arriving at a set that all have some shared but unpredictable result.

Are these true?   If so,

wouldn't $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$ be completely immune to current attacks (at the cost of giving up on one-pass hashing)?

@RickyDemer pointed out in comments that available parallelism makes even random-walk search formidable, and it does seem to me that while appending the full hash forces full recalculation at each iteration, stripping that advantage isn't on average going to claw back more than say eight bits of strength....  though I suppose recursing the construction until at least a certain number of hash blocks have been processed could slow down attackers arbitrarily.

So, just for fun,
$$\mathcal H^0_H(m) = H(m)$$
$$ \mathcal H^n_H(m) = H(\mathcal H^{n-1}_H(m)|m)$$
$$|\mathcal H^n_H(m)|=1+n\cdot|m|$$ (with $|m|$ expressed in units of $H$'s block size)
 $$ \mathcal{\bar H}^e_H(m)=\mathcal H^n_H(m): \log_2|\mathcal H^{n-1}_H(m)| <e \le \log_2 |\mathcal H^n_H(m)|$$

So $\mathcal {\bar H}^{16}_{\rm SHA1}$ would be $\mathcal H^n_{\rm SHA1}$, $n$ large enough that at least $2^{16}$ additional blocks were hashed.

Leaving the question after accounting for his observation:

would $\mathcal {\bar H}^e_H$ be immune to current attacks (at the cost of giving up on one-pass hashing) even in the face of an attacker willing to throw $2^e$ parallel devices at it?

Your scheme is twice as slow as the original hash function.  If you were going to accept such a huge performance penalty, you'd be better off just picking a new hash function that (you trust) isn't broken.

Also, it's not clear to me how much security your construction actually adds.  I don't immediately see a proof that it is secure even if the compression function has some problems.  I'm not even sure how one would formalize this.  We'd have to assume something about the compression function, as you can't get something from nothing; but it's not clear what minimal assumptions about the compression function are sufficient to ensure that your construction is secure.


What are the constraints for an IV using AES in CBC mode? I'm designing a protocol for use into a VPN software.

The VPN frames are encapsulated into AES-256 CBC encrypted frames. I understand that IVs must be uniquely used for each message encrypted with the same key. I believe that usually protocols generate those randomly and transmit them (in cleartext, since those are no supposed to be secret) with the ciphertext.

In my case, I wanted to avoid that because transmitting 16 bytes of IV for each VPN frame has a huge cost in bandwidth (in some cases, the size of the headers would exceed the size of the encapsulated frames) so I decided to compute those IV instead, using the following mechanism:

4.4.1. DATA messages initialization vectors

   Each DATA message relies on the session keys and on an initialization
   vector. This initialization vector MUST be unpredictable.

   That is, it is computed for each DATA message using a concatenation
   of the current session and sequence numbers. The concatenation MUST
   have the following layout (numbers are in network byte order):

                  0      7 8     15 16    23 24    31
                 +-----------------------------------+
                 |          session_number           |
                 +-----------------------------------+
                 |          sequence_number          |
                 +-----------------------------------+
                 |           must_be_zero            |
                 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+

   The must_be_zero field is a sequence of 0x00 bytes so that the whole
   frame is the size of a block for the selected cipher algorithm.

   The concatenation buffer, which is globally unique, is then ciphered
   using the target host encryption key (KE) without padding and using a
   null initialization vector.

   The resulting buffer is the initialization vector to use to (de)cipher
   the DATA message.

The complete protocol specification is available here if anyone wants to read it.

The session_number is constant for a given session (it has the same lifetime than the AES keys of the session) and the sequence number is a zero-initialized counter incremented on each send.

Doing so, I believe I have an unpredictable IV (because the attacker would have to know KE to predict the IV) and that this IV is unique (because it depends on the sequence_number which changes for each message).

I realized lately that this method was expensive in CPU time and was the cause of performance issues (because of the hash computation that seems to be the bottleneck).

So I do have two questions here:

Is my method correct (read "secure") ?
How could I do differently to avoid computing a hash for each IV while keeping unpredictability and uniqueness ?

The IV for a block cipher in CBC mode must not only be "uniquely used for each message encrypted with the same key". It is usually assumed to be indistinguishable from random by an adversary.

If the IV is predictable, some attacks apply. For example, if an attacker is able to choose plaintext messages with prior knowledge of what the IV will be for this chosen plaintext, she can determine if a plaintext block in a previous message matches a guess; that's simply by submitting a message which first plaintext block is the exclusive-OR of that guess, the IV that will be used, and the ciphertext block preceding the block guessed (or the corresponding IV if the guessed block is the first block); then checking if the first ciphertext block for the chosen plaintext matches the ciphertext block for the guessed plaintext (there is a match if and only if the guess is right).

If I understand it correctly, the scheme proposed avoids transmission of the IV, replacing that IV with a (never transmitted) value obtained by enciphering a unique but predictable value, with AES and the same key as used as in the rest of the message.

This is not quite as good as a random IV. For example, an adversary temporarily gaining the capability to encipher blocks of her choice with the key (or equivalently, temporarily gaining the capability to dynamically choose plaintext blocks as a function of the previous ciphertext block within the same enciphered message) can use that capability to compute IVs that will be used in the future, in turn making it possible to verify guesses on messages encrypted after she had been denied that arbitrary block encipher capability, if she still has the capability to encipher chosen messages (having in-advance knowledge of the IVs, she proceeds just as outlined above in the regular CBC case). By contrast, with a truly random IV, the temporary possibility to encipher arbitrary blocks does not compromise the security of later messages.

Admittedly, the threat model I have been considering is quite hairy, and does not match the one usually assumed in the standard proof that CBC is IND-CPA (where the adversary has the capability to encipher arbitrary messages, but never to encipher arbitrary blocks). I fail to tell if the proposed scheme is IND-CPA, or not (that's an interesting question; an interesting variant would use decryption, rather than encryption, to prepare the IV).

Note 1: It is easy to make an implementation goof when trying to avoid reuse of a predictable value, especially if the key survives power loss.

Note 2: The scheme as described in the question does not insure integrity. That's a major practical issue.

Note 3: I fail to understand how the proposed scheme can be considered inefficient, and how "hash" crept into that consideration.


ORAM over Third Party DB Oblivious Ram (ORAM) is a cryptographic technique that is used for secure DB querying without leakage on the access patterns. There are several schemes for ORAM, amongst the most popular ones, there is Path ORAM.  However, and as far as I understand it, ORAM is tied to a client/server(s) configuration, in other words, it let a given client outsource DB services. In this, case the DB belongs to the client, and security follows from the server not learning anything from the DB content and the access pattern. My Question is as follows:

In the case the DB does not belong to the client, and the definition of security is expanded such that the server does not learn anything from the query but also the client does not learn anything from the DB, except the result of query (A third party DB), can I still use ORAM, how should I do it? and how an scheme like Path ORAM would work instead? Any insight on this precise topic is more than welcome!

ORAM  can be built on a multi-party scenario, where the data belongs to various parties using Secure Multiparty Computation. Recent research calls this approach ORAM for Secure Computation (SC-ORAM).

Given that writing and reading are required, it is my believe this would be the best approach.

In the typical SC-ORAM setting, several parties store information on remote server that holds the ORAM, and use SFE and general 2PC to execute ORAM tasks.

There are ways you can get rid of the Server however, Keller and Scholes propose the adaptation of Path ORAM, among other methods under a setting where the DB is secretly shared among the participants. Their results could be adapted to any method using ORAM and MPC.

What may be the most relevant of all, are the results by Faber et al, show how to build such setting under an MPC framework that allow for a secret shared database between 3 distrustful parties.

A short post about their results including a nice video with detailed explanations can be found here.


Block cipher mode with diffusion on ciphertext As I understand, diffusion property in AES-CBC ensures that one-bit change in plaintext will yield changes in all following blocks in ciphertext upon encryption.

I'm looking for algorithm that will have this property on ciphertext. I.e. when I change one bit in ciphertext, then plaintext after decryption will be changed in all following blocks. As far as I know, AES-CBC changes only two blocks upon decryption.

Does such a mode of operation exist? Or do I have false assumptions?

Yes, there are modes of operation that achieve the property that you are describing. For example, the Propagating Cipher Block Chaining (PCBC) mode of operation:

This mode is similar to CBC but the output for each block is propagated to the input of the next one, so a small error will propagate indefinitely, both for encryption and decryption.

There may exist other less known modes of operation that also share this property.

Depending if you consider also corruption of the Initialization Vector (IV), then other common modes of operation will do. For instance, the Counter (CTR) mode and the Output Feedback (OFB) mode will irremissibly corrupt all the plaintext blocks during decryption if the IV is changed.


How much bigger does a precomputed lookup table get when salt is added? I am trying to wrap my head around the benefits of salt in cryptography.

http://en.wikipedia.org/wiki/Salt_(cryptography)

I understand that adding salt makes it harder to precompute a table. But exactly how much harder do things get with salt?

It seems to me, like when you add salt, the number of entries in your precomputed table would = number of common passwords to precompute x number of entries in the password table (ie number of different possibile salts).

So if you have a list of 100 common passwords, then without salt, you would have 100 hashed passwords. But if you have 10 users on a system, with 10 different salts, then you would now have 1000 different combinations to check.

So as the numbers of users or the size of common password list increases, the precomputed table gets so big that you can't pre-compute it easily (if at all)

Am I getting this? Do I have it right?

NoteCross posted on cs theory https://cstheory.stackexchange.com/questions/11118/how-much-bigger-does-a-precomputed-lookup-table-get-when-salt-is-added#comment30381_11118 CS Theory Users suggested I post here too

Looks right to me, assuming you know what the 10 salts are.

If you don't know a priori what the salts are (which is typically the case when building a rainbow table), you'd have to compute for the entire salt space. This is where the big gain comes into play as for each additional salt bit, the storage requirement doubles. Thus you get exponential growth of the storage requirement.


How does a perfect hash function work? According to wikipedia, a perfect hash function is a hash function that uses algorithms that has a certain random aspect to their logic. It is suppose to be collision-free.

However due to the pigeon hole principle where given a set of all possible preimages M & a set S where S is the set of all possible hash values resulting from H(M) = (S) & set M is bigger than set S. How does a perfect hash function have collision-resistant in this case?

Based on the answer given by poncho the pre-images are known beforehand & thus the hash function is structured in such a way that there exist a unique hash value for each message. However my confusion exist is that given a message space where each message is for example at least (4 bits long = 16 possibilities) & the hash value is return as (2 bits long = 4 possibilities) value. How can this still possibly be collision-resistant?

Summary, in a perfect hash function:

Must the bit length of the hash value be long enough to cover N number of messages?
Does it not simply make a perfect hash function as a specified lookup table for a set of predetermined message?

Another side question is in the wikipedia page there is a mention of a minimal perfect hash function. Is a hash function that distributes the hash value uniformly across S (Where S is the set containing all possible Hash value resulting from message space M)

How does a perfect hash function have collision-resistant in this case?

Well, when we select a perfect hash function, we take as inputs a set of messages $M_1, M_2, M_3, ..., M_n$, and use them to select a hash function for which $H(M_i) \ne H(M_j)$ (if $i \ne j$)

Now, according to the pigeon hole principle, the output of $H$ must be at least $\log_2 n$ bits long; as $n$ is typically not that huge, that is not a practical problem.

Now, there may be messages $M$ not in the original set for which $H(M) = H(M_i)$ for some $i$; that's ok, as the collision freeness of the perfect hashing function is defined only for the original set of messages, not any additional messages.

And, as cryptostatis has mentioned, we don't have much use for perfect hashing functions in cryptography.  We do use collision resistant hash functions; however by that, we mean that while collisions $H(M) = H(M')$ do exist, it is difficult to find them.


What is the difference between PBE and symmetric key encryption? What is the difference between PBE (password based encryption) and symmetric-key algorithms?

My understanding is that symmetric-key algorithms like AES and Twofish are used in PBE. Hence PBE is just a technique which employs symmetric-key algorithms to do the work. So there is no point in comparing the two. Is that correct, or am I missing something?

As typically implemented, PBE takes a low-entropy, user-supplied password, adds some entropy to it, and thus strengthens it before turning it into a key. This key can then be used for symmetric encryption.

The problem is that the user's password often has so little entropy to start with. If an attacker learns the salt, digest method and quantity of iterations, he needs to keep trying to guess the pre-strengthened password, apply matching PBE-strengthening to his guess, and then use the resulting key to match up with ciphertext that was created with that key.

If the programmer used a decent digest method (such as PBKDF2 with HMAC SHA 256), a salt generated by a cryptographically secure pseudo-random number generator (CSPRNG) and a decent quantity of iterations (200,000 or more) then he can make it pretty expensive for attackers to guess the key.

However if the user's password is ridiculously easy to guess (such as "password") then even a good digest method and lots of iterations won't make much difference. You still need to force the user to choose sufficiently complex passwords, to maximize the entropy prior to any strengthening occurring.

OWASP has some best practices on enforcing password complexity.


Can the same random number be used in encryption and signing? In several public key algorithms, the person running the algorithm must generate a random number (that's separate from the key). Can this random number be the same for an encryption and a signature? For instance, if I'm encrypting a message with ElGamal and signing with DSA, can I use my random number from creating the DSA signature as the random input to ElGamal?

Generically speaking you can do this but you shouldn't. It may well be possible to perform specific calculations when a random number is used for both (I'll leave it to the more theoretically inclined to create a demo if this is possible for ElGamal / DSA). Another reason is that the single secret gets known then both keys/algorithms will be compromised. It's certainly harder to create a security analysis or proof if the one part of the protocol depends on the other.

You can however use your random number as input to a DRBG (deterministic random bit generator) and let that generate more random data. Then the separate values will not be dependent on each other (as long as the random bit generator is secure, of course).

When based on symmetric primitives (block ciphers/hash methods) DRBG's should perform favorably when compared against ElGamal or DSA, so the performance degradation should not be that much.


Refreshing Procedure in FHEW: membership test I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure.

Especially, they mentioned that we could change this algorithm to a more "general" one that would allow to check the membership for different subsets of integers $\bmod t$ in only one refresh procedure. However, I can't find an "efficient" approach to this problem (the one I have in mind needs more than one refresh).

Does any of you have some "hint" to guide me to the right direction?

P.S. They also mentioned a xor-for-almost-free procedure if the plaintext modulus is turned to $t=6$. I don't really understand that as - I believe - it perfectly works with $t = 4$ with the subset $S = {1;3}$. If I am wrong, please let me know.

There are to my knowledge two articles that develop further on generalized member test (or even function) extraction, I hope this may help you out:

https://link.springer.com/chapter/10.1007/978-3-319-22174-8_7 and
https://eprint.iacr.org/2017/996.pdf

A small difference there is that the ring dimension is a prime rather than a power of 2, and this eliminates the symmetry constraint.

I think you are right about the XOR almost for free working also for $t=4$, though it may require to change other parameters to get the error bound right. As for the almost-free part, note that you could extract both the carry and the xor out of the same ciphertext, and the extraction part is much cheaper than the rest of the loop: you get both bit out for essentially one refresh.


Public key encryption algorithm for short messages I need to encrypt a high number of short messages (30-200 bytes). The problem with usual algorithms, such as RSA, is that the size of the encrypted message tends to increase a lot, compared to symmetric encryption algorithms.

Ideally, this cryptosystem shoud accomplish:

Asymmetric
Size of the encrypted message must be at most 25% longer than the original
Should be fast encryption and decryption
It's not a problem if, after some work, some messages are decrypted
But private key must not be found so easily
It would ve good if it's a known algorithm with solid implementations in most common languages

The only solution I found until now is using RSA with short keys (64 bits), but I wonder what a better approach could be.

Using RSA with short keys is a bad idea since it would make the encryption less secure.

The standard way to use asymmetric encryption is to only use the asymmetric encryption algorithm to encrypt a symmetric encryption key and then use that key to do the actual communication. In this case you only get the message overhead of the asymmetric encryption scheme once which can then be amortized over many small messages.

Is there any reason you can not use this approach in your application?


Why is does the protocol of Ding et al. produce biased bits and does it relate to passive security? I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 9):

  We remark that a work of Ding et al. DXL14 proposes a different
  reconciliation method for lower bandwidth "approximate agreement," in
  the context of a key exchange against a passive adversary. However, we
  observe that the agreed-upon bit produced by their protocol is
  necessarily biased, not uniform, so it should not be used directly as
  a secret key (and the protocol as described does not satisfy the
  standard definition of passive security for key exchange).

I don't understand the biased part and how it is related to passive security for key exchange. Maybe I just don't understand the definition of passive security for key exchange. I don't know. Any help would be appreciated.

The usual definition of (passive) security for key exchange requires the agreed-upon key to be indistinguishable from uniformly random. That's not the case for DXL14 because the bits of the key are biased, not uniform. You can check that yourself if you implement the DXL 14 algorithm in (for example) SageMath. It shows that bits are biased and not uniform.

Now, you may wonder: is it because it uses Polynomial instead of Vector of polynomials, because of limited domain of $\mathit{Sig}$  function (i.e. $E= {-\lfloor {\frac {q}{4}}\rfloor ,...,\lfloor {\frac {q}{4}}\rceil \}}$), or if there’s some other reason?

Well, it's simply because any deterministic map from $\mathbb{Z}_q$ to 0,1 must be biased when $q$ is odd.


Can hashing become encrypting? hashing some data and encrypting data share some similar attributes. Surely this is why "Difference between encrypting something and hashing something" has been asked.
The point of this question is hence not repeating the different purposes. Instead I would like to ask.
Since hashing does not, by intention provide a way back I was wondering if there would be a possibility enhance a hashing scheme as to allow a way to revert the data.
To keep this a concrete and less abstract question assume this case.

Let there be data and a key provided initially (which I agree is already some derivation to hashing in which there is only data)
Then let the key serve as the initial input to a perform a hashing operation. For instance this could be a SHA256(key)
Let step 2 be continuously repeated using the result of the previous step as new input. (So essentially this would be a SHA256(SHA256(key)) as the result of the second round). The results of each round are collected until it reaches the length of data.
Finally let the data be XOR'ed with this "hash-generated one-time-pad"

Now to reverse the steps 1 to 3 can also be used to reverse again from the ciphertext to the plaintext data.
In this concrete example it seems that somehow hashing has essentially become encryption. The question therefore is this: Can this be?, is the scheme presented above an encryption scheme mainly consisting of a hashing function?
Addition
would the hash be a cryptographic safe pseudo-random-number-generator (CSPRNG) and hence this hash be part of a stream cipher setup?
Or:
Can a hash become a CSPRNG (and this would be then a stream cipher)?
Update
With happiness I have read all and even accepted one answer with thanks. Yet I want to stress that the questions focus was less
"Is this suggested algorithm a safe encryption scheme" (it is not in particular the question of safety), Instead it was about logical connectedness/links between what can be understood as encryption and which is understood as hashing
Given that for instance both hashing and encryption often attempt to produce a pseudo-random deterministic outcome. I think the question hence "can hashing become encryption?" is answered well, as it seems in some respects there is chance to use mainly a hash and end up at least with a weak encryption. Maybe the only think yet still missing (because much of some answer's efforts focus on the safety of the example algorithm) is maybe.
(1) If all encryption can be seen as hashing?
and be
(2) all encryption bases on hashing? (which I do not think)
Yet the question is already answered very nicely so any addition focusing on that aspects (instead of the safety of the algorithm - which was simple to be more concrete) would be nice.

You can in principle encrypt using a hash function, in the manner you describe (although what you have described is not necessarily a secure construction).  What you are trying to do is generate a keystream from a hash function and a key.

You can use counter mode to turn any strong pseudorandom function (PRF) into a stream cipher.  CTR mode produces a keystream that is XORed onto the plaintext to produce the ciphertext (or vice versa).   Some Message Authentication Code (MAC) functions are PRFs; in particular HMAC has been proven (Bellare 2006) to be a PRF if the compression function of the underlying hash is a PRF (as is the case with SHA-2).  So HMAC-SHA256 in CTR mode would be a secure construction that supports encryption and decryption using a hash function.

While you can do this, you probably shouldn't.  The security of block ciphers for this purpose has received more attention, and block ciphers are substantially faster than hash functions.  NIST SP800-108 "Recommendation for Key Derivation Using Pseudorandom Functions" permits HMAC-SHA256 in CTR mode as a key derivation function, but cautions against using the output as a keystream for a stream cipher as "The level of security provided ... has not been investigated".

See also Is SHA-256 secure as a CTR block cipher?.


What is the difference between Module-LWE and Ring-LWE? Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?

To quote [AD17]: "One way to informally view the MLWE problem is to take the RLWE problem and replace the single ring elements with module elements over the same ring. Using this intuition, RLWE can be seen as MLWE with module rank 1." For more intuition c.f. their introductory section, and for formal definitions c.f. §2.3 in that paper.

[AD17]: Albrecht and Deo, Large Modulus Ring-LWE $\geq$ Module-LWE.


How to authenticate over open channel? I am making an arduino project to open my garage door.  I want to make it so users with the passphrase can open the door.  Due to computational restrictions it is unlikely encryption is possible.  Under the assumption that only hashing algorithms are available, what is a secure way of protecting the door?  My thoughts:

Client sends request to open door.  Server increments counter.
Server responds with current counter value, timestamp and date, with hmac of the above.
Client responds with H(passphrase + counter) + above server response.
Server verifies hmac of server response, timestamp is within valid window, and sent hash matches known secret appended with counter.

Have I thought this one through properly or am I missing something?

What you're suggesting is likely good enough, and very likely far more secure than just about any other lock on your house.

If the only hash function you can find is MD5, go with it, but make sure to HMAC with the passphrase as the key. Again, it's not going to be the weak point of your security. I'm sure I could pick the lock on your front door faster than I could break an MD5 HMAC. Obviously, HMAC-SHA1 would be better, or SHA-256, even. See if you can find a SHA-1 for Arduino.

I don't understand the exact protocol you're proposing. Why the timestamp and a counter? Either alone would work fine, assuming you take more than one second to do the protocol. It doesn't hurt to do both, but let's break it down:

Client sends a request to open.
Server sends a unique string to the client.
Client computes HMAC(passphrase, unique-string) and sends the HMAC back to the server.
Server also computes the HMAC and compares them. If they match, the door opens.

That seems good enough to me, the only thing we're debating is the content of the unique string. A timestamp alone would work if you prevent replays. You could do that by having the Arduino spin until the clock ticks. But there's also nothing wrong with an equivalent of:

static int counter = 0;

...

sprintf(challenge, "%d-%d", time(0), counter++);
send(challenge);

and that would be unique enough.

The risk in this basic protocol would be someone pre-computing an appropriate HMAC. Strictly speaking, the timestamp and the counter helps thwart this, but in practical terms it isn't really going to help. If someone intercepts any given successful challenge and response, they can run a dictionary search on passphrases to find the right HMAC.

But still, it's almost certainly more secure than the locks on the other doors.

Jon


Smart Card - Entropy during on-board public key generation I know that some (advanced) smart cards or tokens allow generating key pair directly on the device, but I wonder how the card can gather entropy during the process. Any idea ?

In short, they retrieve the entropy directly from a source on the chip.

From Wikipedia:

  In computing, a hardware random number generator (TRNG, True Random Number Generator) is an apparatus that generates random numbers from a physical process, rather than a computer program. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, and other quantum phenomena

All reasonably secure smart cards contain a hardware source of entropy. In that way they are not dependable on entropy from the outside. This is of course highly important for smart cards as they should consider any outside information as possibly tainted.

Often these sources of random entropy are post-processed by some form of whitening. And often they are fed into a Deterministic Random Number Generator before the data is used by an application or send to the outside world. On less secure cards this is often a LSFR, but on higher-end cards NIST modes such as CTR_DRBG are used. This is therefore somewhat similar to how RD_RAND operates on modern Intel CPU's.

Beware to check if on card key generation is actually certified in the field for the particular smart card. Even if the key generation is supported, it may not contain enough protection against side channel attacks in the field. In that case you should only use the on board key generation within a secure environment. This is particularly true for RSA key pair generation.

Just like all the other parts of a smart card processor, the entropy source as well as the post processing can come under attack. Furthermore there have been (many) mistakes in the implementation of random generation in smart cards. Some of these can be contributed to the sometimes extreme limitation of resources on smart cards chips (over-optimization).


How to calculate key size for Diffie-Hellman key exchange? How to calculate key size for Diffie-Hellman key exchange? The strength obviously depends on both generator and prime modulus.

  Formula:

  $$g^x\bmod p$$

  Public values:

  $$g=3$$

  $$p=17$$

  Alice:

  $$x=15$$

  $$3^{15}\bmod 17=6$$

  Bob:

  $$x=13$$

  $$3^{13}\bmod 17=12$$

  Alice:

  $$12^{15}\bmod 17=10$$

  Bob:

  $$6^{13}\bmod 17=10$$

The original numbers $(3,17,13,15)$ weren't that (no way secure, but not that) low and they ended up with 10 which is much easier to brute force than guessing each part from $g^x\bmod p$.

With Diffie-Hellman in its most general description, there are three different types of objects involved:

The group
The exponents
The generator

The group
Diffie-Hellman operates in a group. This group may be $\mathbb Z_p^*$ or may be the points on your favorite elliptic curve usually. Usually the group parameters are what needs to be adjusted over time the most due to computational advances and the advances in cryptanalysis of the discrete logarithm problem (DLP). So what you want is a group where the DLP is assumed to be hard and for this you need to adapt the group or change parameters (like the prime or curve parameters).*
The exponents
There isn't much to the exponents with diffie-hellman except that you want to avoid predictable exponents, because then the other party or an adversary could predict your exponent and calculate the shared secret from that.
The generator
The generator of the subgroup of the group is actually fairly irrelevant. You need to make sure it indeed generates a subgroup of appropriate size and that's about it, especially you should avoid the neutral element or other elements with small order.

*This is actually not true as you usually want the computational diffie-hellman (CDH) problem to be hard, but these two are very closely related most of the time such that there's no known way to break CDH without breaking DLP.

As for the "the shared secret is actually easier to brute-force than all other values". While this is true here, this doesn't scale.
Brute-force of the shared secret scales at $\mathcal O(q)$ (because the shared secret is a random element from the group, with $q$ being the order of said group).
The best generic attack on the discrete logarithm problem scales at $\mathcal O(\sqrt q)$ (there are more efficient ones for prime-moduli-groups).
Now chunk in some numbers. If you multiply $q$ by, let's say, 10,000 you get a workload increase of 10,000 for brute-force, but only 100 for the better attack. So brute-forcing the shared secret clearly isn't the way to go for real-life parameters.

If you're seeking for advice on which keylengths to choose and which parameter set corresponds to which security level, you can use Keylength.com for the TL;DR and read the Lenstra-Verheul paper (PDF) for all the details.