Is this paper's technique for factoring RSA 2048 with noisy qubits realistic? A paper titled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits has just come out which proposes a technique to factor RSA keys with moduli up to 2048 bits with a design whose assumptions they stress are realistic. What are the implications of this new research?

The abstract of the paper, which lists some of the assumptions:

  We significantly reduce the cost of factoring integers and computing discrete logarithms over finite fields on a quantum computer by combining techniques from Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Eker-Hstad 2017, Eker 2017, Eker 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of $10^{−3}$, a surface code cycle time of 1 microsecond, and a reaction time of 10 micro-seconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses $3n+0.002n\lg n$ logical qubits, $0.3n^3+0.0005n^3\lg n$ Toffolis, and $500n^2+n^2\lg n$ measurement depth to factor $n$-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

How feasible would it be to design a quantum computer with these properties? 20 million qubits is obviously significantly more than any general purpose quantum computer has right now, but the paper also points out that the qubits only need nearest neighbor connectivity, which is much simpler.

I'm one of the authors of the paper.

In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others.

"Approximate encoded permutations and piecewise quantum adders
". We put small amounts of padding at various places in our registers so that we can perform addition operations in piecewise fashion and also avoid normalizing modular integers into the [0, N) range until the end of the computation. There are information leakage issues that we had to solve in order to apply these operations in a quantum context, and these cause the representation with padding to be approximate, but otherwise it's a known standard classical technique (e.g. it's called "nails" in GMP).

Modular addition using these approximate representations are significantly more efficient than modular adders using the normal representation. For example, here is a comparison of the time*space of each addition when targeting a 0.1% total approximation error rate over the entire algorithm. The "runway" entries are the ones using the approximate representations. The runway entries are significantly better across the entire span of register sizes:

These representations build on previous work by Zalka from 2006.
"Windowed quantum arithmetic". Classically, if you know what constant you are going to multiply by when producing a physical multiplication circuit, you can specialize the circuit to that factor. This allows you to make the circuit smaller and more efficient. There is a quantum equivalent to this optimization, where the quantum program can be optimized using knowledge of the classical constant you are going to multiply by. We use this to make n-bit quantum-classical multiplication programs log(n) times shorter.

We then generalize the technique, apply it simultaneously to the exponentiation part of the circuit, and save another factor of log(n).

This paper builds on previous work by R. Van Meter from 2005 (although we didn't actually know this when writing the paper, so it is not cited in the current version).
"Flexible layout of surface code computations using AutoCCZ states". This one is by far the most quantum-mechanics-y, so I won't try to explain the details. You can think of it as finding a better way to pack the computation, reducing the amount of space overhead used when routing data around and also allowing it to progress at a rate limited by the classical control system's reaction time instead of by the error correction code distance.

The main contribution here may actually be saying what the layout is in the first place, as opposed to just talking about it in the abstract. We have an operating area where the ripple-carry addition zig-zags back and forth horizontally, while input data streams through vertically, and the operating area is gradually moved as the data is processed.

Location of data (rows from top to bottom) over time (left to right):

A mocked up snapshot of the 2d data layout during a small amount of time:

The ideas in this paper build on previous work by Fowler from 2012.

In summary, there are a lot of ideas in the paper but they are not radically new (they build on previous work) and they are not strongly coupled (if one is wrong, the others will still stand). So I see the savings as being on pretty strong footing. I'm more worried about whether or not people will be able to build quantum computers with 20M qubits than I am about the estimate being off by a factor of 2.


How secure is Firestore / Google Cloud server-side encryption? We use Firestore. On their Google help page they say it is AES encrypted.

https://cloud.google.com/firestore/docs/server-side-encryption

But this means in the moment a user is logging in, the data is decrypted on the server not the client? So if there is a corrupt Google admin guy, could he wait till I login and then get the decrypted data?

Server-side encryption means that the servers, owned by Google and running in a datacenter rented or owned by them, has access to the encryption keys when you log in. Compare this with client-side encryption, where only the client has access to the key and the server reads and writes opaque ciphertext. So yes, a corrupt sysadmin or someone with sufficient access to the server your data is stored on would potentially be able to obtain the encryption key and plaintext data.


Why can't Homomorphic encryption schemes support algorithms with conditions/branching? If it isn't already apparent from the title of my question, i should make clear that I have only a very basic understanding of homomorphic encryption.

I would like to know why homomorphic encryption schemes cannot support algorithms with conditions/branching, and what the likely impact will be on the overall adoption of HE schemes. Given this limitation, are HE schemes likely to be useful in real life? Thanks.

I think you have a misconception.  Fully homomorphic encryption can support algorithms with conditions and branching.  Any such efficient algorithm can be unrolled to be implemented as a circuit (say, with just AND and NOT gates), removing all conditions and branching, and thus can be implemented on encrypted data using fully homomorphic encryption.

Of course, fully homomorphic encryption schemes are hardly practical right now; search this site for more details.


What is the difference between SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms? I installed djigzo on my android phone and I want to use it for smime mail.
I don't know the difference between choosing SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms in the settings.

My online search only returned OIDs and code samples. Can you enlighten me?

It seems that djigzo uses bouncycastle and if you look in the source at the DefaultSignatureAlgorithmIdentifierFinder, e.g., here, then you find:

algorithms.put("SHA256WITHRSAENCRYPTION", PKCSObjectIdentifiers.sha256WithRSAEncryption);
algorithms.put("SHA256WITHRSA", PKCSObjectIdentifiers.sha256WithRSAEncryption);

Thus, it seems that both refer to sha256WithRSAEncryption, which means RSA with SHA-256 and PKCS #1 v1.5 padding.


Comparing the first 50 bits of a hash Vs. the last 50 bits of hash If I had a hash function outputting a 256 bit hash, would there be any discernible difference comparing the last 50 bits of 2 hashes versus comparing the first 50 bits?

I guess what I am trying to say is can you have 2 hashes that finish with the same 50 bits yet have the first 206 bits different? (Assuming we are using Merkle-Damgård setup)

My gut says it shouldn't be any different because theoretically a hash should use all possibilities of hash values with equal randomness.

If I had a hash function outputting a 256 bit hash, would there be any discernible difference comparing the last 50 bits of 2 hashes versus comparing the first 50 bits?

No, not for a correctly constructed cryptographic hash function.

  My gut says it shouldn't be any different because theoretically a hash should use all possibilities of hash values with equal randomness.

That is correct.

  I guess what I am trying to say is can you have 2 hashes that finish with the same 50 bits yet have the first 206 bits different? (Assuming we are using Merkle-Damgård setup)

Yes, absolutely. There is always a possibility of two hashes matching by pure chance, but by checking only 50 bits instead of the full hash, you are increasing that probability significantly.

Checking only 50 bits of a 256-bit hash is essentially the same as checking all of a 50-bit hash (whichever 50 bits you choose). And as SEJPM is stating in their comment, the probability of two hashes of this size matching by chance is about one in $2^{25}$ (i.e. much higher than one in $2^{50}$) because of the birthday paradox. As user Meir Maor rightly pointed out, the birthday paradox does not apply here.

This answer to the similar question "Should I use the first or last bits from a SHA-256 hash?" might be of interest to you.


Knowing SHA256(m) and k, is it possible to calculate HMAC-SHA256(k,m)? Cryptographic APIs use to allow for calculating HMAC-SHA256 signatures for message m and key k with something like HMAC-SHA256(k,m). However, I found out that none of them (unless I overlooked it) allows for calculating the MAC from the hash of the message, and key. IOW, the API to calculate HMAC knowing only h=H(m) and k is not available.

For example, Java provides the Mac class, but only allows for a buffer to be fetched so that the output (the HMAC-SHA256) is calculated.

Does this cryptographically makes sense, and if yes, any clue on how to implement this in Java?

No, knowing the SHA-256 hash of an arbitrary message, and a key, it is not possible to compute the HMAC-SHA-256 for that message and key; that's because in HMAC, something dependent on the key is put in front of the message before hashing the message.

Addition: if what's asked was possible, then a break of SHA-256 allowing to find collisions would be a death blow for HMAC-SHA-256 (the HMAC for messages colliding per SHA-256 would be identical for any key). By contrast, we have excellent hope that the HMAC construction would provide enough protection to keep HMAC-SHA-256 practically safe. There's the precedent of HMAC-MD5, which remains unbroken even though MD5's collision resistance is trounced; and the theoretical security argument made by  Mihir Bellare in New Proofs for NMAC and HMAC: Security without Collision-Resistance.

Independently, on the same line: knowing the SHA-256 hash of an arbitrary key of more than 64 bytes, and a message, it is possible to compute the HMAC-SHA-256 for that message and key; that's because by definition of HMAC, for keys larger than the message block size (64 bytes for SHA-256), the first operation made with the key is to replace it by its hash.

Note: in this answer, arbitrary excludes guessing a low-entropy value from its hash.


Figure out the encryption being used There is a web API (for a game) that sends and receives data encrypted in hex format. I'm interested in accessing the api outside of the game client (mobile app). When sending a request with an invalid query, the server sends an encrypted response (as a hex string) that is different every time (same length), but I'm fairly confident that the dencrypted message is the same.

I've been doing some research lately about d/encryption and have a feeling that it is impossible, but I figured I'd ask in case I'm mistaken.

Q: Given a (unlimited) series of hex strings that all decrypt to the same message, is it possible to figure out (brute force?) the encryption?

Here are some of the values:

6683A5C618FDA544DF87F6
1CD9EE2E62A7EE3E85CC1E
7AE3FDAA049DFD58BFDF9A
73863C600DF83C51DA1E50
39B4789847CA781BE85AA8
1C024088627C403E5E62B8

In order to tell for certain which algorithm is used from the cipher text alone, you have to break the key as well. It is however possible to make some educated guesses about the algorithm.

Your strings are only 88 bits long. That rules out every asymmetrical algorithm that I know of.

If it is correct, that all of those strings encrypt the same message, then it would have to be a probabilistic encryption (which is also best practice security-wise).

A block cipher in CBC mode is one of the first probabilistic encryptions, that many cryptographers learned about. However a CBC mode encryption takes up at least two blocks worth of cipher text, and I know of no block cipher with blocks as short as 44 bits. I do know a few with 64 bit blocks, but except from very special cases, such short blocks should be considered obsolete by now. AES has a 128 bit block, meaning your messages are too short for even a single block.

Every probabilistic encryption uses an IV (possibly called a nonce in some contexts). In case of CBC the IV is a full block, but other modes like for example CTR can use a shorter IV. Additionally since CTR operates as a stream cipher, there is no requirement for full blocks being used in the enciphered data. Partial blocks will work just fine in CTR mode.

Your strings are likely 3 + 8 bytes, with either 3 bytes IV and 8 bytes data or vice-versa. An IV as short as 3 bytes is ridiculously insecure (which hasn't stopped it from being used in widely used protocols in the past).

If the messages are using 3 bytes of IV and the 8 bytes for some reason is a full cipher block, then it would have to be one of the ciphers with a 64 bit block. DES is one cipher with such a block size, Blowfish is another. To the best of my knowledge among the block ciphers with 64 bit block size, DES was the most widely used, and Blowfish was the most secure.

It could also be that there is 8 bytes of IV and 3 bytes of message. When encrypting with CTR it could make sense to split the input blocks into half IV and half counter. If IV and counter are 8 bytes each, the block size would have to be 128 bits. There are many ciphers with that block size. AES is one of them. If this is how the encryption works, that message would be 3 bytes long. It might be that the message being used is always either yes or no.

Encryption without integrity is almost always a bad idea. But since people are so often told about encryption and not so often about data integrity, it is not so unusual to encrypt data without integrity. 88 bits is very short if it is both probabilistic and protects integrity, so I guess it doesn't do both. So if you believe it really does provide probabilistic encryption, I guess it has no integrity.

Feeding mangled messages into the legitimate decryptor would provide clues as to whether any integrity checks are in place. Other than that, it is probably a lot less work to simply reverse engineer the code than to break the encryption.


Why can’t DSA be used for encryption? This question at StackOverflow mentions that DSA cannot be used for encryption. But both RSA and DSA can be used to generate public and private keys, right? Then why can't I use the DSA public key to encrypt?

DSA stands for "Digital Signature Algorithm" - and is specifically designed to produce digital signatures, not perform encryption.

The requirement for public/private keys in this system is for a slightly different purpose - whereas in RSA, a key is needed so anyone can encrypt, in DSA a key is needed so anyone can verify. In RSA, the private key allows decryption; in DSA, the private key allows signature creation.

The fact that RSA also can be used for signatures is a result of the textbook algorithm being a trapdoor permutation - in simple terms, this means the ciphertext and the plaintext are part of the same set space. It is not a requirement of a public key algorithm for this to be the case - public key algorithms just require trapdoor functions.


Could completely public passphrase hashes ever be reliably secure? This is a hypothetical question and I only have a basic understanding of Cryptography.

If one were to follow the very best cryptographic practices for storing passphrases, could it ever be possible to publish literally all information (the usernames, the hashes, the salts, the algorithms used) and still be reasonably certain that no-one could crack them?

I'm assuming there would have to be a minimum-length constraint - like 12, or maybe 16 characters minimum - and obviously if someone were to choose "1111111111111111" then it would be easily guessable, but assuming people choose sensible passphrases, like "correct horse battery staple", could this work?

For any value $x$ chosen randomly in a set of size $N$, and hash function $h$, publishing $h(x)$ allows for an exhaustive search on $x$ with average cost $N/2$. This is unavoidable.

The problem with passwords is that, by virtue of fitting in the brain of a human, they tend to come for a set of potential passwords of relatively small size $N$. We try to cope with that by making $h$ a slow function, and using a new variant of $h$ every time (that's what salts are about). See this answer for details on password hashing.

Now that's just an average. Though most humans will have trouble remembering many fat random passwords, a normal human can remember a really random password with enough entropy to defeat exhaustive search. This will imply some effort, so a lot of users won't do it.

Entropy is the key word. An entropy of $n$ bits means a set of passwords of size $N = 2^n$ (that's a simplification: I am assuming that all potential passwords have an equal probability of being selected). In the case of the famous comic which describes the "correct horse" method, an entropy of 44 bits is claimed. This is mathematically correct (see that answer for an analysis). However, 44 bits are not a lot, certainly not enough to defeat exhaustive search. Cryptographers have long required at least 80 bits, as a rule of thumb for "unbreakable through brute force"; and the relentless progress in technology, as well as an aesthetic appeal for powers of two, now make "128 bits" to golden rule. It can be argued that 128 bits of entropy ought to resist brute force for quite some time.

Basically, the "correct horse" password generation method assumes a list of 2048 words, and four words are selected randomly and uniformly in that list. That is, there are four successive selections of one word in the list, and the selections are independent of each other (so the same word can be selected several times). Make that twelve words instead of merely four, and your password will be rock solid, even if you publish the hash of it.

(If you use slow hashing with a salt and enough iterations, these twelve words can be reduced to, say, nine or ten words.)


Bit-strength of discrete logarithm for a group of integers modulo a safe prime Preliminaries

Let $p$ be a safe prime number.
Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$.
We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ .

Let $g \in \mathbb{Z}_p$ be a primitive element of $\mathbb{Z}_p$ .
Let $h$ be an element of $\mathbb{Z}_p$ .

We define the Discrete Logarithm Problem for a group of integers modulo a Safe prime (DLPS) as:

  DLPS: Find the integer $k$ such that $\;\;1 \le k \lt p\;\;$ and  $\;\;g^k \equiv h \pmod p$ .

We assume that the best algorithm to solve DLPS is the Number Field Sieve for Discrete Logarithms, which has an expected running time of
$$L_p\left[1/3, \sqrt[3]{64/9}\right] \,=\; e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln p\big)^{1/3}\big(\ln \ln p\big)^{2/3}}$$

Questions

If we choose $p$ to be a 2048-bit safe prime, which is at least equal to $2^{2047}$, then the expected number of arithmetic operations needed to solve DLPS is approximately equal to:

$$e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln 2^{2047}\big)^{1/3}\big(\ln \ln 2^{2047}\big)^{2/3}} \\
\approx \, e^{\textstyle \big(1.923\big)\big(1419\big)^{1/3}\big(7.258\big)^{2/3}} \\
\approx \, e^{\textstyle \big(1.923\big)\big(11.24\big)\big(3.749\big)} \\
\approx \, e^{\textstyle \big(81.00\big)} \\
\approx \, 2^{116.9}$$

Is it correct?

Should I make sure that $(p+1)$ has a large prime factor? (to make $p$ a strong prime)

If I am not mistaken, this is the graph showing the security level of DLPS in function of the size of $p$:

Edit 7th June 2019: Here is the context in which I will use this discrete logarithm problem:

Context

I am creating an online massively multiplayer video game. In this game, the player moves around a character and performs actions in a persistent virtual world. I use the discrete logarithm problem as an in-game currency. Every action performed by a character (move around, buy an item, throw a projectile, etc.) has to be paid by the player with CPU time. This way, I don't have to spend my time monitoring players to detect cheaters (multiple accounts, farming bots, etc), because what cheaters usually do is explicitly allowed in my game.

Here is how it works: to earn the right to perform an action in the virtual world, the player requests a discrete logarithm challenge to the game server. Then, the server generates random values for the generator $g$ and the exponent $k$, computes the result $h \equiv g^k \pmod p$, and send the values of $g$ and $h$ to the player. Then the player's client computes the value of the exponent $k$ and send it back to the server to receive credits.

The value of $p$ will never change, and the values of $g$ and $k$ will be different for each challenge. The player can choose the difficulty of the challenge by setting an upper bound on the bit-length of the value of the exponent $k$ (the amount of credits earned is proportional to the amount of CPU time spent).

For a proof of work scheme, you're probably better off making $p$ large enough that you don't have to worry about NFS (e.g. 2048 bits or more), or alternatively, using an elliptic curve group (e.g. P256 or Curve25519).

Instead, you'd tune things so that the generic attacks (e.g. Big-Step-Little-Step) are the optimal attacks, and use that to select the difficultly (range of $k$); if the solver knows that $0 < k \le M$, then these generic searches will take circa $\sqrt{M}$ group operations (modular multiplications, elliptic curve additions), and that's the best the searcher can do (assuming that he doesn't have any further insight into the group structure - that's what we're trying to ensure by making NFS infeasible).

Now, while this would work as a 'proof-of-total-work', I'm not sure if it really meets your requirements, because someone with significant amount of parallelism (e.g a botnet farm) may be able to accelerate this computation significantly.

A better approach might be to have the serve publish integer $g$, $k$ and a composite $n$, and ask the client to compute $g^{2^k} \bmod n$; this type of operation isn't greatly parallizable (because each squaring operation must be done sequentially), and the server (who knows the factorization of $n = pq$) can verify this by checking a claimed answer $A$ by the relation $A \equiv g^{2^k \bmod p-1} \pmod p$


How does one attack a two-time pad (i.e. one time pad with key reuse)? My question might appear the same as the question Taking advantage of one-time pad key reuse?, but actually I did read all the answers and none of them helped me with the details I need.

I am new to cryptography and my problem is with two time pad attacks on OTP.
The problem I had in my course was that I have 10 ciphertexts encrypted with the same key $K$. I am then given another ciphertext that I should decrypt.

I know that XOR-ing two ciphers gives me the XOR of their original messages.

My question is what is the correct thing to do after that?

I tried to take 3 ciphertexts $C_1, C_2$ and $C_3$.

Then get $S_1 = C_1 \oplus C_2  \oplus $' ', also get $S_2 = C_1 \oplus C_3 \oplus$ ' '.

After that I compared all corresponding characters in $S_1$ and $S_2$,
and if $S_1[i] = S_2[i]$ then I calculate $S_1[i] \oplus C_2[i]$ to get $K[i]$.

I tried this on paper before coding and it worked, but I might be missing something.

Is this the right approach? Why does it work?

Well, the classical answer to "what is the correct thing to do after you have the XOR of the two original messages" is crib-dragging.

That is, you take a guess of a common phrase that may appear in one of the plaintexts (the classical example against ASCII english is the 5 letter " the "), and exclusive-or that against the XOR of the two original messages in various locations.  If one of the plaintexts had the text of the crib (" the " in our example), then the result of the exclusive-or is what the other plaintext had in that position; if neither plaintext had that, it's likely that the result of the exclusive-or is just gibberish.  And, once you have a plausible short section, you can extend it (for example, if you know that one of the plaintexts is " na**", you can go through the dictionary of all words that start with "na", use those as cribs, and see which makes the other plaintext make sense).

In addition, you can often deduce things directly from the bit pattern.  For example, if the messages are in ASCII, then one thing to note that bit 6 of letters is set, but bit 6 of spaces, numbers and (most) punctuation is clear; because spaces are far more common than numbers and punctuation, then that will give you a good guess of where spaces occur in the texts (albeit without telling you which message a specific space appears in).

Now, if you have 11 messages all encrypted with the same pad (an "11-time pad"), things get even easier.  Obviously, you can grab a crib across one message, and check it against the other 10; if it makes all 10 make sense, then it is almost certainly accurate.  Even better, by using the observation that you can distinguish spaces from letters (again, by comparing bit 6), you can find where all the spaces appear in the messages; these all act like 1 character cribs, probably revealing virtually all the text of all the messages.


Advise key management protocol Assume that sender and recipient both already have each others public keys(certificates). Sender needs to generate session key to encrypt some data and sends encrypted data to recipient. All offline - without interaction steps. But Sender must be authenticated. Could you advise well-known key management protocol to solve this problem?
I asked this question some times ago but it was deleted. Now I have found the exact answer and want to publish it.
Updated: I answered my own question but would be great if somebody comment or give alternative answer. I want to emphasize that protocol should be offline - interactive protocols like TLS doesn't fit.
If such offline protocol without TLS-like handshakes are not possible without additional threats/attacks (replay and others) - please specify most secure protocol and its threats that it has but TSL doesn't.
authentication of source is necessary. non repudiation is optional.

There is an answer in PKCS#7 in section 11. Signed-and-enveloped-data content type.
Below encryption with the signer's private key means signing process.

"The signed-and-enveloped-data content type consists of encrypted content of anytype, encrypted content-encryption keys for one or
more recipients, and doubly encrypted message digests for one or more
signers. The "double encryption" consists of an encryption with a
signer's private key followed by an encryption with the content-
encryption key.

The process by which signed-and-enveloped data is constructed
   involves the following steps:

    1.   A content-encryption key for a particular content-
         encryption algorithm is generated at random.

    2.   For each recipient, the content-encryption key is
         encrypted with the recipient's public key.

    3.   For each recipient, the encrypted content-
         encryption key and other recipient-specific
         information are collected into a RecipientInfo
         value, defined in Section 10.2.

    4.   For each signer, a message digest is computed on
         the content with a signer-specific message-digest
         algorithm. (If two signers employ the same message-
         digest algorithm, then the message digest need be
         computed for only one of them.)

    5.   For each signer, the message digest and associated
         information are encrypted with the signer's
         private key, and the result is encrypted with the
         content-encryption key. (The second encryption may
         require that the result of the first encryption be
         padded to a multiple of some block size; see
         Section 10.3 for discussion.)

    6.   For each signer, the doubly encrypted message
         digest and other signer-specific information are
         collected into a SignerInfo value, defined in
         Section 9.2.

    7.   The content is encrypted with the content-
         encryption key.

A recipient opens the envelope and verifies the signatures in two
   steps. First, the one of the encrypted content-encryption keys is
   decrypted with the recipient's private key, and the encrypted content
   is decrypted with the recovered content-encryption key. Second, the
   doubly encrypted message digest for each signer is decrypted with the
   recovered content-encryption key, the result is decrypted with the
   signer's public key, and the recovered message digest is compared to
   an independently computed message digest..."


Are there any protocols that are truly secure from active and passive MITM attacks? Are there are any cryptographic protocols or algorithms that can prevent active MITM attacks or interference when initiating a new connection to a server or someone you have not exchange keys with before?

For example:

Alice's computer ➜ ISP ➜ Internet ➜ ISP ➜ Bob's server

It is known that ISPs are compromised with secret rooms and equipment in use by the NSA/GCHQ especially in USA and UK. New Zealand feeling left out of the spying debacle decided to follow suit in the last few days and they just passed a law forcing ISPs to assist the GCSB in surveillance.

The chain is now really this:

Alice's machine ➜ ISP (hostile) ➜ Internet (hostile) ➜ ISP (hostile) ➜ Bob's machine

Assume either of the ISPs have some device or person which can do an active MITM attack in real-time. For example it detects a key exchange and instead of serving Alice/Bob the real key they give them the attacker's key instead. Which protocol lets Alice or Bob know a forgery has taken place? If they detect a forgery, does this cause a denial of service for Alice or Bob who can no longer communicate without being monitored?

Let's be clear, Certificate Authorities are not the solution. I'm not even sure systems like Perspectives or Convergence would help as Alice's or Bob's machine still need to connect through the hostile ISP to contact a notary or set of notaries to verify the authenticity of the original public key. How can you do that securely if the ISP is compromised? The ISP can simply make a response back to Alice/Bob pretending to be the notary and saying everything is fine.

So how do you solve the authenticity problem in this scenario and prevent active MITM attacks?

What about if Alice and Bob already have a shared secret key (perhaps exchanged in person), does this solve the problem? What protocols can be used then and do they fully prevent active MITM and denial of service?

In short:

If you assume no shared secret, you can not build anything. For some theory on this, a similar assumption is formalized in the Dolev Yao model (all messages are send via the attacker, assumes perfect encryption), where no unauthenticated key exchange is possible.

If you assume a shared secret, then it depends on the kind of secret to run a number of protocols:

MITM for key exchange like Diffie-Hellman usually results in a different key for the connection between Alice and Eve and the connection between Bob and Eve (due to DLOG still being hard). So you start with a normal key exchange, but don't use this key for your session straight away.
run a one-way function on both the session key from the first part and the shared secret. For example you could use a key derivation function on the cocatenation. Eve should not be able to calculate this key, since she does not know the secret.
Use the derived key as session key or MAC key, or whatever you want to do with it. Eve should not know it, and it can be used to check message integrity (or to notice if Eve already tempered with the first key exchange).


Hash length vs Data length I'm very (!) new to the world of cryptography, so pardon me if this question is very basic.

Related to hashing, something that hasn't become clear to me is the relation between data length and hash length.

If I understood correctly, any change in the data should also alter the hash, while still avoiding hash collisions. So my question is if it's possible to have a hash whose length is inferior to the data length and still avoid hash collisions.

My use case would be something like hashing data with less than 128 bits, but I absolutely cannot spare another 128-bit space to store the hash. I would be able to store maybe a 32-bit hash, if even that.

Are there any hashing functions that perform better in these scenarios over others?

Edit: To clear some confusion, here are some bullet points:

I have a set of data that is about 128 bits long. I can only fit another 32 bits in that same packet.
Ideally, the data should not be readable by anyone else other than the destination (there is a shared key), and it should be possible to identify 'fake' packets (modified or injected into the network)
My first idea was to create a 32-bit hash and then encrypt the whole 128+32 bit using the shared key
I'm looking for better suggestions/guidelines, since I'm a newbie in this area.

Thanks!

My use case would be something like hashing data with less than 128 bit, but I absolutely cannot spare another 128 bit space to store the hash. I would be able to store maybe a 32 bit hash, if even that.

If you have any kind of security in mind, $32$ bit are definately not enough. Even $128$ bit is not enough today if you need collision resistance due to the birthday paradox.

With just $32$ bit output, everyone can find a preimage on the most basic computer within a very short time (seconds maybe) by just trying out enough possible inputs.

  if it's possible to have a hash whose length is inferior to the data length and still avoid hash collisions"?

I think there is a misunderstanding in the properties of a cryptographic hash function. My first suggestion would be to study the properties collision resistance and preimage resistance in detail (the wiki-link above is a useful starting point). As you can see, the length of the input is not mentioned at all - it does not matter for the security. What is stated is:

It should be hard to find any $m_1,m_2$, such that $h(m_1) = h(m_2), m_1 \neq m_2$ (collision resistance)
Given $h$, it should be hard to find any $m$, s.t. $h(m) = h$ ((first) pre-image resistance)

It is not about:

if collisions are possible (because they always are - that is given by the fact that the input is of arbitrary length)
special treatment of certain lengths for the property in general (including shorter/longer than the input)
any kind of brute force: If you have just two possible messages and know $h(m)$, then it's easy to test just both and see which message was the preimage.

And then, it's important to get a rough idea what is actually feasable in tdoay's world and what is not. A full search over $2^{32}$ bit is easy. A full search over $2^{64}$ is practically possible but far beyond what you can do on a single computer (e.g. that's roughly the number of hashes of the entire bitcoin network in $3.7$ seconds), $2^{128}$ is practically impossible ($2^{100}$ hashes would take the bitcoin network already around $8000$ years at its current rate - $2^{128}$ is around a quarter million times longer).


How to prove that a one way function is uninvertible? Suppose we define the "hard to invert" part in the definition of one-way functions differently:

  A function $\ f : \{0,1\}^* \to \{0,1\}^*$ is called uninvertible if it is easy to compute $f$ but there does not exist a PPT (polynomial time) algorithm $\ A$ such that, for every string $x$, on input $\ (1^k; f(x))$, $\ A$ outputs $x'$ such that $\ f(x) = f(x')$.

How to show that if $\ f$ is a one-way function, then it is an uninvertible function.

I know that if $\ f(a,b) = a\land b$, and let $x$ be an output of $\ f$. So there cannot be unique values of $a,b$ such that this is invertible. So basically this is uninvertible. I am not getting the connection between PPT algorithm and uninvertible function.

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very efficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unique preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not uninvertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash function is uninvertible (this is why we store hashes of passwords).
Also, that RSA is one-way: an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is uninvertible is clear from the definitions (write down your definition of one-way function: it should be immediate; if not, edit your question adding that definition).


How to generate a certificate/PEM from specific plain text keys? Is there a way to generate a certificate with a pre-stablished public/private plaint text keys?

Explaning: I generated some keys on a web site for development propurses, but now one of the parties requires it on a X509 certificate...

Sample keys can be generated here: http://travistidwell.com/jsencrypt/demo/

Yes, of course this is possible.

Generally you are required to first create a certificate (signing) request or CSR - a specific structure sometimes also called PKCS#10 after the standard that defines it. The certificate request contains the public key inside of it. This certificate request needs to be signed with the pre-established private key for the certificate. This certificate request can processed by a local or remote certificate authority, which returns the certificate. Commonly the certificate or certificate chain and the private key then need to be stored together into a (PKCS#12) key store.

Alternatively you should also be able to directly to create a self-signed certificate. Again, the public key is contained in the certificate. And again, the private key is required to perform the signing.

Note that the public key is commonly also contained in the (PKCS#1 or PKCS#8) structure of the private key. This means that you may not have to explicitly include it in any commands for creating the certificate request or self-signed certificate.

I found some answers on this page on how to do this with OpenSSL:

Generate a CSR from an Existing Private Key

openssl req \
       -key domain.key \
       -new -out domain.csr

Generate a Self-Signed Certificate from an Existing Private Key

openssl req \
       -key domain.key \
       -new \
       -x509 -days 365 -out domain.crt

here the domain.key is the OpenSSL PEM encoded private key.

I've tested both methods successfully after copying the private key to a file called domain.key. If this goes wrong, it's likely because of copying or system issues.


Meaning of the term "Key Material" I am reading specifications from my client that focuses on the topic of security. In these specs, the term key material has appeared many times.

I used Google to look for what the term means. Unfortunately few posts explain what it means.

What is the difference between key and key material, if any?

Key material is the “mathematical” key, as opposed to metadata about the key such as the key type, its name in a database, its usage policy, etc.

In the context of key management, and in particular of programming interfaces that manipulate cryptographic keys, the term key can mean multiple things. It can refer to the actual bytes or numbers that are used in cryptographic computations: this is key material. It can also refer to the name (or label, identifier, index, …) of a cryptographic key in a key storage database. It can refer to an object in a system which supports requests such as “encrypt” and “decrypt”, and which may have associated metadata such as the key type (“this is an AES key”) and usage policies (“this key may only be used for AES-GCM, only on Tuesdays and only by users with the Grand Vizir privilege”).

In the context of information security, key material is the aspect of a key that requires especially confidential storage. Typically, the metadata about a key has low sensitivity and can be stored, manipulated and displayed with ordinary precautions. Key material (except for public keys) is more sensitive and requires additional precautions: avoid storing copies in a cache, require additional authentication before viewing or extracting, refuse copying to unencrypted storage, etc.

For example, the top Google hit for “key material” for me right now is “Importing key material in AWS Key Management Service”.

  An AWS KMS customer master key (CMK) is a logical representation of a master key. In addition to the CMK identifiers and other metadata, a CMK contains the key material used to encrypt and decrypt data.

When you create a CMK in AWS, you have a choice of letting AWS generate the key material randomly, or importing your own key material. In either case, you pass metadata such as identifiers as parameters to the key creation request.

Another example: PKCS#11 does not consistently use the term “key material”, but it uses it (without a formal definition) in the context of key objects. For an RSA private key, the key material consists of the (RSA-specific) attributes modulus, public exponent, private exponent, etc. For a secret key, the key material is a single byte array which PKCS#11 calls “key value”. Other key attributes, such as the key type, start and end date, usage policies “derive”, “encrypt”, “verify”, etc. are key metadata, not key material.

If you have a smartcard containing a decryption key, and you know the PIN that allows you to use the smartcard, then you have access to the key, in the sense that you can use the key for its intended purpose. But unless the smartcard is configured to allow extracting the key, you don't have access to the key material itself: only the smartcard has the key material.


Is there a null HMAC? I came up with this question while unit testing a function that includes an HMAC. What is the expected behavior of an HMAC with a well-defined key and a set of data with no elements in it? Is there such a concept as a "null HMAC"?

For example,

byte[] key = RNG.RandomData(32);
byte[] data = { };
byte[] hmac_result = HMAC.HMAC(key, data)

Ignoring the specific language or library I used, is hmac_result well-defined (based on the value of the key or specific HMAC algorithm used), or should the function return an exception?

I'm looking for an answer backed in theory, as I could believe different HMAC implementations could choose to raise an exception on questionable input data.

If the answer depends on the hash function used, what  factors would lead to the result being well-defined or not?

It is well defined.
The hash function has no impact on whether HMAC is defined for a null string text argument. As long as HMAC is defined for a particular hash function, the resulting HMAC of a null string text argument should also be well defined.
The definition of HMAC according to FIPS 190-1 is:
$HMAC(K, text) = H((K_0 \oplus opad)|| H((K_0 \oplus ipad) || text))$
If $text$ is the empty string the right hand side simply collapses to
$H((K_0 \oplus opad)|| H(K_0 \oplus ipad))$
which is well defined.
The hash function used has no impact on the existence of the null HMAC.


Possibility of Chosen Plaintext Attack (CPA) in real-world scenario? In CPA, it is said that the adversaries get ciphertext for the choice of plaintext of adversaries through an encryption oracle. Is this a realistic assumption in real-world, in which the adversaries get ciphertext for the choice of their plaintexts? If so, please provide me with some example scenarios illustrating how adversaries obtain ciphertexts for their plaintexts?

Bruce Schneier foresaw your skepticism and directly answered this question in "Applied Cryptography":

  Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It is not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe someone to encrypt a chosen message. You may not even have to bribe someone; if you give a message to an ambassador, you will probably find that it gets encrypted and sent back to his country for consideration. Many messages have standard beginnings and endings that might be known to the cryptanalyst. Encrypted source code is especially vulnerable because of the regular appearance of keywords: #define, struct, else, return. Encrypted executable code has the same kinds of problems: functions, loop structures, and so on. Known-plaintext attacks (and even chosen-plaintext attacks) were successfully used against both the Germans and the Japanese during World War II. David Kahn's books [794, 795, 796] have historical examples of these kinds of attacks.

Here are the referenced books:

D. Kahn, The Codebreakers: The Story of Secret Writing, New York: Macmillan Publishing Co., 1967.
D. Kahn, Kahn on Codes, New York: Macmillan Publishing Co., 1983.
D. Kahn, Seizing the Enigma, Boston: Houghton Mifflin Co., 1991.


On Linux, does /dev/random unblocking imply that /dev/urandom is seeded? Linux has the familiar problem that /dev/random blocks too much (insisting on being information-theoretically secure), while /dev/urandom doesn't block enough (it will return data before it's been adequately seeded). The new getrandom() system call does the Right Thing, but as of this writing it's not yet universally available in the major distros.

My question is: if I succeed at reading a single byte from /dev/random, does this imply that /dev/urandom is seeded? I've spent some time staring at http://lxr.free-electrons.com/source/drivers/char/random.c but haven't been able to figure this out. Entropy provided by device drivers gets mixed into the input pool, then the input pool feeds separate /dev/random and /dev/urandom output pools, but I can't glean the conditions which trigger transfers from the input pool to the output pools, or (consequently) whether it's possible for /dev/random to be fed while /dev/urandom starves.

I finally untangled what this code is doing.

YES.

The quick version of why this is true is that the first 128 bits of entropy which the system collects get mixed directly into the nonblocking pool, bypassing the input pool. The logic which implements this is part of each of the add_foo_randomness() functions:

 r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;

http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L804
http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L924

And per http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L677, nonblocking_pool.initialized is set when its entropy_total exceeds 128 bits. So by the time anything is available from /dev/random, /dev/urandom has been seeded.

For completeness, here's the rest of the story on how the entropy pools are managed:

All pools, even the nonblocking pool, have entropy estimates that are credited when new entropy is mixed in and debited when entropy is extracted.
As detailed above, the first 128 bits of entropy collected get written and credited to the nonblocking pool; everything thereafter gets written and credited to the input pool.
If the input pool is overflowing (i.e. its entropy estimate is approaching its total size), then this triggers a transfer from the input pool to either the blocking or the nonblocking pool, on an alternating basis. Pools skip their turn if they're already at least 75% full. (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L692)
Reading from /dev/random always triggers a transfer from the input pool to the blocking pool (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L1177). Reading from /dev/urandom triggers a transfer from the input pool to the nonblocking pool only if there has been no such transfer in the past 60 seconds (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L983).
The amount transferred is (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L995):

Typically equal to the amount being read from /dev/{u}random
But at least 64 bits
But not more than the current entropy estimate for the input pool
And not more than that estimate minus 128 bits if the transfer is to the nonblocking pool. (EDIT: I think this is a bug. See http://marc.info/?l=linux-kernel&m=145945873501946&w=2)


What is the meaning of IND-CCA secure under standard model? I notice that in many research papers (viz. "Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption" by Cramer and Shoup) the authors showed that their cryptosystem is IND-CCA secure under standard model. What does it mean? What does an adversary have access to in a challenger-adversary game?

Actually, my aim is to get a clear idea on IND-CCA secure under standard model. I am confused on the statemant like "The given public key cryptosystem is IND-CCA secure under Diffie-Hellman assumption ". Is this statemant means that this particuler cryptosystem is IND-CCA secure under standard model?

Your questions can be split in two:

  What is the meaning of IND-CCA secure? What have an adversary access
  in a challenger-adversary game?

This basically means that the scheme achieves the indistinguishability notion, even if an attacker has access to a decryption oracle. See
Easy explanation of "IND-" security notions? for more detail on this.

  What is the standard model?

This simply means that no additional assumptions are made for proving the security of the scheme. You see, a lot of crypto proofs require additional assumptions. For example, one of the most used is the Random Oracle Model, which assumes the existence of an ideal hash function that guarantees uniformly-random outputs. Proofs in the standard model are therefore considered more desirable.


Does choosing N to be product of safe primes avoid William's p+1 factoring attack on RSA? In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack. Suppose $N = p \cdot q$, where $p$, $q$, $(p-1)/2$ and $(q-1)/2$ are primes. In this case, certainly $p-1$ and $q-1$ are not smooth. They have a very large prime factor. But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors?

In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack.  But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors?

Actually, you're tripping over the various notions of "safe primes" vs "strong primes".

"Safe primes" are generally defined as you said, primes $p$ where $(p-1)/2$ is also prime.  As you note, it guarantees that $p-1$ has a large prime factor; however it gives no guarantee of $p+1$

"Strong primes" are more variously defined; one common one is a prime $p$ where $p-1$ and $p+1$ both have a known large (for example, > 100 bit) prime factor (and sometimes there are more conditions).  With this definition, both $p-1$ and $p+1$ are not smooth.

The ones arguing for more complex RSA key generation methods (the reasoning apparently being that adding complexity always adds to security) generally argue for "strong primes".

On the other hand, it's not at all clear that it adds any real security at all; if your primes $p$ and $q$ are small enough that a random prime has a nontrivial probability to be vulnerable to William's method, then with strong primes of the same size, you have a nontrivial probability of being vulnerable to ECM (and so the sizes of prime you picked as too small).

Here's how it works: William's method works this way: the attacker takes guesses at prime factors; if he guesses all the prime factors of $p+1$ or $q+1$, he can factor (and, other than time, there's no downside to incorrect guesses).  (And, Pollard's method works the same with $p-1$ and $q-1$).

ECM works this way: the attacker picks a pseudocurve, which fixes "small" values $\epsilon_p$ and $\epsilon_q$; then, he takes guesses at prime factors, and if he guesses all the prime factors of $p + \epsilon_p$ or $q + \epsilon_q$, he can factor (and, again, other than time, there's no downside to incorrect guesses). [1]

Each iteration of ECM (that is, a guess at a prime factor) does take more time than the corresponding iteration of William's, but only by a small constant factor; as we rarely have that precise an estimate on the attacker's capability, we can generally ignore this constant factor.

What does this mean?  We can certainly select $p$ to be a strong prime, where $p+1$ has a large prime factor (which is essentially unguessable), and so William's factoring method has no hope.  However, we cannot do the same for $p + \epsilon_p$, as that covers a range around $p$, and we cannot control which pseudocurve the attacker selects.

Hence, selecting strong primes doesn't, in practice, make the factoring any more difficult.

[1]: Real ECM implementations will select a number of pseudocurves, and run them in parallel.  They do this to take advantage of the possibility that one of the curves might have a $p + \epsilon_p$ which is exceptionally smooth; however the above argument holds even if the attacker doesn't do that.


What are the pros/cons of using symmetric crypto vs. hash in a commitment scheme? In a commitment scheme, are there any differences on using a symmetric cipher versus using a hash?

If at the "opening", I have to reveal $r$ (a random number concatenated with the messaged at the time of hashing) and $m$ (the message),  why not reveal the key used for encryption for everybody to decipher the message and so confirm it?

It seems to me that both binding and hiding properties of the commitment would be preserved? Is this so?

Any pros/cons of using one over the other that I'm unable to see?

My preference would be to use hash for this purpose.
Cons of using symmetric cipher include:

Symmetric cipher keys are shorter than hashes (128-256 bits), where as hashes are longer (160-512 bits).
When considering the length of symmetric cipher output, it is commonly short (like 128 bits). This length is often inadequate to protect against birthday attack and other attacks applicable.
In most uses of symmetric keys, related key attacks are of lesser consideration. However, in this scheme, malicious party could try to use related key attack to find key matching slightly altered message and/or different r. The strongest known related key attacks against AES are $2^{189.7}$ (AES-192) and $2^{99.5}$ (AES-256). These attack complexities are from Wikipedia.

I'm not aware of significant benefit symmetric cipher would provide in this context, except that AES is faster to execute on (many) of recent processors than hashes of the SHA family.


Can you help me understand the RSA Broadcast Attack? I am currently working on a broadcast attack on RSA. This is what I have:

17 ciphertexts $C_i$ and corresponding moduli $N_i$ for a single common message $m$.
Public key $e = 17$

The first part (of the exercise) asks me to attack the first 17 ciphers. I programmed it with sage using the CRT. The CRT returns a result $x$ where I applied the 17th root on it, revealing the encrypted message. Everything good so far.

The second part asks me to again recover the message, but the ciphertexts and one modulus got changed. I tried to do the same as in the first part but I don't get a solution.

I already read different articles and books to figure out what the problem is, but I can't find anything :(

Could someone help me with that one?

This is the first one: Part 1
This is the second one: Part 2

Your solution works for Part 1 because (there) for each $i \neq j$ holds  $gcd(N_i,N_j) = 1$. In Part 2 $gcd(N_7, N_{13})$ is not equal to $1$.
$N_{13}$ is a product of two primes ($q = gcd(N_7, N_{13})$ and $p = N_{13}/q$).
Using that information you can recover the secret key $d$ (simply invert $e$ modulo $(p-1)(q-1)$ as during the key generation of RSA) and from that you can recover $m = C_{13}^d (mod\ N_{13})$. We did not use the broadcast attack in this case (I am not sure if you can make it work).


How to deterministically generate a 256 bit ECC key from 128 bits of entropy without a CSPRNG A safe way to generate a 256 bit ECC key from 128 bits of entropy is to use a CSPRNG, according to this answer: https://crypto.stackexchange.com/a/56551/43864

However, it's difficult to find a cross language, cross platform CSPRNG that guarantees to produce the same result across all implementations.

What would be a safe alternative to using a CSPRNG? Ideally the answer would involve just the use of SHA3-256, for which implementations are widely available.

If you need a CSPRNG, there is no safe alternative.

Your assertions that “it's difficult to find a cross language, cross platform CSPRNG” and “SHA3-256, for which implementations are widely available” are contradictory. SHA3 implementations are not very common, whereas every cryptography library provides a CSPRNG. Furthermore, given a hash implementation, it is fairly easy to construct a CSPRNG: use either Hash_DRBG or HMAC_DRBG, both defined by NIST SP 800-09A. Hash_DRBG is slightly faster and HMAC_DRBG is slightly more resistant in case a weakness in the hash algorithm is found.


What are the two parts of SHA1's compression function called? SHA1's compression function has two distinct parts: one where 16 words are expanded into 80 words, and one where the 80 words are used over 80 rounds.  Are there specific names or terms for each of these parts, and if so, what are they?

The part where 16 words are expanded into 80 words is often called message schedule (the name in FIPS 186-4) or message expansion; that's also the key expansion phase of the cipher at the core of the compression function (SHA1's message block is the key of that cipher, due to the Merkle-Damgård + Davies-Meyer structure of SHA-1).

The rest of the compression function would be the compression itself; or the encryption step of the cipher followed by the Davies-Meyer final combination (which, in SHA-1, is five additions modulo $2^{32}$, rather than XOR).


How to convert a Diffie–Hellman key exchange number to work with different encryption algorithms I just read about Diffie–Hellman key exchange and was wondering how the value created from that can be used for any encryption method.  Here is a link of where I read it from.

As the output of the DH key exchange is a number, it has to be converted into big-endian bytes before running it through a hash - say SHA (SHA2 or SHA3) for example, can convert it into a key of the correct length.

If you need variable-length keys, then you can use XOFs, which provide variable length outputs. This cannot increase the entropy of the result of the DH exchange.

If you need multiple keys, HKDF is an option. The DH output is already of enough entropy, so you can skip the HKDF-Extract step, and use the HKDF-Expand to create multiple keys that cannot be derived from each other.


One Time Password generation algorithm to ensure data/transaction integrity? Here is my use case:

A user is trying to transfer money to his friend's account. He enters transaction details on banking website. Bank receives it and then
Bank sends transaction details (receiver name and amount) + One Time Password back to the user (may be through different channel : mobile) so that user can verify the transaction details (this is to ensure transaction integrity. ie., no man-in-the-middle attack) and enter the OTP to confirm the transaction.

What is the threat model?

Man-in-the-middle attack. If an attacker (in middle)  modifies the receiver's bank account details with attacker controlled bank account but shows fake transaction summary, the OTP that sent along with the transaction details should become invalid.

What OTP generation algorithm should I use?

   someOTPgenAlgo(transaction details) = OTP.

Now if the attacker changes the receiver bank account details, he also has to find the matching OTP for that modified transaction details Which should be impossible. How do I achieve this? Is following enough ?

someOTPgenALgo(transaction details + some random key ) = OTP

Thanks a lot. Sorry if the question is naive, I am pretty clueless about this

What you're imagining is impossible to be secure.

Basically what you're describing is a message authentication system where a message is MAC'ed and only the MAC is matched against the actual MAC, but it isn't checked whether the message actually generates this MAC, so an attacker could just fake the transaction details and leave the MAC be and the user would enter the MAC and thus accept the transaction.

Now I'm gonna tell you how many banks here in Germany solved the problem.
This assumes you've issued a card with a chip to every customer and keep track of all cards.
If the user wants to make a transaction, he uses his browser to fill in the data. Then the browser takes him to a page where he is either presented with an optical code (not unlike a QR code, but also using time-based patterns) or some data.
The user has to either scan the code or enter the data, into a physically separate device in which the user plugged the card. The data consists of the amount and the last few digits of the recipients account number. Now the device passes this data to the card which basically just performs HOTP but also incorporates the values for amount and recipient in the calculations. This is done after the user verified the correctness of the transaction on the built-in display. Now he's presented with a short code which he has to enter into the browser. The server confirms the calculations and initiates the transaction.

In a more mathyy way, the OTP would look like this:

$$\text{OTP}=\operatorname{BytesToCode}(\operatorname{HMAC-SHA256}_{\text{Card-Server-Key}}(\text{amount}||\text{recipient}||\text{counter}))$$


How many bits are needed for an LFSR to generate a specific number of sequences? I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so?

That is, what is the number of bits for the initial seed? How can I calculate this number? Can we minimize this number? Should it be a fixed number of bits?

An $n$-bit LFSR with a primitive feedback polynomial will cycle through all $2^n-1$ possible non-zero states. You will need an LFSR to generate $16\times 64 = 1024$ bits. An 11-bit LFSR will cycle through $2^{11} - 1 = 2047$ states and output as many bits, so for your purposes, an 11-bit state is sufficient.

If the feedback polynomial is not primitive, then the period will be unpredictable but not maximal. An example primitive polynomial suitable for use in a maximal-length 11-bit LFSR is $x^{11}+x^9+1$.

It's extremely important to know that an LFSR is not cryptographically secure. An $n$-bit LFSR can be broken after only $n$ bits of keystream are known ($2n$ bits if the feedback polynomial is secret).


DES - Weakness in Sbox In the book "Introduction to Cryptography with Coding Theory ", in the chapter about the Differential Cryptanalysis for Four Rounds for DES algorithm, the authors say:

  There is a weakness in the box $s_{1}$. If we look at the 16 input
  pairs with XOR equal to 0011, we discover that 12 of them have output
  XOR equal to
  011. Of course, we expect on the average that two pairs should yield a given output XOR, so the present case is rather extreme. A little
  variation is to be expected; we’ll see that this large variation makes
  it easy to find the key. There is a similar weakness in $s_{1}$,
  though not quite as extreme. Among the 16 input pairs with XOR equal
  to 1100, there are 8 with output XOR equal to 010.

I've understood the attack in case of a 3-round scenario.
However, it's not clear to me how this particular weakness of sboxes is used in order to attack the DES algorithm in a 4-rounds scenario.
Can you explain to me ?

ps: you find the book writing on google "Introduction to Cryptography with Coding Theory pdf" and taking the first link. The related chapter is 4.3

The attack on 3 rounds is deterministic. It is extended to 4 rounds in a probabilistic manner, which is the normal way of carrying out differential cryptanalysis, see for example Heys' tutorial on linear and differential cryptanalysis which is easy to find online and uses a simple toy cipher to explain these concepts.

Basically, given enough input output pairs, one can use the fact that those differences will statistically dominate. Scan through a set of subkey bit patterns and declare the subkey bit pattern which leads to the most biased output difference distribution as the correct key bit pattern.


Is this RSA / SRA cipher modification secure? I have modified SRA algorithm to suit my problem and I'm wondering if it is still safe to use.

Main question is if RSA Encryption key that contains even number is a safe one way function?

In RSA algorithm: encrypted message is (message)^e1 % N

As far as I understand when I select e1 as even number, multiplicative inverse of e1 mod N won't exists.

If e1 is selected even, the algorithm strength remain unchanged?
If not, what is a different way to public encryption key and ensure everybody that I do not posses decryption key?

If e1 is selected even, the algorithm strength remain unchanged?

Actually, as far as we know, this algorithm relies on a weaker security assumption (and hence is arguably stronger than RSA).

RSA is known to be breakable if you can factor the modulus; however it's possible that there is a way to break RSA without factoring.  We don't know of such a way, but it may exist.

In contrast, it is well known that you can efficiently factor $n$ if you are given a method that takes $x^e \bmod n$, for $e$ even, and recovers a possible $x$ value.  Hence there cannot be a (much) easier way to reconstruct $x$ than factoring $n$

On the other hand:

  what is a different way to public encryption key and ensure everybody that I do not posses decryption key?

What makes you think you can convince anyone that, given $x^e \bmod n$ for even $e$, you cannot find $x$?  If you know the factorization of $n$ (which, assuming that you are the guy that picked $n$, is a reasonable assumption), you can reconstruct a handful of possible $x$ values (no more than $\gcd(p-1, e) \times \gcd(q-1, e)$, which may be as small as 4), one of which is the correct value.

Now, what is the problem you're trying to solve?  If you want to make sure that there is no 'decryption key', why don't you just, say, do a hash of the plaintext.

If there needs to be a 'decryption key' (and just that no one knows it), well, one way is to use one of the larger RSA challenge numbers as a normal RSA modulus (and use a large prime public exponent).  However, we rarely need to do that; what are you trying to accomplish?


Security strength for encryption and authentication (wrapping) of cryptographic keys Let $K$ and $M$ be AES secret keys. The purpose is to wrap $K$ using $M$ to allow $K$ to be used at a later time (see, e.g. NIST SP 800-38F, section 3.1). One method to achieve this goal is to use $M$ with an Authenticated-Encryption algorithm such as AES-CCM or AES-GCM. Another way is Encrypt-then-MAC such as AES-CBC + AES-CMAC with independent keys $M_1$, $M_2$.

The general question is how one must choose the values for the parameters in the above methods in order to preserve the security strength of $K$. To be more specific:

What should be the size of $M$ (relative to the size of $K$)?
Suppose $K$ is an AES-256 key and $M$ is an AES-128 key. Presumably, encrypting $K$ with $M$ will reduce the security strength of $K$ to 128 bits since the complexity of a brute-force attack on the wrapped key is $\mathcal{O}(2^{128})$.
What should be the size of the authentication tag (relative to the size of $K$)?
Now suppose both $K$ and $M$ are AES-256 keys so there shouldn't be an issue with the encryption mentioned in the previous paragraph. However, in all the algorithms mentioned above, the maximal tag size is 128 bits so in all the cases the authentication can be attacked with complexity of $\mathcal{O}(2^{128})$ regardless of the size of $M$.

There is a non-academic kind of answer, that states that there is no better security than "cannot break it", and 128-bit keys are already quite far into that zone, leading to the following recommendation: 128 bits for everything, and be done with it.

A dual version, often encountered in marketing and compliance circles, is that larger keys are always better, and more apt at wooing auditors or customers; thus, you need 256-bit keys everywhere. If you could paint keys, you would make them red, or decorated with shark teeth drawings.

Of course, this cannot please everybody. There are some rational objections related to multi-target attacks: if you want "128-bit security" but you have a set of $2^{30}$ keys to try to attack, and finding any one of them is enough for the attacker to "win", then you need 158-bit keys to reach your specific level.

For that kind of analysis, context matters a lot. For instance, if you have one wrapping key $M$, used to protect $2^{30}$ keys $K$, and you want 128-bit security, then $M$ must live in a space of size at least $2^{158}$. Conversely, if you have a single key $K$ but it has been wrapped with $2^{30}$ distinct keys $M$, then the attacker only has to break on of the wrapping keys to obtain $K$; in that situation, $M$ should have length 158 bits or more, while $K$ may remain at 128 bits.

Therefore, there is no fully defined clearcut context-free answer.

The authentication tag is not about confidentiality, but integrity. Integrity matters, notably because in most contexts where attackers can observe confidential data, then can also change it. For instance, over the Internet as it is practiced today, to eavesdrop on a link, you must be physically connected to that link, or arrange to make the link pass through hardware you control (e.g. you run your own WiFi access point, or you poison the DNS to make target names resolve to the IP address of your own server).

There again, context matters a lot, as well as application conditions. Suppose, for instance, that wrapping uses AES/GCM with a 256-bit wrapping key $M$. An attacker could try to find the key through exhaustive search, which is going to be expensive ($2^{255}$ tries on average). On the other hand, the attacker may "just" want to make a forgery (feeding the recipient with a fake encrypted key); with a 128-bit authentication tag, the attacker has probability $2^{-128}$ of succeeding at each attempt. In that sense, the authentication tag offers only 128-bit security.

But the situation is quite different! In the exhaustive search on the key, each "try" correspond to the spending of some computational power by the attacker on his own machines. This attack is not limited by anything else than the attacker's budget. On the other hand, each "try" on a forgery attempt implies talking to the recipient, to see if the altered wrapped key will still be accepted. That attack is then running on the defender's budget, which is usually a lot less than the attacker's. Moreover, it's much less discreet: after a few billions of failed attempts, the defender may catch up that something's running afoul.

Thus, it would be wrong to equate "128-bit symmetric key security" with "128-bit authentication tag security". They don't really live in the same world.


Proving the knowlege of e-th root in an non-interactive way Just like in this question: Protocol for proof of knowledge of $l$-th root

I want to prove that for $u^e = w$ I know $u$ without revealing it.
Three other requirements are:

e is small (65537)
The proof has to be non-interactive
The proof should be as efficient as possible (not several megabytes)

EDIT

So the best solution I have come up so far is to use the Guillou-Quisquater protocol together with a Fiat-Shamir heuristic to make it non-interactive.
This would work the following way:

The prover

Step 1.

The prover generates 10 numbers $T1,T2 ... T10$ where each number is calculated using the following formula and where $r$ is a secure random number:

$T = r^e$

Step 2.

calculate a hash $m' = h(T1||T2 ... T10||m)$ where $m$ is the message or challenge the prover wants to sign.

Note that if the hash contains 2 successive zero bytes or a zero byte followed by a byte of the value 1 of which the probability is low the prover has to go back to step 1 and generate new T numbers

Step 3.

The prover selects the 160 leading bits of the hash and splits them into 10 pairs of 16 bits numbers $d1,d2 .. d10$. Then for each of those 16 bits numbers calculates $t1,t2 ... t10$ such that

$t = u^d r$

Note that in this case to calculate $t1$ the prover will use the random number $r$ that we used to calculate $T1$, for $t2$ the number $r$ used in $T2$ and so on.

Step 4.

The prover publishes the signed message $m$, the hash $m'$ and the numbers $t1,t2 ... t10$

The verifier

Step 1.

The verifier starts by splitting the leading 160 bits of the $m'$ hash into the 16 bits number $d1,d2 .. d10$ then calculate the values $T1,T2 ... T10$ from it:

$T = t^e w^{-d}$

Step 2.

Using the T values calculated in the previous step verify that $m' = h(T1||T2 ... T10||m)$ if this verification holds the proof is correct.

I do believe that doing this with 160 bits (proof with ten 16 bits numbers) is very secure, but what about doing it with 80, 96 or 128 bits?
Is there another way to improve this implementation or is there an error in it?

Bad news is that what you ask for is impossible to achieve with the proposed Guillou-Quisquater (GQ) identification protocol. Unfortunately, $\Sigma$-protocols for group-homomorphisms are not efficient in groups of unknown order.

1) Efficiency Limitations of $\Sigma$-protocols in groups of unknown order

Informally speaking $\Sigma$-protocols in groups of unknown order for group-homomorphism $\phi(\cdot)$ have large knowledge error. This was shown by Bangerter et al. in case of generic-groups (see Theorem 6. in the linked paper). More specifically, in your specific scenario, the knowledge error of the GQ-protocol is $1/e$, where $e$ is your exponent (prime in your case). Hence, to achieve reasonable knowledge error, you need to repeat the protocol several times which would sacrifice the succinctness of your proof, given that supposedly your RSA group elements are already large (few thousand bits, I suppose).

For instance, let's take your setting: $e=65537\approx2^{16}$. Assuming you want to achieve $128$-bit security you need to repeat the GQ-protocol $8$ times. If you have $2048$-bit length for the modulus, then the proof size is $2\cdot8\cdot2048$ bit, which is $4.096$ kilobytes.

2) Circumventing the limitations by a trapdoor-free CRS

Efficiency limitations of $\Sigma$-protocols in groups of unknown order can be circumvented by applying a trapdoor-free CRS. In this case it is enough to repeat the $\Sigma$-protocol only once as it was shown by Boneh et al. Namely, the CRS would contain only a single group element whose DLOG should be not known to anyone. The downside of this approach is that it assumes a non-standard assumption, i.e. the Adaptive Root (AR) assumption. As of today we know quite little about AR. For example, it is not known yet whether AR is equivalent to Factoring in the generic ring model or not. However, we do know that AR holds in the generic group model, although this is not a decisive result as the generic group model is quite a restricted computational model.

3) Making $\Sigma$-protocols non-interactive

There are standard ways to implement the FS-heuristic. However, there are some pitfalls you need to have in mind. In the weak-FS (wFS) the challenge is computed as the hash of the commitment (first message of the prover). In the strong-FS (sFS) the challenge is obtained by hashing both the statement and the commitment. It was shown by Bernhard et al. that a protocol implemented with the wFS becomes insecure if a malicious prover can adaptively choose her statements she wants to prove. So to be on the safe side always implement FS with the strong variant.

TL,DR: either you have an inefficient protocol or you need to assume a non-standard RSA assumption, called the Adaptive Root assumption.


Does information theoretical security definition imply DDH, RSA, QR does not hold? Assuming we are in the information theoretical setting, whereby there is no bound on the computational power of an adversary. Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary?

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary?

That is correct; a computationally unbounded adversary could trivially solve any of these problems.  For example, to solve the DDH problem ("given, $g, g^x, g^y, g^z$, does $g^{xy} = g^z$?) a computationally unbounded adversary could go through all possible values $x, y, z$ (between $0$ and $p-1$), and check if they match the $g^x, g^y, g^z$ values they were given, and if so, does $g^{xy} = g^z$.  This sort of solution works for all the other problems you mentioned.

Note: there are computationally far easier ways to solve this problem; this is just the generic strategy that works against any computationally bounded problem.


AES key and block size I am trying to understand $AES$ and I wondered what happens in the case of a $128$ bit block size and a $256$ bit key.
All documents I read about $AES$ told me the key expansions algorithm for $128$ bit keys and $128$ bit blocks.
But I have a $256$ bit key ($8$ words) and $128$ bit block ($4$ words) and I am not sure how the key expansion works now.
Should I expand it how usual but instead beginning in the second round beginning in the third round?
Like this graphic shows:

Well, as SEJPM and Mok-Kong Shen pointed out, it's described in FIPS 197, but let's explain it in details:

Here's the Key Expansion algorithm pseudo-code from FIPS 197:

Where

$Nk$ is the number of $32$-bit words that composed the key
$Nr$ is the number of rounds
$Nb$ is the number of columns in the state block (which is always $4$).
$word$ is a $32$-bit word (can be seen as an array of $4$ bytes).
$w$ denotes a $4$-byte word array where the number of elements is equal to $Nr + 1$ (because AES uses a different key at each round)

For a $256$-bit key, we have $Nk = 8$ and $Nr = 14$ according to FIPS 197.

When you are asking

  Should I expand it how usual but instead beginning in the second
  round beginning in the third round?

Don't you mean the fourth round? Let me explain.

As you can see with the above pseudo-code, the first loop just copy the secret key at the beginning of the array $w$. Then, we get into the second loop to compute rounds key which are derived from the given one.

So for a $128$-bit key, you start to derive round keys as soon as $i=4$ but only when $i=8$ for a $256$-bit key (because the key is longer).

Also, as mentionned in FIPS 197, note that the routine isn't the same regarding to the key length (which is $Nk$) because there are arithmetic conditions between $i$ and $Nk$ to get into different branches of the algorithm.
For example, only $256$-bit keys will satisfy the condition else if (Nk  >6 and i mod Nk = 4).

Hope it's more clear now.


Corruption bound of MPC when n>2 In the book titled "Secure Multiparty Computation and Secret Sharing" stated that MPC protocol is not secure when the adversary $t>n/2$. This was proved by using a 2 party protocol, but I can't understand why the same applies when $n<2$.

For example, when $n=6$ and $t=3$, the adversary might know the multiplication of the output for the 3 honest players, but as long as their individual inputs are not known, doesn't that consider as secure?
Could someone please help me with this problem?

First, it's important to understand that MPC is not possible for $t \geq n/2$ in the information-theoretic setting (where the adversary is computationally unbounded). In the computational setting, where the adversary is polynomial-time, it is possible to achieve MPC under cryptographic hardness assumptions.

Regarding your specific question, I assume you are referring to a case where we have a polynomial of degree $t$ to share a secret. Indeed, it is possible to share a secret securely for any $t\leq n$. However, the problem is that you need to be able to process that secret. So, if $t=3$ and $n=6$ and you have a degree-3 polynomial, then the first step of multiplication yields a polynomial of degree-6. In order to reconstruct the values, 7 points are needed for a degree-6 polynomial. However, there are only 6 parties and only 6 points. So, this cannot be done.

Of course, the above just says why this approach doesn't work. However, it's possible to prove that no approach can work, and I believe that this also appears in the book.


Storing Parameters In Argon2 Hash As Potential Security Issue? I'm really trying to make sure that I follow best practices when it comes to password storage, and after some looking around for a good algorithm, I found that Argon2 was the "next big thing". I've been testing it out within VB.Net using the NuGet package provided by Liphsoft (Liphsoft.Crypto.Argon2).

By default, it looks like the parameters for the hash algorithm are stored in the hash itself. I understand (or at least I think I do) that this is suppose to make it easier to migrate it to a new hash if you ever decide to change the parameters.

My question is, does it make it less secure by supplying the hash algorithm's parameters in the hash itself? I'm currently thinking of just trimming out the information and just hiding the parameter values within code so that if someone gets a hold of the hash, they can't immediately see that "Oh, they're using Argon2 with these specific parameters." Should I even be concerned about that?

Any feedback is greatly appreciated. Thank you!

I also looked at this question before posting: Argon2 output length and parameter storage?

First, following the "next big thing" is not generally a good idea in the world of cryptography. You should strongly prefer battle-tested code and algorithms over new ones. In this particular case, consensus is mostly that Argon2 is highly unlikely to fall victim to attacks that make it worse in practice than scrypt, bcrypt, or PBKDF2, so you're not necessarily wrong to pick Argon2; just consider that your instincts should drive you toward more well-established, conservative choices when it comes to cryptography. You should also strongly prefer off-the-shelf algorithms and implementations over versions you've made custom modifications to; you are orders of magnitude more likely to make things weaker through a misunderstanding or a through a bug than you are to sufficiently address a real weakness. Think of it this way: if your concerns are based on something real, and they're as easy to address as you believe, cryptographers and authors of cryptographic libraries would already handle this for you.

Second, the parameters are required in order to recalculate the hash. If you specify different hardness constraints when initially hashing the password, you get out a different result. It follows that if you don't know those parameters when trying to verify the hash, you would have to try every combination of those parameters until you get lucky enough to stumble upon the result
If you have these parameters stored directly in your code, you technically don't need to keep them alongside the hash itself. However, these parameters should not be set in stone: they should be continually increased as memory gets cheaper and hardware gets faster. Some libraries let you do this dynamically by "calibrating" the computation the first time you instantiate the library, such that it uses some fraction of available memory and takes (for instance) 0.1s of CPU time.

In exchange for losing this flexibility, you gain a relatively minor benefit in security. If you're using Argon2 with reasonable costs (> 0.1s), it should take an attacker an impractical amount of time to recover all but the most trivial of passwords; running through the list of the most common 1,000 passwords against a database of 10,000 users would take more than ten days of CPU-time, and even here you're better off mitigating this by preventing users from using passwords from these lists.

Still there's an undeniable, if small benefit. Can we get that benefit without the downsides? Yes. Rather than hide the cost parameters (which don't constitute much in the way of entropy), you're better off computing an HMAC of the password before sending it to Argon2. By using a secret key and computing an HMAC first, you get to keep flexibility for your cost variables, but you also prevent an attacker from having any ability to test passwords unless they've also acquired the HMAC secret, which has far more entropy than do your cost parameters.

Edit: One other thing to note is that your suggestion doesn't really defend as much as you think it would. As I point out in my comment to @LuisCabrillo's answer, the sum of these things adds up to perhaps 16 bits of entropy. Against a smart attacker who creates an account on your site with a password they already know, you've done very little to stop them now: they know the password and the matching hash, so just need to run through each possibility once until they determine your algorithm and cost factors. Then they can attack your password database per usual.


How to quickly detect incorrect password in encrypted file without compromising security? I am developing a software to encrypt/decrypt files/streams using symmetrical encryption algorithm. During encryption phase data wil be compressed and encrypted.

When decrypting data, I want to be able to check whether supplied password is correct. For that purpose encrypted file contains header (which I would like to keep as small as possible), where some signature derived from password is going to be stored.

There are several condition that must be met:

A. Password checking must be as fast as possible and it should not require excessive CPU/memory resources. Risk of using weak/guessable password is NOT present as we declare in advance that only secure, long, random passwords are going to be used for encryption.

B. If we encrypt the same plaintext file twice with the same password, the header and encrypted text must not be the same.

I assume that a theoretical attacker has complete source code of my software. The one and only thing that the attacker does NOT have is password.
My question is - what kind of signature should I use so the security is not compromised?

Here are possible options that I was thinking about and my commentary to them:

Password hash (SHA, MD5, etc.). Probably not a good idea because of risk of precomputed dictionary attacks.
Hash of the salted password. Salt is going to be generated using pseudo-random number generator (PRNG). The initial seed of the PRNG is derived from the password. I suspect this won't help at all since we know that the attacker has access to the source code - so the attacker will always be able to generate salt for the given password and, hence, generate the hash. Then the attacker can write proprietary software which will be able to perform dictionary attack agains files encrypted with my software using our own hash-generating algorithm.
Using key derivation function (KDF), like PBKDF2. This does not meet condition A, because all good key derivation functions should deliberately use excessive CPU/memory resources.
Using HMAC. I am not very good at understanding HMAC, but I think that in this case HMAC would not be used for what it was designed. I don't need to verify integrity of the password AND the encrypted file (or, in cryptographical terms, key and the message). I just need to verify whether the password is correct.
Other options?

I would be grateful if someone who understands cryptography better than me could give me some ideas or comments.

This is a perfect job for a Key Based Key Derivation Function or KBKDF. Generate two keys from the input (salt and password). One is stored directly in front of the ciphertext and one is used as encryption key. Because the KBKDF is based on PRF it cannot be reverted, so the keys are not related as far as an attacker is concerned.

Currently the best KDF is arguably HKDF. It contains both an extract functionality (to handle long passwords) and can take a salt and OtherInfo structure as input. The OtherInfo can be used for inserting an ASCII string identifying the key, e.g. "KCV" (key check value) and "ENC" (encryption). It is possible to derive the IV by using "IV" of course, in case the salt is already random for each encryption. You may want to perform only one extract and three expands of HKDF.

I would strongly recommend authenticated encryption. Make sure you use a fresh salt for each encryption procedure.


Oblivious Decryption: Decrypting with a private key, without knowing the message I’m trying to devise a protocol, complimentary to a private-set-intersection, involving three parties, namely Alice, Bob and Charlie.

Alice has a public and a private key. And receives website logs from Charlie.

Charlie runs a website, and he sends his website logs to Alice, encrypting the user-ids using Alice’s public key. Let’s say they are using RSA with padding for each log entry, this way the same user-id always looks random when encrypted.

Bob is managing a small part of Charlie’s website. Charlie has agreed to forward a related portion of the logs to Bob. But it’s directly sampled from the same logs Alice got, so they carry the user-ids encrypted with Alice’s public key.

Naturally, Bob doesn’t have Alice’s private key, and wants to learn the user-ids that visited his section. He can ask Alice to decrypt the user-ids he has, however he doesn’t want to give Alice the information about the users he’s interested in.

Is it possible to devise a protocol where Alice decrypts the messages encrypted by her public key, without really knowing what the message was. Hence the name Oblivious Decryption...

So, I have thought of the commutative property of RSA. If Bob had a private and public key both secret to himself, before sending the message to Alice he might have encrypted and  then decrypt what Alice has decrypted, getting access to the user-id himself only. However for Bob to be able to create such a key-pair he needs to know the prime factors of the modulus.

Is there a way, this can be achieved. And If not can we prove that this is not possible?

This can be done by exploiting the homomorphic property of RSA.  Let's say Alice's key is $(e,N,d)$ where $e$ is the public exponent, $N$ the modulus, and $d$ the private exponent.

To decrypt $x$, Bob samples $r$ randomly from $\{1,\cdots,N\}$ and computes $xr^e\mod N$ and sends it to Alice.  Alice computes $(xr^e)^d=x^dr\mod N$ and sends it back to Bob.  Bob multiplies by $r^{-1}$ to extract $x^d$.

Note that Alice does not know $r$ and thus cannot determine $x^d$ from $x^dr$.  This does lead to at least one vulnerability: Bob can send Alice whatever he likes.  In particular, he could ask for the decryptions of other private messages to Alice that he somehow acquired.


Does the key schedule function need to be a one-way function? For some key schedule $e_n(e_{n-1}(k))$ (where $e_{n-1}(k)$ is the result of the previous round) , does $e$ need to be a one-way function?

In the case of DES or Rijndael the key schedule doesn't really look like one, as the adversary only has to reverse the operations to get the input.

My question is this:

In the case of the well-studied Rijndael,

What are the implications of replacing the iterated schedule $e_n()$ with a one-way function $f$?

My guess is it would increase linearity, leading to a weak cipher. So,

What if we added a one-way component to $e$ such that

$$e(x) \leftarrow s( r (f (x))) $$

where $s()$ and $r()$ are the s-box and bit-shift functions respectively.

Note: I ask about Rijndael where I really mean any block cipher that is secure, eg. Rijndael but I'm not exactly sure how to phrase that.

As fgrieu already pointed out, using a OWF in the way you describe would make the key schedule not efficiently invertible (or even not invertible at all), meaning you would need more memory/chip space to store the user-input key in order to efficiently encrypt more than one block.

In terms of other implications, if the key-state update function $e_n(\cdot)$ is non-surjective then the later round keys will have less entropy than the user-input key, and hence may be guessed with less effort than with the current AES key schedule.  This could make the last rounds easier to peel off.

However, if $e_n(\cdot)$ is such that every output bit is a high degree non-linear function of every input bit, then any such loss of entropy would likely be very difficult to exploit, and also would likely make related key and biclique attacks more difficult.

You should also be aware that OWFs can be used in the key schedule in a different way than you describe -- i.e. as round key extractors instead of as key-state update functions.  So you might have a permutation (perhaps even a linear one) to update the key-state between each round, but then derive each round key from the key-state using a OWF.  As a concrete (but slow) example, your key-state update function might be to add 1 (or some other constant) to the user-input key between each round, and then extract the current round key from that by hashing the key-state with a cryptographically secure hash function like SHA-256.  As a much faster example, Serpent uses a linear key-state update function, and non-linear round-key extractors (though in that case they are non-linear permutations using the Serpent s-boxes instead of OWFs).


Is GCM mode of authenticated encryption quantum secure? Regarding post-quantum symmetric cryptography, it has been recommended to move to AES-256 or similar ciphers with 256-bit keys. How is authenticated encryption affected? Is AES-256-GCM considered quantum-safe? what are the other alternatives for post-quantum authenticated encryption?

Is AES-256-GCM considered quantum-safe?

For most common scenarios, yes.

Actually, it depends on your attack model.  If your attack model is that the attacker is allowed to perform entangled queries on your GCM implementation, and return entangled responses, then, no, GCM is known not to be secure against this model; the attacker can use Grover's algorithm on the decryption Oracle to find a second valid ciphertext/tag with a previous seen nonce with $O(2^{64})$ work.

On the other hand, the attack model is rarely appropriate.  Entanglement is quite delicate, and to make this attack model work, the decryption oracle would need to be implemented using quantum error correction.  Typically, implementations don't help out the adversary to that extent, and hence it would need to be implemented as a part of the quantum computer (so that the adversary can implement quantum error correction within the oracle).  About the only way this would be practical would be if you were attacking a white-box GCM implementation (so you couldn't trivially examine the implementation and extract the key).

In the standard scenario, where the attacker is allowed to make conventional queries to the oracle, and get the standard response, the standard proof of GCM applies; unless they can distinguish AES from a random permutation, they cannot generate a valid ciphertext/tag pair with nontrivial probability; using a 256 bit AES key means that Grover's algorithm would take $O(2^{128})$ time for this, which is generally considered infeasible.