Subverting the key generation step in RSA public key cryptography I am interested in the ways an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who interact with the owner, are left unaware that something is going on. I assume that the owner of the key does not have the ability to detect subtle bugs in the key-generation implementation, but that the key will be used for encryption and decryption with standard implementations outside the subverter's control.

My first idea was that a subverted primality test might accept, instead of rejecting, numbers of the form P1*P2 where P1 is a fixed prime known only to the subverter, and P2 a random prime. The owner of the key would end up with a modulus of the form P1*P2*Q, which the rest of the world would not necessarily be able to distinguish from a semiprime number. However, according to this answer, the owner of the key may find themselves unable to crack their own public key, that is, to read messages intended for them. I understand the linked answer to mean that the prime decomposition of the modulus is necessary to read encrypted messages, and in effect, the owner of the key would not have this decomposition. The owner of the key would only have P1*P2 on the one hand and Q on the other hand.
Another idea would be that the prime generation implementation might be subverted in a way such that there exist a million primes P1,P2, …, P1000000 that the implementation is more likely to generate than the others (say, each has probability 1/2000000 to be generated each time). This would, in effect, amount to a private Mining your Ps and your Qs attack(*), reserved for the subverter (who would know the values of P1, …, P1000000) but, as long as the subverted implementation remained in moderate use, unlikely to be detected by anyone else (owner of the key and rest of the world).

(*) It occurs to me after having written the question that the subverter can keep its game preserve more private if the subverted implementation never pairs a prime from the list P1,P2, …, P1000000 with another prime from the list. This doesn't prevent them to be discovered one by one using the original “Mining your Ps and your Qs” attack, but at least they do not unravel all at the same time.

My question is: can 1. be made to work using, say, some sort of pseudoprime instead of a composite number to maliciously accept as prime? Is there a reason why 2. might not work in practice?

These are two questions but they are related in that they are relevant to the same purpose

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$.  The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is $(p-1)(q-1)$. But in reality, if $p$ is not prime, the actual totient must be smaller, because the totient of $p$ is strictly less than $p-1$ (and similarly for $q$). So the generator will not be working with the correct totient, and cannot compute a correct secret key. (Technically, all of this assumes that $p$ and $q$ are actually coprime, which the generator can check for itself.)

As for idea 2, it essentially has been implemented in practice, in the sense that several key-generation algorithms having that flaw were deployed and used for years without suspicion. The simplest explanation is that these were accidental rather than malicious flaws, but the same kind of flaw could be deployed maliciously as well.

UPDATE: the "problem" with subversion of type 2 is that the public can discover that many keys share a common prime, and thus learn of the subversion. Here is another kind of subversion that does not have the problem of shared primes, but does allow the subverter to factor the generated modulus. The subverter designs the generation algorithm to choose a prime that is close to the output of a PRF applied to (say) the email address and/or time of day -- some (quasi-)public information that will be associated with the key, which will be unique every time the generator is run.  So the chosen primes will likely never be the same, but the subverter can find them easily using the secret key of the PRF. The only catch is that the PRF secret key must also be hidden in the generator algorithm. A suspicious user might be able to discover the subversion by inspection or by running the algorithm in controlled ways, but not by discovering shared primes across keys (because they do not exist).


How to use the Extended Euclidean algorithm to invert a finite field element? I was doing some practice on cryptography (I'm new to this topic) and was wondering what the following question even means or what it is asking me to find. I do know how to do Extended Euclidean algorithm, but I have no idea how to apply it to this problem. I do not need the answer to it but I would appreciate someone explaining to me what the question is asking for.

  Calculate by hand, using the Extended Euclidean algorithm:
  $(\mathtt{0x35})^{-1}$ in $\operatorname{GF}(2^8)$ with the irreducible polynomial $m(x) = (\mathtt{0x11B})$. (2 marks)

  (Note: this is the finite field used by AES, ‘$\mathtt{0x}$’ denotes the hexadecimal representation.)

To answer this question, we need to understand what is meant by:

  the field $\operatorname{GF}(2^8)$ generated by the irreducible polynomial $m(x) = (\mathtt{0x11B})$.

and I'll try a gentle, progressive introduction to that.

One simple way to see this field is that as the set of the 256 octets $\{\mathtt{0x00},\mathtt{0x01},\dots,\mathtt{0xFF}\}$; with additive law bitwise XOR $\oplus\;$; and multiplicative law the commutative operation $*$ defined in either one of the following ways:

By having $\mathtt{0x01}$ as the neutral element, $\mathtt{0x02}*\mathtt{0x80}=\mathtt{0x1B}\;$ (that's the given $\mathtt{0x11B}$ truncated to its low-order 8 bits), and the more intuitive $\mathtt{0x02}*\mathtt{0x02}=\mathtt{0x04}\;$, $\mathtt{0x02}*\mathtt{0x04}=\mathtt{0x08}\;$, $\mathtt{0x02}*\mathtt{0x08}=\mathtt{0x10}\;$, $\mathtt{0x02}*\mathtt{0x10}=\mathtt{0x20}\;$, $\mathtt{0x02}*\mathtt{0x20}=\mathtt{0x40}\;$, $\mathtt{0x02}*\mathtt{0x40}=\mathtt{0x80}\;$. These and the properties of $*$ (commutativity, associativity, distributivity with respect to $\oplus\;$) are enough to fully define $*$. The constant $\mathtt{0x1B}$ is such that every element except $\mathtt{0x00}$ (the neutral element of $\oplus\;$) has a multiplicative inverse, which can be found by inspection of the multiplication table (building this table, and deriving an algorithm which computes the product of two arbitrary elements without this table and at most 8 iterations, is left as a recommended exercise to the reader). This gives the result asked in the question, but not by the method thought, and is impractical by hand.
Alternatively, we can define a commutative ring $(\mathbb N,\oplus,\otimes)$ where $\oplus$ is bitwise XOR, and $\otimes$ (sometime called carry-less multiplication) is the same as common multiplication when either argument is a power of two, and the associativity of $\otimes$ with respect to $\oplus$ is used to define the other cases. For example $\mathtt{0xDB}\otimes\mathtt{0x42}$ $=\mathtt{0xDB}\otimes(\mathtt{0x40}\oplus\mathtt{0x02})$ $=(\mathtt{0xDB}\otimes\mathtt{0x40})\oplus(\mathtt{0xDB}\otimes\mathtt{0x02})$ $=\mathtt{0x36C0}\oplus\mathtt{0x1B6}$ $=\mathtt{0x3776}$. We can define an analog to Euclidean division in $(\mathbb N,\oplus,\otimes)$, giving quotient $q$ and rest $r$ from dividend $d$ and non-zero divisor $n$, such that $d=(q\otimes n)\oplus r$, and the bit size of $r$ is less than the bit size of $n$. That allows us to define an analog in $(\mathbb N,\oplus,\otimes)$ of modular reduction in the ring $(\mathbb Z,+,\times)$. Our operation $*$ in $\operatorname{GF}(2^8)$ is $\otimes$, followed by reduction modulo $m=\mathtt{0x11B}$. That constant is such that $(\operatorname{GF}(2^8),\oplus,*)$ is a field, much like $(\mathbb Z_n,+,\times)$ is a field when $n$ is prime. Now we can apply the Extended Euclidean algorithm and answer the question by the method asked. We do as for computing an inverse modulo a positive integer, but use $\oplus$ instead of addition and subtraction, $\otimes$ instead of multiplication, and the analog of Euclidean division in $(\mathbb N,\oplus,\otimes)$.

An equivalent way to see the field $\operatorname{GF}(2^8)$ is as the set of the 256 polynomials with one variable, of degree less than 8, having bit coefficients per Boolean algebra; additive law the addition of polynomials; and multiplicative law the multiplication of polynomials followed by modular polynomial reduction of the product by the polynomial $m(x)=x^8+x^4+x^3+x+1$ (corresponding to bits in $\mathtt{0x11B}\;$). A necessary and sufficient condition for every element except zero being invertible, is that $m(x)$ is irreducible, which holds. Now we can apply the Extended Euclidean algorithm and answer the question by the method asked. We do as for computing an inverse modulo a positive integer, but use $m(x)$ as the modulus, and division of polynomials with bit coefficients instead of Euclidean division.


Are there any other applications of machine learning to cryptography? I've checked a bunch of articles about machine learning and cryptography and derived from them three distinct possibilities:

Use ML to approximate a cipher as a function. Article "Neuro-Cryptanalysis of DES and 3DES" shows a way to approximate DES using only $2^{10}$ plaintext-ciphertext pairs with average error of 10% of bits in the test sample.

Although this result sounds pretty good, considering linear cryptanalysis needs $2^{43}$ text pairs to fully determine the cipher, this article doesn't have many references, so I have some doubts about importance of achieved result. And the chosen method has a considerable error of 10% which can happen on any bit of deciphered text. In other words, it is possible that every bit in deciphered text will be wrong, although pretty unlikely.
Side-channel attacks. This looks more promising, especially power analysis attacks, there are some very interesting articles where ML is used on power signal.
Machine learning on encrypted data. This one needs homomorphic encryption, as I see it, there is a bunch of articles too.

Are there any other applications of machine learning to cryptography? Are there any possible ML applications that can assist a cryptographer in their task?

(I can post links to articles if anyone is interested.)

While your question is somewhat opinion-based and it depends on how far we stretch cryptography, my answer (having some experience in both fields) would be no, there are no applications of Machine Learning in cryptography.

Why?

Well, for starters, machine learning is made to find some regularities in input data and to produce output data from it. This requires a lot of inputs and well defined function that will define if we are doing good or bad. And they operate on floating-point numbers (they might lose some accuracy with result).

Cryptography and cryptographic functions are designed to be very random-looking and to be very complex. They are designed so that there are no visible structures in output data. They are nearly always defined on integers.

So cryptographic data can't be easily mapped onto machine learning data, because for machine learning 1.0 and 1.5 are close, but in cryptographic sense they aren't close, they are just numbers. And for machine learning representing data in meaningful way is very important to get meaningful results. This is nearly impossible with inputs and outputs from most cryptosystems.

I will ignore your first point, as this probably deserves investigation into it on it's own (but I think most of us fail to believe that those results are correct - it might be worth asking question about that paper specifi).

  Side-channel attacks. This looks more promising, especially power analysis attacks, there are some very interesting articles where ML is used on power signal.

Now depends if we call that cryptography. I'd say that Machine Learning in this case is used to extract data. We can represent power-consumption as floats, and we can represent results as confidence in key bit. However, I do not agree that this is strictly cryptography, as this isn't really meaningful way to connect Machine Learning to cryptosystem. This is barely used as way to analyze data. For me it's like saying that medicine and cryptography are related fields, because cryptosystems are used to secure medical records.

  Machine learning on encrypted data. This one needs homomorphic encryption, as I see it, there is a bunch of articles too.

This is something I don't understand. Homomorphic encryption allows us to modify encrypted data to some extent and Machine Learning allows us to find regularities in data. Just because both were used, I won't say that both are related.

Summary

Cryptosystems are used as means to operate on data (including encryption and verifying). This is merely usage of cryptography. Cryptography is art of designing and verifying security of such systems.
Machine Learning is used to analyze data and produce some action based on data. This is again just usage of Machine Learning, not "machine learning in cryptography".
So to clarify: Machine Learning is applicable when we have input which we can efficiently map into ML and we want to act upon input. This applies to any data which we can efficiently map into ML. Cryptographic functions can't be efficiently mapped into Machine Learning input, so Machine Learning is of no special use in cryptography (but it can analyze some non-cryptographic data even when evaluating cryptographic designs).

So I guess answer can also be: There are infinitely many applications of machine learning in cryptography, just as any other field.


Are interactive proofs more secure their non-interactive counterpart? Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure?

Are there any new attack vectors that get introduced?

Is there any reason to use the interactive version over the non-interative version? Aside from both parties always being online

Are there any complexity theoretic comments that can be made about the distinction between interactive and non-interactive proofs?

When turning an interactive ZK proof into a non-interactive zero-knowledge argument with the Fiat-Shamir transform, the following security issues must be taken into consideration:

Even if the interactive ZK proof is a proof system (meaning that it is statistically sound), the Fiat-Shamir transform produces an argument system (where soundness is only computational). In concrete terms, that means that you must in general increase the soundness error of the interactive protocol before making it non interactive. Consider for example an interactive protocol where a cheater has probability at most $2^{-40}$ of producing a convincing proof for an incorrect statement: this can be a perfectly fine security guarantee in many real-world situation. But as soon as you turn this protocol into a NIZK with Fiat-Shamir, the guarantee changes: now, you are only guaranteed that forging an incorrect proofs will take $2^{40}$ computation steps for the malicious prover. But performing $2^{40}$ operations is trivial on any standard computer, hence the scheme would be completely broken. Put differently, a NIZK will in general need to be less efficient than the corresponding interactive ZK proof, in terms of communication and computation, to achieve a sufficient security level.
Many interactive ZK proofs naturally satisfy non-transferability: if a prover interacts with a verifier and demonstrates that he knows some value, or that some statement is true, the verifier, even after seeing the proof from the prover, cannot in turn convince another party that he knows the value/that the statement is true. This is because the verifier can at best show the transcript to this other party, but by the zero-knowledge property of the protocol, this transcript could in fact have been generated easily without knowing whether the proof is true (put otherwise: if you know the challenge in advance, it's easy to forge a proof. How could the other party know that the verifier had not colluded with the prover and given him the challenge in advance?). In contrast, NIZKs are naturally transferable, since they are publicly verifiable. Sometimes, non-transferability is crucial: suppose you solve a million-dollar problem, and want to prove to someone that you've found the solution. Using a zero-knowledge proof allows you to convince him that you know the solution without revealing it; but you still do not want this person to be able to use your zero-knowledge proof to convince someone else that he knows the solution, since he could then just use your proof to claim the million dollar prize!
As pointed out by Martin Kromm, the Fiat-Shamir transform is not proven secure in the standard model under any known security assumption. It is only proven secure in an idealized model, meaning that the security guarantees it gives are, at best, heuristic indications that breaking it requires doing "something non trivial" with the underlying hash function. Concretely, NIZKs obtained with the Fiat-Shamir transform have never been broken as of today and seem relatively safe, but we have no proof of that, so one should be cautious.

As for the reasons to use interactive proofs over non-interactive proofs (besides the one above, that apply specifically to Fiat-Shamir): If you want an extremely efficient proof, where verification is super fast and the communication is very small, then this can be achieved using an interactive proof using standard and well studied assumption, such as collision-resistant hash functions (this paper), the discrete logarithm problem (this paper), etc. In contrast, if you want such an efficient NIZK, you either only have security in the random oracle model (using Fiat-Shamir), or must rely on exotic and poorly understood assumptions, such as the knowledge-of-exponent assumption.

As for complexity-theoretic discussions on NIZKs versus ZK proofs, I discussed the complexity-theoretic questions related to the round complexity of zero-knowledge proofs in this answer. There is also some discussion on the hardness of building NIZKs from standard assumptions (compared to the relative easiness of building interactive ZK from standard assumptions) in the introduction of my recent paper, which you might find relevant.


On plaintext conversion for DES The DES (Data Encryption Standard) takes 64 bit key as input but how is the plain text of length say n is getting converted into 64 bit binary format?

The conversion to binary is not part of the DES standard. So you'll have to define that part of the protocol yourself. The cipher itself needs to be used with a mode of operation, as fgrieu indicated.

There are basically two families of modes of operation: streaming modes of operation and block modes of operation.

In block modes sych as ECB or CBC you have to split the plaintext into separate, sequential blocks, usually after padding the plaintext.

In streaming modes such as CFB and OFB the bytes may be encrypted byte for byte.

Of course the API (the programming interface) of high end implementations of ciphers or modes may hide such implementation details.


Do I need to keep a 64-bit version number secret? Assume the following structure:

version | iv | ciphertext | HMAC(version | iv | ciphertext | ..., key)

The version starts out to be a "random" 64-bit number. It identifies the key used to encrypt the ciphertext for the purpose of key rotation (version is not, nor does it contain any part of the key). For every message encrypted by the same key, version is the same. The rest of the text, starting with a random iv, is always different.

Is there any reason I need to protect version? If an attacker knows the version the most they can do is identify a group of ciphertext that was encrypted with the same key.

The ciphertext itself has validity period of it's own. The data should be updated around the same time as the key is rotated. The rational behind version is to allow the ciphertext to be updated gradually as-needed.

Would obscuring the version in some way add any benefit, even small? Something like this:

$Version_n \oplus Hash(iv)_n$

I know this adds no real security benefit. If version doesn't need to be protected, the most I'm going for is to make it appear random.

For most purposes, you probably don't need to provide confidentiality protection for the version field.

There may be some settings where the version field allow traffic analysis, and to analyze that, we'd need to know so much detailed information about your particular protocol that the question would probably become too localized to be a good fit for this site -- but for most circumstances, you don't need to worry about confidentiality protection.

I do recommend you do apply integrity protection (e.g., the MAC, as shown in your question).  The word "protect", in cryptography, is ambiguous, and it's important to understand that confidentiality protection is not the same as integrity protection.


Why RSA2048 sign of Intel accelerate card is fast? Intel accelerate card

This card executes rsa2048 sign 35K ops(operation/second). My fast version is only 100 ops.

I can't find any HSM paper that has same performance level.

I am interested in this problem. I know modexp, montgomery, crt, PE-array and some other circuit skills, but I can't reach such a high performance.

Could someone give me a hand please? Thanks very much.

Specialized hardware is the answer. This machine uses asynchronous computation, very likely using parallel Montgomery multipliers and a local register of 4096 bits (4096 seems to be the largest key size for RSA, so we can conclude that this is the size of the register). Similar hardware can be found in Smart Card CPU's. These don't go as fast, because they are hampered by low power consumption, TDP, a relatively slow - often 8/16 bit - CPU and large transistor sizes. The solution requires OpenSSL 1.1 to utilize the asynchronous API that the Intel QuickAssist hardware offers.

Newer Intel chips have vectoring instructions that also help to speedup the multiplication and squaring required to perform fast modular exponentiation (the base of any RSA calculation). However, they don't offer a Montgomery multiplier of sufficient size to overtake fully specialized hardware (actually, the use of the vectoring constructions may quickly lead to overheating and scaling down of processor frequencies).

It's unlikely you can beat specialized hardware in software; modular exponentiation is not a cheap operation (it's only fast compared to finding large primes required for RSA key pair generation). Furthermore, you may make a very fast implementation that is not protected against side channel attacks, which is a major requirement for keeping your private key secure.

Note that the specialized hardware is not an RSA accelerator (that the software delivered with the hardware does offer). It performs the mathematical operations more quickly. It can also be used to speed up (EC)DH and (EC)DSA, for instance.


Is there any course video for lattice cryptography? Recently, I started doing research about Lattice Based Cryptography. and searched on YouTube a lot of public talks or seminars about it.

But is there any course video (graduated course) related to it?

It's from 2012, so it's not the most up to day. However, the 2nd BIU winter school was on this topic, and all of the slides and videos can be found online. The lecturers were Craig Gentry, Vadim Lyubashevsky, Chris Peikert and Oded Regev. The link is here: https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/.


Is this truly a TRNG? As an appendix for my bachelor thesis, I proposed a solution for a TRNG that uses JPEG images as entropy source.
It's open source and available on GitHub.

My question is:
can this be really considered as a TRNG?

Obviously I tried to create a TRNG (and not a PRNG or a CSPRNG), but you know... the devil is in the detail.
Here some info, so you can help me enstablish if it can be considered as a TRNG or just a bottle of snake oil :)

How it works

It uses two different input images (with the same resolution). These images are considered independent because captured in two different moments.
It uses the Mixing technique, so the output will be unpredictable if at least one  of two images is unpredictable.
Only some of the total amount of pixels are considered. The CSPRNG SecureRandom sets for each considered pixel how many consecutive pixels have to be discarded. In this manner the correlation between consecutive pixels is avoided. This also guarantees that if the generator is run twice two different outputs will be generated.
Only the BLUE channel is considered. So the correlation between different channels is avoided.
The noise that can be found inside an image is located in the least significant bits (LSB). For this reason only the LSB of each input byte is used. You can choose to consider the second least significant bit too.

Bruce Schneier guidelines

In Applied Cryptography, Bruce Schneier lists some guidelines to check if a generator could be considered as (CS)PRNG or TRNG:

  For our purposes, a sequence generator is pseudo-random if it has this property:
  It looks random. This means that it passes all the statistical tests of randomness that we can
  find.
  For a sequence to be cryptographically secure pseudo-random, it must also have this property:
  It is unpredictable. It must be computationally infeasible to predict what the next random
  bit will be, given complete knowledge of the algorithm or hardware generating the sequence
  and all of the previous bits in the stream.
  Philosophy aside, from our point of view a sequence generator is real random if it has this
  additional third property:
  It cannot be reliably reproduced. If you run the sequence generator twice with the exact
  same input (at least as exact as humanly possible), you will get two completely unrelated
  random sequences.

And the solution I proposed:

I executed some tests, and seem promising. Maybe other tests are required (?)
It doesn't use hash functions. Each output bit is dependent on a specific pixel only. So, if an attacker knows the previously created bits, he cannot foresee the future ones.
It uses a CSPRNG just to choose the pixels to consider. So, executing the generator twice, each time two different outputs will be generated.

Just no.
If you use some files and a CSPRNG as data source for a deterministic algorithm, it's not a true random number generator.

According to your own Schneier quote:

  If you run the sequence generator twice with the exact same input (at
  least as exact as humanly possible), you will get two completely
  unrelated random sequences.

It sounds like your generator will generate the same numbers, so... don't mistake the CSPRNG for your generator. The CSPRNG is input for your generator. (And even if not, same input for CSPRNG is same output).

There are other problems (like thinking two images of the same place are independent), but they don't really matter anymore.

...

  Obviously I tried to create a TRNG

That's a pretty good giveaway that you don't really know what your doing. A TRNG can't be created with some software piece on a turing-machine-alike. Nobody can, never.


Do these 2 KSA shortcuts weaken RC4? Alice securely gives Bob a secret key so they can exchange 10 different messages encrypted with RC4.  (Messages will include a counter for uniqueness and a MAC for authentication.)  For each message exchange, Alice and Bob both start by permuting the standard byte array using the secret key (ie, the "KSA" key-scheduling algorithm, per Wikipedia):

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

At this point, Alice and Bob have each computed identical S[] arrays, and the secret key is no longer used by subsequent RC4 steps.

Shortcut 1:  Alice decides that instead of securely sending Bob the secret key and making him do the KSA step for every message exchange, she'll compute the S[] array, securely send him the 256-byte array instead of the secret key to begin with, and from then on each time they need to encrypt/decrypt they'll both skip the KSA step to save time and just start with Alice's precomputed S[] array.

Shortcut 2:  After using the above algorithm to compute the initial S[] array she had planned to send to Bob instead of the secret key, Alice realizes the KSA step seems to basically just want to scramble the S[] array.  So instead of scrambling the array based on a key, she relies on the operating system random() function and just computes...

for i from 0 to 255
    S[i] := i
endfor
for i from 0 to 255
    swap(S[i], S[random(0..255)]) // swap S[i] with some arbitrary S[]
endfor

...and securely sends Bob her "randomly" scrambled array that doesn't even use a key.

Do those 2 shortcuts weaken RC4?

The obvious problem with Shortcut 1 is that the same keystream will be used to encrypt all the messages.  That is, an attacker can exclusive-or two ciphertexts together, and the result will be the exclusive-or of the two plaintexts; this may very well allow the attacker to recover both messages.  How easy this is depends on the language the messages are in; if we assume they are in ASCII-English, this is fairly straight-forwarding as long as the messages aren't extremely brief.

There are two obvious problems with Shortcut 2:

How cryptographically secure is the operating system "random" function?  Quite often, such operating system functions are only statistically random, this might not be good enough.
You say that Alice "securely" sends Bob the array; is she sending a separate array for each message?  If so, why doesn't she use that secure method to send the message?  If not (that is, she reused the same array for different messages), she runs into exactly the same problem as Shortcut 1.

Also, in shortcut 2, your pseudocode says "Assign a random S[] element to S[i]", while your comment says to swap them.  Which do you mean?  What you really want to do is swap the elements (it's important that S[] remain a permutation).


addition on finite elliptic curves I tried to calculate the sum of two Points on an elliptic curve in a finite field. The Curve is defined as following:

$$y^2 \equiv x^3 + x \mod 257$$

So the curve parameters are $a = 1,b = 0,p = 257$.I want to add the two points $P = (1|60)$ and $Q = (15|7)$:

$$60^2 \equiv 1^3 + 1 \equiv 4 \mod 257$$
$$7^2 \equiv 15^3 + 15 \equiv 49 \mod 257$$

To add this two points, I calculate the slope $s$, $x_r$ and $y_r$:

$$s = \frac{y_q - y_p}{x_q - x_p}$$
$$x_r = s^2 - (x_p + x_q)$$
$$y_r = s(x_p - x_r) - y_p$$

for my points $P$ and $Q$ I get:

$$s = \frac{7-60}{15-1} = \frac{-53}{14} = -3.7857142857$$
$$x_r = (\frac{-53}{14})^2 - (1 + 15) = 14.3316326531 - 16 = -1.6683673469$$
$$y_r = \frac{-53}{14}(1-(-1.6683673469)) - 60 = -70.1016763848$$
$$R = (-1.6683673469|-70.1016763848)$$
However:
$$x_r^3 + x_r = -6.3121837787$$
while
$$y_r^2 = 4914.2450319648$$
So $R$ seems to be outside the curve. Even if I calculate everything modulo 257 I get weird results.

What I don't understand:

since I defined the curve on a finite field, I expected integer results
I expected $R$ to be part of the curve
the definition of $x_r$ is the difference between $s^2$ and the sum of the x-coordinates of the two added points. Why can $s^2$ be interpreted as an x-coordinate or even a length?
in reference to wikipedia, the addition of two points of an elliptic curve is commutative. That seems to be true for $x_r$, but why should it be true for $y_r$?

Notes:

I looked for an answer to this questions and all I did find were this and this. Both questions looked similar to mine but I still don't understand addition on elliptic curves.
I'm really new to elliptic curves, sorry if I did huge mistakes by calculating these values

You are right, when you're working on a finite field, you should get integer results. So let's look at why you aren't.

The problem lies in how you handle the fractions inside the equation, e.g.
$s=\frac{y_q-y_p}{x_q-x_p}$. Elliptic curve operations make use of finite field arithmetic. Maybe it'd be easier for you to grasp if you imagined the equation to look like $s=(y_q-y_p)(x_q-x_p)^{-1}\mod p$. This means that you have to calculate the modular inverse of the denominator of your fracture and then multiply this with the nominator.

$R$ is indeed part of the curve. Recalculate it using the "technique" described above.
It's not right to see it as length. As you're reducing the result modulo a prime ($\mod p$) the information which you call "length" is lost.
Take two points that are part of an elliptic curve, e.g. $P$ and $Q$. Commutative means that $P + Q$ gives the same result as $Q + P$. However it does not mean that you can just switch the $x$- and $y$-coordinates


Is there a difference between PRF and a hash function? Is there a difference between  PRF and a hash function?

For example: Creation of a secret key is using PRF and creating a secret key is using hash function.

No, the two primitives are definitely not the same.

A pseudorandom function is a keyed function that is (computationally) indistinguishable from a function chosen at random from all functions with matching domain and range as long as the key remains secret.

On the other hand, a cryptographic hash function is a function with either a publicly known key (in theory) or no key at all (in practice) that is compressing and collision resistant. That means, it maps long inputs to outputs of a fixed length and it is hard to find two inputs that map to the same output.


Why not combine hashing algorithms? The recent SHA1 collision got me thinking.. why do we always throw out the baby with the bathwater when moving to more modern hashing algorithms?

When GIT was written, they went with SHA1 hashes because MD5 was too old and had verified collisions. It is inevitable that given enough time and effort, any current and future algorithms will have problems and eventually demonstrable collisions.

So why not just choose to combine hashing algorithms, preferably the most modern, with the second most modern? Naturally, the hash length in bits would be longer, but seems to be a better way of future-proofing a system than just "use the best at the time of writing"

Is SHA1 hash concatenated with MD5 hash more or less likely to introduce a collision?

This question is similar to asking whether combining multiple symmetric encryption algorithms is a good idea. Of course it is less likely to get a collision for MD5 and SHA-1 simultaneously compared to just getting a collision for SHA-1. Surprisingly, it is, however, not much more expensive to find a collision to both MD5 and SHA-1 than to find one only for SHA-1, as explained here. Also using two hashes decreases the efficiency because you have to hash everything twice and it becomes more difficult to implement it correctly. Moreover, if you care not only about collision resistance, but also other properties, concatenating two hash functions could even be less secure than using just one of them, as explained here. Overall, it seems to be a better idea to just use one good hash function.


RSA-OAEP Input Parameters When creating padding for RSA using OAEP, a message is prepared as follows:

Hash(Input Parameter) || Zeros || 1 || Message

My question is, what should the Input Parameter be? It must be known to both sides, I understand it can be an empty array (string, whatever). In that case there is no need to calculate the hash, hashing an empty input always produces the same result.

Is there a recommendation regarding what to use as the input parameter?

I'm thinking about hashing the public modulus n, which is already known by all parties. It's not necessary I suppose since the random seed from the other part of the OAEP procedure will change the final value anyway, but I'm still curious what is considered "best practice", or some requirement that I missed.

The Input Parameter in the question is called a Label in PKCS#1v2.1; this standard states it might be empty, or be expressed in some specified syntax. I borrow Victor Shoup's explanation from Remark 3 in this paper:

  A label is a byte string that is effectively bound to the ciphertext
  in a nonmalleable way. It may contain data that is implicit from
  context and need not be encrypted, but that should nevertheless be
  bound to the ciphertext. We view a label to be a byte string that is
  meaningful to the application using the encryption scheme, and that is
  independent of the implementation of the encryption scheme. For
  example, there are key exchange protocols in which one party, say A,
  encrypts a session key K under the public key of the other party,
  say B. In order for the protocol to be secure, party A's identity
  (or public key or certificate) must be non-malleably bound to the
  ciphertext. One way to do this is simply to append this identity to
  the cleartext. However, this creates an unnecessarily large
  ciphertext, since A's identity is typically already known to B in
  the context of such a protocol. A good implementation of the labeling
  mechanism achieves the same effect, without increasing the size of the
  ciphertext. Labels may also be of arbitrary and variable length, but
  we do not impose the restriction that the encryption and decryption
  algorithms should be able to process labels as streams. Both the ECIES
  and RSA-OAEP submissions include the notion of a label (where it is
  called an encoding parameter), although absolutely no indication was
  given as to the role or function of a label. Nevertheless, it seems to
  be a potentially useful feature (..)


Why XOR and NOT is free in garbled circuit I am having trouble understanding the term "free" in V.Kolesnikov et al's paper.

1. Why NOT is free

In page 4, section 3.1, they said that NOT gate is free

  by simply eliminating them and inverting the correspondence of the wires’ values and garbling

I came up with the following example, which confused me

Let's say that $a,b$ are two single digit inputs from Alice and Bob, respectively.
Suppose Alice is the garbler, she garbles the above circuit and sends to Bob, along with her garbled input $GI(a)$. She then sends Bob's garbled input $GI(b)$ to Bob through obvlivious transfer.  In this example, without trying to implement NOT "for free", Alice only has to send

garbled circuit $\hat{C}$, which contains 7 wires (in different colors above), each with two labels
.$GI(a)$
$GI(b)$, and Bob can figure out the result.

Following the first step "simply eliminating them", I remove all the NOT gates and get the following circuit

Now, AND1 and OR1 shares the same input from $b$. No matter how I invert the wire's value, the circuit will not represent the same function as before.

It seems now I have to separate the inputs for AND1 and OR1, and then give them different labels, although they came from a single source in the original circuit. Then the circuit would still have 6 wires, which isn't quite "free". If it was free, shouldn't we be able only to use 5 wires to construct the ciruit?

2. Why XOR is free
In the same page, they showed their XOR gate $G$.

I see that by doing this the garbler won't have to generate random labels for $w_i^1$ and $w_c^0$. But why is it called free?

In addition, what's the computational saving between generating random labels for all wires and generating only $w_a^0,w_b^0,R$ then computing other labels from the three?

Regarding the NOT gates in your example. Suppose the wire called $b$ has wire labels $B$ for false and $B \oplus R$ for true. Then you would garble gate "AND1" using these labels as normal, and you would garble gate "OR1" imagining that $B \oplus R$ means false and $B$ means true.

There are two equivalent ways to think about this. One is to consider the output of the NOT gate to be a separate wire (separate from the input to the NOT gate). If the NOT gate input wire has labels $A, A\oplus R$ then the output wire has labels $A \oplus R, A$.

The other way to think about it is to absorb all NOT gates into their neighboring AND/OR gates. In your example we could garble a NAND for gate AND1 and we could garble a gate $(x,y) \mapsto (\lnot x \lor y)$ for OR1. The way to actually do this is the same as above, just let the garbler switch the "meaning" of the two wire labels, locally for this gate.

Regarding free XOR: the main cost that it saves is not in generating random wire labels for output wires. (In fact, advanced GC constructions do not sample wire labels at random except at the inputs.) The savings are: (1) neither garbler nor evaluator have to evaluate a cryptographic primitive to process this gate. Instead they just make one xor computation. (2) Nothing must be included in the garbled circuit, saving bandwidth. So XOR gates are free for communication cost, and are "free" in computational cost of crypto operations (as you point out, not "free" of all computational cost since some minor xor computation is required).


Attack on a key-exchange,symmetric-key cryptography protocol This is an exam question in Oxford 's Computer Security course:

  Here is the start of a protocol, based on a long-term secret key $k_{AB}$ previously shared between Alice and Bob, designed to offer bilateral authentication and establishment of a session key $k_s$. The session, which begins at message 4, is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents.
  1.$A \to B$: Alice, $nonce_A$
  2.$B \to A$: $nonce_B$, $E_{k_{AB}}$$(nonce_A \| k_1)$
  3.$A \to B$: $E_{k_{AB}}$$(nonce_B \| k_2)$
  Alice and Bob both compute $k_s$ = $k_1$ ⊕ $k_2$
  4.$A \to B$: $E_{k_s}(...)$
  5.$B \to A$: $E_{k_s}(...)$

  a) Why would Alice and Bob want a session key $k_s$, rather than simply using the already shared secret key $k_{AB}$ for session encryption?
  b) How should Alice and Bob format the contents of their session, messages 4 onwards, to meet the aims of the protocol?
  c) If they additionally wish to ensure the integrity of the session, what should they add to the protocol?
  d) Does this protocol provide key agreement or does it provide key transport? Explain your answer.
  The following appears to be a man-in-the-middle attack on the protocol, under the usual Dolev- Yao model:

  1.$A→I_B$: Alice ,$nonce_A$
  1´.$I_A→B$: Alice, $nonce_A$
  2´.$B→I_A$: $nonce_B$,$E_{k_{AB}}$$(nonce_A ∥ K_1)$
  2.$I_B→A$: $nonce_B$,$E_{k_{AB}}$$(nonce_A∥K_1)$
  3.$A→I_B$: $E_{k_{AB}}$$(nonce_B∥K_2)$
  3´.$I_A→B$: $E_{k_{AB}}$$(nonce_B∥K_2)$
  Alice and Bob continue their sessions with the intruder.
  e) Why does the above sequence not constitute an attack on the protocol?
  f) Although not subject to man-in-the-middle attacks, there does exist a flaw in the protocol. Find it, and explain carefully why it does constitute an attack on the protocol.

Part f) is where I'm currently stuck.

One attack I can think of is when $nonce_A = nonce_B$ a Dolev-Yao attacker can pose as B and send A $E_{k_{AB}}$$(nonce_A ∥ k_1)$ in message 3 then $k_s = k_1 ⊕ k_1 = 0$ then the attacker know s$k_s$ and he can send message and decrypt message. But the chance $nonce_A = nonce_B$ is very small, so I'm not sure if it constitutes an attack.

I'm not sure but in my point of view.

Since $k_{AB}$ is used to authenticate both side.
Mapped $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pair on one side can be used on both side.
Thus we can gather $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pairs from $B$ since $B$ will happily echo $E_{k_{AB}}$$(nonce_x∥k_x)$ for every $nounce_x$ I asked.

This doesn't form practical MITM attack but I can make $A$ agree on $randomK_1⊕k_2$ as $k_s$ while on the other side $B$ will accept $k_1⊕k_2$ as $k_s$. In another word we can make $A$ and $B$ agree on different values at probability equivalent to (or more than because we can query it ourself) birthday attack.

This might make some cryptanalysis possible but I don't know the details.

As you suggested in chat:
$nonce$ collision is unnecessary we rather change the scheme to something like:
After received $nonce_A$ we send it to $B$ twice but only sent the first response to $A$


Is quantum key distribution safe against MITM attacks too? i read this recently: http://www.newscientist.com/article/dn12786-quantum-cryptography-to-protect-swiss-election.html

and some parts of this: http://en.wikipedia.org/wiki/Quantum_key_distribution

they talk about direct fibre optic cable and evesdropping that seems passive.

i want to know whether quantum key distribution provides any security against active attacks too?

i mean, for example isn't it possible that fibre optic cable is cut at some point in its path by an attacker and then he places a repeater there and before repeating the signal he can read the secret information in the channel?

No, Quantum Key Distribution is not any safer than conventional crypto is against an active Eve impersonating as Bob to Alice using the same equipment and knowledge as the rightful Bob (or/and impersonating as Alice to Bob using the same equipment and knowledge as the rightful Alice). Otherwise stated, QKD can resist Man Eve In The Middle only inasmuch as Eve lacks some initial shared secret known only to legitimate parties Alice and Bob (or there is an independent channel with known integrity, but that's impractical).

The best QKD claims to achieve is turn an authenticated channel (or a short shared secret) into a channel safe from any eavesdropping (or an arbitrarily longer shared secret), against any attack active or passive (including by MITM). E.g. Alice and Bob start from a shared secret of say 512 bits (that could be the conventional hash of a pass phrase), assumed unknown to Eve. Alice and Bob apply some protocol with photons and mirrors, plus some conventional operations¹ on bits for post-processing; and end up with some kilo bits (per second of experiment) of random secret material unknown to Eve. Alice and Bob can use that secret material to encipher data using a One Time Pad (perhaps while they are generating that secret material, so they need not store it).

Non-quantum cryptography routinely does the same (or better: the initial trusted data needs not be secret, e.g. Alice and Bob can exchange their public key; this makes it easier to safely use asymmetric non-quantum cryptography than it is to use QKD). However non-quantum cryptography relies on assumptions on the hardness of some problem, such as the discrete logarithm problem, or/and finding more plaintext/ciphertext pairs given examples for a blockcipher; whereas QKD, and more generally Quantum Cryptography, attempts to rely only on the laws of physics.

The security track record of QKD systems is poor: one security problem has been that imperfections of single-photon sources could be exploited; another rather spectacular one was active blinding; now I'm hearing of double blinding. QKD is not practicable with the current fiber infrastructure (quantum repeaters, if any, exist in labs only). Combine with the fact that QKD solves a problem that is already solved in practice, more conveniently, by classical cryptography, and many reach the conclusion that QKD is a marvelous accomplishment but pointless in practice, except perhaps as a justification for funneling out money.

Update: the need for an initial shared secret (or a channel trusted for integrity) is acknowledged in this whitepaper by ID Quantique², a supplier of KQD equipment:

  Key distillation is then complemented by an authentication step in order to prevent a “man in the middle attack”. In this case the eavesdropper would cut
  the communication channels and pretend to the emitter that he is the receiver and vice versa.
  Such an attack is prevented thanks to the use of a preestablished secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only
  to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

¹ Despite the inevitable errors in the quantum communication, these conventional operations can be simple, secure, and robust: pick at most two attributes! Perhaps the most cited considered to reaching the later two is the cascade protocol in: Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

² Originally available there.


Using date stamp down to milliseconds / ticks as a salt? As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash.
The salt is often stored with the hash, either prepended or as a separate field.
As this just needs to be "different" for every input, would using something like:
DateCreated.ToString("yyyyMMddHHmmssffffff")
To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond. This would be unique per record and provide the means to change the hash.
As an example, if I run a basic hash:
 using (HashAlgorithm algorithm = SHA256.Create())
                return algorithm.ComputeHash(Encoding.UTF8.GetBytes(inputString));

If my input string is BabySharkDoDoDoDo - every time this is hashed, I'll get the same result: 567d01ee59d062ff75435033b4c2593058aed5b5ccca0f29ba92b22c13e084b3
So, to make sure each entry to my shark database is unique, I prepend the inputString with DateTime.ToString("yyyyMMddHHmmssffffff") - so my input to the hash becomes 202104132059471235487BabySharkDoDoDoDo and each time I get a unique hash.
So I can check the input is valid, if someone enters the right record and the string BabySharkDoDoDoDo I need to store the salt, either with the hash or in the separate column.
So, the salt is known to the attacker - always the case right? So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?
If I go for it and create a 128 bit salt, from a crypo library, Rijndael or similar - sure it's unique (hopefully), but I then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.
A timestamp down to the millisecond or tick would also be unique and serve the same purpose?

You're going out of your way to create more work for yourself, and introducing a vulnerability. It's not necessarily a huge vulnerability, but why bother?

To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond.

You cannot have such a guarantee, not without doing very complicated things.

If your server is fast enough, it may take less than one millisecond to serve a request. Even if it doesn't now, maybe it will after a hardware upgrade.
Clocks are not always accurate. Just because you have a function GetCurrentTimeInMilliseconds() doesn't mean that it has millisecond accuracy.
The time can go backward if the clock is adjusted. Or if you use the local time rather than wall-clock time.
If you have multiple threads running on multiple processors, they will, from time to time, happen to serve a request at exactly the same time, no matter how much resolution your clock has.
If the same code is running on multiple servers, it's the same thing: they'll all be generating the same number at the same time.

Depending on the purpose of the salt, repeating a value may or may not be catastrophic. For a nonce or IV in encryption, it is often catastrophic. For password hashing, the attacker only has a small advantage if the salt is rarely repeated.

then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.

Yes. This applies no matter how you generated the salt.

So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?

You don't need “crazy random entropy”. You just call GenSecureRandom() or whatever your function to generate cryptographically secure random bytes is called. This is less complicated than the date-based approach you propose!
Even better, when hashing a password, the password hashing library should take care of generating the salt. But if you're stuck with an old API that requires you to do the work, then just generate a random salt of the length stated in the documentation of the library or of the password hashing algorithm. This is the simplest method.


Why are zk-SNARKs possible, in layman's terms zk-SNARK: Zero-Knowledge Succinct Non-interactive Argument of Knowledge

From the Ethereum blog:

  One natural use case for the technology is in identity systems. For example, suppose that you want to prove to a system that you are (i) a citizen of a given country, and (ii) over 19 years old. Suppose that your government is technologically progressive, and issues cryptographically signed digital passports, which include a person’s name and date of birth as well as a private and public key. You would construct a function which takes a digital passport and a signature signed by the private key in the passport as input, and outputs 1 if both (i) the date of birth is before 1996, (ii) the passport was signed with the government’s public key, and (iii) the signature is correct, and outputs 0 otherwise. You would then make a zero-knowledge proof showing that you have an input that, when passed through this function, returns 1, and sign the proof with another private key that you want to use for your future interactions with this service. The service would verify the proof, and if the proof is correct it would accept messages signed with your private key as valid.

I bolded the parts which seem impossible to me intuitively. I found some research papers with very technical explanations, which I don't understand. Could someone explain why this is possible, in layman's terms? Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

Some documentation and code

When you have eliminated the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

If I find you in my dorm room and the door and windows are intact, I can only conclude that you somehow learned the entry code, because I do not know of any other way by which you could have entered my room without breaking the door or windows.

A ZK-SNARK for a function $f$ is similar: if you present a proof for the result $1$ which can pass the verification procedure, it necessarily means that you must know an $x$ such that $f(x) = 1$. This is because we do not know of any (efficient) way to generate such a proof if you do not know such a value $x$. In fact, we have a proof that being able to do this would imply being able to solve certain mathematical problems which are believed to be hard (you can think of factoring integers, although the problems used to construct SNARKs are more complicated). So when you say

  Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

... there may or may not be, but we do not know of any and we consider it very unlikely (i.e., impossible, for all practical purposes).


Why is it insecure to use a randomized IV for CBC-MAC instead of an all-zero IV? A fixed length CBC-MAC uses an all-zero block as the initialization vector.

Suppose that we used a randomized IV instead, and sent the IV along with the tag.
So if the message $m$ will be $m = b_1 || b_2 || b_3 || ... || b_l$, the MAC will be $(IV, t)$ where $t$ is the authentication tag defined as normal.

Why is this method of using a randomized IV more insecure than the normal method of using an all zero IV?

(This method was used in some nCipher products, and declared insecure in nCipher Advisory #13 – see also  nCipher Insecure CBC-MAC API Vulnerability.)

The nCipher Advisory #13 cited in your securityfocus.com link contains the explanation of the vulnerability (in the section "Cryptographic details").

The CBC-MAC algorithm works similar to the CBC encryption algorithm, but only outputting the final block (or a part of this).
Each block of the plain text is XOR-ed with the previous ciphertext and then encrypted.

This means we XOR the first block with the initialization vector before it first comes into contact with the block cipher. So changing only the first block together with a corresponding change in the initialization vector will mean that the same value is input to the block cipher, which gives the same resulting authentication tag at the end (which does not have to be changed).

If the initialization vector is fixed as zero (or some other constant), there is no way for the attacker to change it together with the first block, and this kind of attack is not possible. As an added bonus, we have one block of data less to transfer.


Why programming languages don't provide simple encryption methods? In c#, there is a namespace called System.Security.Cryptography and there are many classes in this namespace, which help developers encrypt and decrypt data. However, always they take byte[] array and they return byte[] array. So, as a developer, you have to always write a library to get the clear-text, turn it into byte of arrays, encrypt it, then turn the cipher array into an string, and return it.

I've talked to some other PHP and Java developers, and they told me that they have to undergo the same process there too. I haven't seen those languages though.

My question is, why frameworks like .NET framework, don't provide an straightforward mechanism for encryption and decryption?
I mean, from the point of view of a developer, cryptography means a black box into which you pass a string, and from which you will get an string, without the need to get into the complexity of creating streams like CryptoStream and without the need to converting strings into bytes of arrays, etc.

For example, look at this simple encryption example, taken from Microsoft's MSDN:

    static byte[] EncryptStringToBytes(string plainText, byte[] Key, byte[] IV)
    {
        // Check arguments.
        if (plainText == null || plainText.Length <= 0)
            throw new ArgumentNullException("plainText");
        if (Key == null || Key.Length <= 0)
            throw new ArgumentNullException("Key");
        if (IV == null || IV.Length <= 0)
            throw new ArgumentNullException("Key");
        byte[] encrypted;
        // Create an Rijndael object
        // with the specified key and IV.
        using (Rijndael rijAlg = Rijndael.Create())
        {
            rijAlg.Key = Key;
            rijAlg.IV = IV;

            // Create a decrytor to perform the stream transform.
            ICryptoTransform encryptor = rijAlg.CreateEncryptor(rijAlg.Key, rijAlg.IV);

            // Create the streams used for encryption.
            using (MemoryStream msEncrypt = new MemoryStream())
            {
                using (CryptoStream csEncrypt = new CryptoStream(msEncrypt, encryptor, CryptoStreamMode.Write))
                {
                    using (StreamWriter swEncrypt = new StreamWriter(csEncrypt))
                    {

                        //Write all data to the stream.
                        swEncrypt.Write(plainText);
                    }
                    encrypted = msEncrypt.ToArray();
                }
            }
        }

        // Return the encrypted bytes from the memory stream.
        return encrypted;

    }

This is just not simple and easy, and I think there should be a class in .NET Framework like TripleDesCryptoHelper with two methods as follow:

public string Encrypt(string clearText)
{
    // Doing the cryptography stuff here
    return cipherText;
}

public string Decrypt(string cipherText)
{
   // Doing the cryptography stuff here
   return clearText;
}

It's not nearly as simple as you imagine. When you encrypt a string, what character set is it in? What characters are permissible in the output? There are too many unusual combinations of code requirements and security requirements for a "one size fits all" to make sense.

But if you think one size does fit all, sit down and write it. It should take you an hour or so. You'll have it forever, can share it with other people, and this problem will be solved. I think you'll find everyone needs it to be a little different and you'll be right back where we are.

Here's a function to set the character set. Here's a function to switch between hex and base64. Here's a function to add padding. Here's a function to add a checksum. Here's a function to set the key in hex. Here's a function to set the key in base64. And so on, and so on, and so on.

Fundamentally, encryption is not easy. Threat models differ. Requirements differ. One simple "this encrypts" interface is much more likely to be used to disastrous results than good ones.

There's also the attractive nuisance issue -- things that are neither easy nor safe probably should not look easy and safe.


How to generate backup key for PBKD functions? I would like to encrypt some files using AES, Ill derive key from password using some standard PBKD function and use that as AES encryption key.

My question is, if user forgets the main password, then he has no input into PBKD function thus no way of getting the AES encryption key.

What algorithm/technique should I use to generate together with the key also a kind of "backup key", preferably a 16 digit number (so ~53 bit key) which can also be used to derrive correct AES encryption key? User would be encouraged to write down this key on paper and save it on a safe place in case main pwd is forgotten.

My idea was to actually encrypt the password used by client using a 53 key, and when needed decrypt it and let user replace or view his lost password, but this would severely compromise the security, as itd lower the difficulty of attack to just getting the 53bit backup key.

So it looks to me that I have to use at least 128bit random key (same strength as the main derived key), which I can convert to ~38digit decimal number or 32digit hexadec number. This is way longer than Id like.

Now while using a 53bit key as a backup key may seem as a crypto joke, when we actually consider that an average password would be 8 digit alphanum string, using lowercase, uppercase, numbers and something like 10 special chars (if only users followed at least these guidelines...), this gives us about 72^8 ~~ 2^50 options, i.e. the output key from PBKD func is an equivalent to 50bit key. a 128bit key would require PBKD input to be at least 21 of these mixed chars and I dare guess users dont usually use such long passwords.

So what are your suggestions and comments on the scenario I described? Thanks.

This kind of key management problem is a big reason why encryption is not more widely used for everyday data.

I see a single easy way to do this, I think it is similar to the way disk encryption systems work, and it may not work for your uses.

For each file, a random key $kf$ is generated. 2 copies of the key are encrypted, one with a key derived from the password ($kp$), the other with a key derived from the backup code ($kb$). The original key is used to encrypt the file, and the 2 encrypted copies of this key are stored with the file.

$EncFile = E_{kp}(kf) \ || \ E_{kb}(kf) \ || \ E_{kf}(File)$

This can also be done on a per user basis. The encrypted keys are not stored with each file, just one copy with a group of encrypted files, and backed up somewhere else.

This scheme allows decryption of the files using either the password or the backup code, and also allows the password to be changed without changing the backup code or reencrypting the files, only the encrypted file key is changed, which is the first few bytes of the encrypted file, or stored in a separate file. It also slows down brute force attacks slightly, thanks to the additional encryption operation.

The scheme would store the 2 encrypted keys with the encryption software, and decrypt the file key from the password when encrypting new files, so that the user or the software does not need to know the backup code. There should be some way of knowing that the file key is decrypted correctly before using it, here is one of many methods:

We have a 16B random plaintext block $P_r$, and a known hash of $E_{kf}(P_r)$. Once the password key is derived we generate:
$kt = D_{kp}(E_{kp}(kf))$
$ht = Hash(E_{kt}(P_r))$
Then $ht$ is compared to the known hash, a match means the password is correct. This may seem a little more complex than just comparing it against an encrypted copy of the block, but it eliminates a plaintext/ciphertext pair an attacker could use for key recovery attacks.


Constructions of PRF (Pseudo Random Function) I was taught only GGM based PRF construction in class. It's very inefficient. I am just curious about various PRF constructions from standard assumptions. Please provide a few PRF constructions from various assumptions.

The most common efficient PRFs from specific assumptions are:

The Naor-Reingold PRF, which is based on the decision Diffie-Hellman assumption (DDH), and

The BPR PRF, which is based on the learning with error assumption (LWE).

Perhaps slightly less well-known is the NRR PRF, which is based on the hardness of factoring.


Should I remove these use cases of MD5/SHA1 from my program? I have a web app (a register and login system) written already but i am now improving it. One of its design goals was high security.

I have some use cases of md5 and sha1 in it and now i am in doubt if i seriously need to replace them (and with what and how).

I mention that uses here and please tell me if i should replace which cases  why and with what other algorithm (please also mention the necessary bit length that u think is the minimum acceptable). but consider that i don't want to get it too hard; e.g. concatenating the output of sha256 to 128 bits for replacing an md5 invocation seems ok too me (i have asked about that before and seems there is consensus that that is considered secure enough for most practical cases considering i am writing a php app running on real world web servers (I think NSA or hackers can breach via those layers, PHP and web server environment, more easily)), so i don't insist on the latest and top secure standards and don't want to use complicated/bulky algorithms just to reduce a hash output length from 256 to 128!

usage 1:

md5 is used to mix several independent keys to form a single 128 bit key to be used in AES128+HMAC encryption (same key is used for enc and hmac; yes i  know it is considered bad practice, but not really serious so far).

sample code:

$aes->setKey(pack('H*', md5($GLOBALS['pepper'].$GLOBALS['site_encr_key'].$GLOBALS['client_sess_key'])));

usage 2:

sha1 is used to mix several sources of entropy obtained from client request parameters to be used in the current crypto operation. this extra entropy is stored too and later used in almost all other crypto operations. Neccessary to mention that, all crypto operations have their own newly generated sufficient entropy (at least 128 bits) and the clients' requests entropy is used only as an extra (it can be useful in case some main sources of entropy fail to provide sufficient real entropy for whatever reason or in the rare case that a good standard crypto random generator isn't available in the execution environment).

see my sample code for gathering request entropy:

$request_entropy=sha1(microtime().$pepper.$_SERVER['REMOTE_ADDR'].$_SERVER['REMOTE_PORT'].$_SERVER['HTTP_USER_AGENT'].serialize($_POST).serialize($_GET).serialize($_COOKIE));

this entropy is then combined with the entropy of the past clients' requests and stored in database:

$query="update `site_vars` set `value`=sha1(concat(`value`, '$request_entropy')) where name='entropy'";

usage 3:

sha1 is used in my crypto random number generator function to get a random integer (random numbers generated by this function are then used in other more useful sub-functions, random_bytes and random_string, to generate random strings/tokens and crypto keys in my program).

see the code excerpts for details:

extract(unpack('Nrandom', pack('H*', sha1(openssl_random_pseudo_bytes(4).$entropy.microtime()))));
    return abs($random) % ($max - $min) + $min;

...

extract(unpack('Nrandom', pack('H*', sha1(fread($urandom, 4).$entropy.microtime()))));
// $urandom is an open file handle to /dev/urandom
    return abs($random) % ($max - $min) + $min;

...

if(function_exists('mcrypt_create_iv') and version_compare(PHP_VERSION, '5.3.0', '>=')) {
    @$tmp16=mcrypt_create_iv(4, MCRYPT_DEV_URANDOM);
     if($tmp16!==false) {
        extract(unpack('Nrandom', pack('H*', sha1($tmp16.$entropy.microtime()))));
        return abs($random) % ($max - $min) + $min;
    }
}

...

extract(unpack('Nrandom', pack('H*', sha1(mt_rand(0, 0x7FFFFFFF).$entropy.microtime()))));
    //mt_rand is only used as a fallback in case other CSPRNGs (openssl_random_pseudo_bytes, /dev/urandom, mcrypt_create_iv) aren't available in the environment
    return abs($random) % ($max - $min) + $min;

Do you know the article If You’re Typing the Letters A-E-S Into Your Code You’re Doing It Wrong? This is basically the same, but with a focus on hashes.

There is a quite important misconception in your system:

you stated "One of its design goals was high security."
and then you start implementing your selfmade algorithms, even stating: "same key is used for enc and hmac; yes i know it is considered bad practice, but not really serious so far"

So, what is your goal here? Actual high security, in a real application? Here a few pointers, if that is actually the goal:

You should probably start by throwing out all those parts, which you designed yourself, and start utilizing proper crypto libraries and the correct primitives. E.g. key derivation functions exist for a reason.
Randomness (which you call entropy) is nothing to be taken lightly. Just because you implemented a system, you can't figure out how to break yourself, doesn't mean it is secure. Use a cryptographically secure random number generator and be done with it.
Key management is actually a quite critical topic, which is overlooked quite often. E.g. depending on your application, it can be bad if the keys are stored in the same location as user data, etc. If you can utilize a crypto library to handle the key management, all the better.

Your own suggestion of replacing MD5 and SHA-1 with a truncated version of SHA-256 would be a step in the correction direction (better without truncation), as it would be a lie to call anything based on MD5 and SHA-1 highly secure. However, this is just a minor step, and your actual problems go way deeper than that.


Why is DDH not hard over $\mathbb{Z}^*_p$? Why is Diffie-Hellman key exchange not hard over $\mathbb{Z}^{*}_p$?

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$.
If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$).
Now, we know that $QR\cdot QR = QR$, $QNR\cdot QNR = NQR$ and $QR \cdot QNR = QR$, where the $\cdot$ operator has the effect $g^a \cdot g^b = g^{ab}$. These identities hold trivially as a QR would be of the form $g^{2k}$ where $k\in \mathbb{Z}$, and so $g^{2k} \cdot g^b = g^{2(kb)}$ which is a QR.
So given a tuple $(g,g^a,g^b,g^c)$, we can check for $g^a$, $g^b$ and $g^c$ whether they are $QR$ or $QNR$, i.e., compute their Legendre symbol.
Note that if this is a valid DDH tuple then you can write it as $(g^a,g^b,g^{ab})$ and if you encounter the cases $(QR,QR,QNR)$, $(QNR,QR,NQR)$, $(QR,QNR,NQR)$ or $(QNR,QNR,QR)$ then it cannot be the case that $ab\equiv c\pmod{p}$, which gives you a distinguisher for the DDH.
More formally, the DDH problem is only hard if for $x, y, z \in G$ we have
$$
|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)|\leq \text{negl}(l)
$$
An adversary $\mathcal{A}$ can adopt the following tactic: check if for the provided $g^a, g^b, g^c$ the above QR/NQR identities hold. If they do, then output $1$. Otherwise, output $0$.
Note that $P(g^x = QR) = 1/2$ for a random $x\in G$. Hence, according to the above identities, the probability of $g^{ab}$ being QR is $3/4$ (which is also the probability of either $g^a$ or $g^b$ being QR). The probabilities above then become:
$$
\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1) = 1
$$
$$
\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1) = \frac{3}{4}\times\frac{1}{2} + \frac{1}{4}\times\frac{1}{2} = \frac{1}{2}
$$
as a valid DH tuple will always obey the QR/NQR identities. Meanwhile, if $z \neq xy$, then the adversary outputs $1$ if by chance the tuple agrees with the identities (so the probability is [prob that either $g^a$ or $g^b$ is QR AND $g^c$ is QR] OR [the same thing with NQR]).
Hence, $|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)| = \frac{1}{2} \nleq \text{negl}(l)$ so the problem is not hard, formally.
If you choose $p$ to be a safe-prime, i.e., of the form $p=2q+1$ with $q$ also prime, however, and you work in the prime order $q$ subgroup, the DDH is hard (then you work in the subgroup of quadratic residues and you will no longer have the above approach to construct a distinguisher)!
An algebraic group commonly used in application of the Diffie-Hellman problem are Schnorr Groups. These are subgroups of $\mathbb{Z}_p^*$ and have the form $G_S = \{h^r \text{ mod } p\ |\ h \in \mathbb{Z}_p^*\}$ where $p=rq + 1$ and $p,q$ are primes. It then follows that the order of the group is $q = (p-1)/r$.
Note that in this case $p,q$ are necessarily odd (aside from the trivial case of $q=2$), which means that $r=2s$ for some $s\in \mathbb{N}$ (ie $r$ is even). This means that all elements are quadratic residuals in $\mathbb{Z}_p^*$ and hence the above distinguisher would not be applicable.
Moreover, a similar attack on DDH can be constructed for cubic, quartic, etc. residuals. Formally, you can construct such a distinguisher for any $k$th residual given $k$ divides the group order. The group order for $\mathbb{Z}_p^*$ where $p=rq+1$, as outlined above, is $p-1 = rq$. Hence, we need to check for $r$th residuals (which don't give any discrimination power as all elements of the subgroup $G_S$ are $r$th residuals) and for $q$ residuals (which aren't useful as that only includes $1$ due to $q$ being prime).
Schnorr groups are selected such that $p\gg q$, resulting in $r$ being big and having a lot of prime factors, making any sort of $k$th residual attack have negligible chances of success for reasons outlined above. Though $k$th residual attacks for large $k$s quickly stop giving any noticeable discrimination power.
But the DDH is not the hardness assumption underlying Diffie-Hellman key exchange, but it relies on the CDHP, i.e., given $(g,g^a,g^b)$ compute $g^{ab}$, which is hard in $Z_p^*$ for appropriate choice of $p$. This is the problem an eavesdropper is faced when it intercepts $g^a$ and $g^b$ to compute the common key $g^{ab}$. Note that an eavesdropper against Diffie-Hellman key exchange will hopefully never see an DDH tuple $(g^a,g^b,g^{ab})$ as otherwise this would mean that the parties would send the exchanged key $g^{ab}$ in clear over the wire, and this would not be a good idea ;)


I need a 64-bit cryptographic hash for 96 bits of data I have a situation in which I need to combine a 32-bit datum, G, and a 64-bit datum, I, to produce a 64-bit datum.  No two tuples with the same I value will have the same G value, and vice versa.  Collision resistance must be very high (data corruption will result if not).

Technically, I don't need encryption, but most decently collision-resistant hash functions happen to come from the field.  Some questions:

I have considered using a cryptographic hash such as SHA-256 and either slicing (i.e., subset of bits) or folding (XOR'ing subsets of bits).

Question 1: is this a reasonable approach (i.e., can anyone recommend
something simpler with comparable collision resistance)?
Question 2: slice or fold?  Folding might help with issues of non-uniform
distribution in the subsets, but does it weaken the result?  I think not,
but I am not certain…

Thank you!

To the responders…  Thank You!

@ChaosInCodes: right – collisions are very problematic, maybe fatal.  This is why I am also soliciting any other ideas about how to do this (i.e., without the use of cryptographic hashes).  The I datum, in particular is sparse (being a composition of a bunch of other, smaller data, including a little slice of G).  I am continuing to work on whether I can recompose (G,I) pairs as a 64-bit datum without using hashes…  Pointers to information on the probability of collisions (given uniformly distributed, random inputs - which I don't really have), that would be helpful.

@poncho: I mean unlikely.

@RichieFrame: thanks, I'll check into these.  As mentioned, I really don't need a cryptographic checksum, just a very good hashing technique.

@fgrieu: OK, the problem I am trying to solve is to represent a filesystem's inode's generation and inode number as a unique 64-bit datum.  The values of I are not unique (by which I mean that at any point in time, an inode points to unique data, but the file system reuses inodes over time); the values of G are also not unique (by which I mean that there are many inodes deployed during a given generation).  The pair (G,I) is guaranteed to be unique, but its too big!

I expect ~billion pairs, and this approach is only workable if the probability of collision is sufficiently low that I will likely retire before the first one occurs. ;-}

The tone of these responses lead me to believe that perhaps a cryptographic hash is insufficient to the need, i.e., may have too high a probability of collision given the input data.  I have some background in data de-duplication, so my head went there, but perhaps it isn't the right approach.

If all that's known about (G,I) is stated in the question, using a hash of the concatenation of G and I, truncated to 64 bits, is a reasonable option (and I see no better one). However the risk that there is at least one collision grows fast with the number $n$ of (G,I). On the (reasonable) assumption that this hash behaves as a random function, this probability of (at least) a collision is
$$p=1-(2^{64})!/(2^{64}-n)!/2^{64\cdot n}\approx1-e^{-n\cdot(n-1)/2^{65}}\approx n\cdot(n-1)/2^{65}$$
The approximation on the right is good when $n$ is less than about $2^{30}\approx10^9$. For $n=10^9$, we get $p\approx2.7\%$. Is that acceptable? You decide.

Late addition: an attacker able to influence (G,I) could do so in a way such as to cause collisions. Against this, instead of a hash, we could use a Message Authentication Code with a secret key; problem becomes, how can a file system hide the key from attackers and still achieve media interoperability?


NTRUEncrypt polynomial $r$ Uniqueness During the encryption process in NTRU, a random polynomial $r$ of small coefficients is generated to bind to the message to obscure it, and this polynomial must be kept secret. Does this polynomial have to be unique per message?

Does this polynomial have to be unique per message?

Yes, if two messages $m_0, m_1$ were encrypted with the same $r$ (resulting in ciphertexts $c_0, c_1$), we would have:

$$m_0 - m_1 = c_0 - c_1$$

This would allow the attacker to directly rederive many of the bits of $m_0, m_1$ (and it gets a lot worse if more than two messages were encrypted with the same $r$.

In addition, if the attacker recovered one of the messages, he can immediately rederive the other.

Bottom line: don't do it.


Finding the n-th root of unity in a finite field I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^{(2\pi ik/n)}$. I have no idea how to translate that into finite fields.

In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.

Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).

To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then:
$$ (x^{(q-1)/n})^n = x^{q-1} = 1 $$
Therefore, $x^{(q-1)/n}$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.

Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j \neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:

Get a random $x \neq 0$ in your finite field.
Compute $g = x^{(q-1)/n}$.
If $g^{n/2} \neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.

This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).

Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.


What is the most important piece of information in a X.509 certificate? X.509 has a structure which contains information like version number, serial number, signature algorithm, issuer, subject name, subject public key, signature of the issuer etc.

However, I'm having an argument between friends because according to them, the public key is the heart of the certificate.

On the other hand, I think issuer's signature (CA) is the most important attribute. This is because basically you can't do anything without having a valid certificate, whereas if public key for some reason is missing, I still think you can digitally sign documents (since it uses private key and not the public one).

Certificate here comes handy because you need the subject's name (signed by youremail@gmail.com") which you can access since you have a valid cert. If you don't have the CA's signature, you can't even digitally sign.

I need to know which is the right answer. Thanks!

As fgrieu says in his comment, the answer to this question is ambiguous; it depends on what you use the certificate for.

You can perfectly trust a certificate, without having a CA signature. A CA signature only signifies that whoever trusts the CA, will also trust your certificate.

The public key however is the way with which the owner of the certificate and key will identify their self with. Therefore, I would say that the public key is more important, because a certificate is useless without it.

  This is because basically you can't do anything without having a valid certificate, whereas if public key for some reason is missing, I still think you can digitally sign documents (since it uses private key and not the public one).

Without the public key, nobody will be able to verify your signature, so your signature might as well be random noise.

  I need to know which is the right answer. Thanks!

As I said, there is no "right" answer here; apart from that you actually need a public key to be in there.


Looking for commutative asymmetric cipher for data matching I need some crypto operation for matching data privately between two peers (let say Alice and Bob). Alice should be able to encrypt her data with Alice and Bob public keys and pass the cipher text to Bob. Bob could not decrypt the cipher text but could match it with the same cipher text produced on the Bob side. As a result Alice and Bob will know which source messages have both of them.

So I am looking for asymmetric cipher which allows to change the order of encryptions providing the same cipher text (I suppose it is called commutative). So given $M$ - plain text message, $pub_1$ - first public key, $pub_2$ - second public key. I need the crypto function $F(message, pubkey)$ with such property:

$F(F(M,pub_1), pub_2) = F(F(M,pub_2), pub_1)$

Rather than using a commutative encryption scheme, I'd suggest looking at private set intersection.  From the description in your first paragraph, it sounds like that's what you're looking for.


Is the polynomial reconstruction problem really "intractable"? In the family of the believed (experts haven't come yet with a solution) intractable problems in cryptography belongs the  Polynomial Reconstruction problem in which an attacker is given $n$ points in which at least $t$ belong to the evaluation of a polynomial $p$ of degree $k$ and the attacker wishes to reconstruct $p$. (where $n>t>k$) The problem has been the basing building block for crypto primitives as public key encryption, block cipher, and oblivious polynomial evaluation.

The reduction for the security proof comes from decoding random reed-solomon codes. My question is the following: Why this is treated as an intractable problem as a very naive idea is to reconstruct the polynomial $p$ by simple Lagrange interpolation after picking up all the ${t} \choose{n}$ elements ?

The polynomial $p$ of degree $k$ can be reconstructed if at least $k+1$ correct points
are known (that is, we know that $(x_i,y_i), 0 \leq i \leq k$ are correct meaning that
$y_i = p(x_i), 0 \leq i \leq k$), and in this
case, Lagrangian interpolation works. If the points are being made available one at
a time instead of all at once, Newtonian interpolation is an even better method for
on-line interpolation.

If an adversary finds out $n$ points of which at least $t > k$
points are correct (though the adversary does not know which
$t$ points are correct), then the adversary can use Reed-Solomon
decoding techniques to determine
$p$ as long as $t \geq \frac{n-(k+1)}{2}$, that is, among the
$n-(k+1)$ "extra points", there are
at least as many correct points as there are incorrect points.
The Reed-Solomon decoding process will also tell the adversary
which of the points are incorrect. Note that the adversary
knows the values of $k$ and $n$ but not necessarily the value
of $t$ but can still use the Reed-Solomon decoding process,
and this process is guaranteed to find $p$ (as well as $t$)
and to identify the incorrect points as long as there are
at least as many correct extra points as incorrect points.

What happens when there are fewer correct extra points than incorrect points?
Well, the adversary does not know this and can launch the
Reed-Solomon decoding process but the process will recover $p$
only in extraordinarily rare circumstances. The process will
find some polynomial $\hat{p}$ but the adversary can readily
determine that this is not the right answer by checking whether
$\hat{p}(x_i)$ equals $y_i$ for most of the points (as it should
for the correct $p$).


Is the idea of a known plaintext attack really that new? As you can probably guess, I just watched The Imitation Game, which hasn't really gotten points for historical accuracy...

During World War II, Turing and his team fret that they can't know the plaintext of the Enigma messages they intercept. In a Eureka moment, it occurs to Turing to try a message that probably contains the words "Heil Hitler."

My question is then: Hadn't it occurred to anyone in the past, say, during the Civil War or World War I, to try something like this to break a code? (I might be mixing up known plaintext and chosen plaintext attacks, please let me know).

No, the idea is much older. Don't trust the movie too far, Turing actually searched for the word "eins" (one) because it was the most common number used. Far more likely to appear than "Heil Hitler" but it doesn't make good screen drama.


Generate PGP keys very very fast Is there a way to generate thousands of PGP keys at a very very fast rate?

I am generating thousands of 3072-bit PGP keys looking like part of a personal research project. Obviously, this is a very slow, CPU intensive activity. I have turned off strong randomization with the --debug-quick-random, am generating them using --batch and maxed out all of my personal CPUs. But this is still not fast enough.

Is there a way to generate perhaps thousands of keys very rapidly? My goal is to get a 16-bit hash collision on the KeyID. I know this is entirely impractical for real security, this is mostly for research purposes. I have not reviewed the GnuPG code, but I am trying to avoid writing any code just yet.

Thanks!

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key)
public_key = timestamp + public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot


Even passwords are vulnerable to hash collision attacks? As stated in this page large documents hashed using md5 maybe vulnerable to collision attacks. My question is even passwords of 6-30 character are vulnerable to such hash collision attacks? If yes, is there any proof available online or any example of two password phrase giving same md5 hash? I googled but of no help!.
Any how I am not going to store password hashed using md5, just asked this question out of curiosity.

Data of more than a few dozen bytes can be vulnerable to MD5 collision attacks, but only (as far as is known) when an adversary can inject (choose) enough data of her choice in both the legitimate and forged version, which is feasible in some important scenarios, including certificate signing. There is evidence this was used by the flame malware, and plausible speculation that it went undetected for years.

No, passwords are not  vulnerable to hash collision attacks in the standard use of a password hash, where the hash is stored instead of the correct password and used to test a candidate password; that's because the adversary is assumed not to know the password, and can not inject material in both hashed messages; it is thus immaterial that in such a standard password hashing application, what's hashed is generally below the threshold where MD5 collisions are known to be feasible.

However, hashed passwords can often be recovered when their hash is known, by a different attack, specifically a brute-force (first) pre-image attack: e.g. an MD5 rainbow table if the password was hashed using MD5 without salt; or, even with salt, enumerating plausible passwords using a password cracker. To defend against these attacks, one should avoid a password hash getting known, and when that can't be insured with high confidence must use a good, purposely slowed password hash, such as scrypt with salt and appropriate parameters. Improving password hashing is an active research topic.

Update: CodeInChaos rightly points in a comment below that even in the standard use of a password hash, an adversary allowed to change password (and perhaps, knowing the salt) could use a password collision so as to select a password such that another password allows access, which she could use to discredit the system to some degree.

Update: Ricky Demer rightly points in comments below that in some Password Authenticated Key Agreement (PAKE) protocols, finding collision on messages involving two different possible passwords can give a useful advantage to the adversary: the ability to check these two passwords with a single query.


Optimal bit-change-probability of the avalanche effect for hashes Avalanche effect:

  The strict avalanche criterion (SAC) is a formalization of the avalanche effect. It is satisfied if, whenever a single input bit is complemented, each of the output bits changes with a 50% probability.

My questions are:

Is a 50% bit-change-probability optimal for any hash or is it just the minimal value so satify the strict avalanche criterion?
What if a hash-algorithm had a 100% bit-change-probability?

Consider a function $H:\{0,1\}^m\to\{0,1\}^h$ (that is, from the set of $m$-bit bistrings to the set of $h$-bit bitstrings). Define $D_n=0^n\mathbin\|1\mathbin\|0^{m-n-1}$ (that is, the $m$-bit "disturbance" bitstring with only bit $n$ set).

By a possible definition, $H$ satisfies the Strict Avalanche Criterion when for each of the $m\cdot h$ pairs $(n,i)$ with $0\le n<m$ and $0\le i<h$, the arithmetic sum of bit $i$ of $H(M\oplus D_n)\oplus H(M)$ computed for all $M$ in $\{0,1\}^m$ is $2^{m-1}$ (that is, exactly 50% of the number of terms summed).

That can be extended to functions with variable-size input (such as usual hashes) by stating that for each input size $m\ge2$ supported, the function satisfies the SAC (Note: when $m<2$ and $h\ne0$, no function satisfies the SAC).

  Is a 50% bit-change-probability optimal for any hash or is it just the minimal value to satisfy the strict avalanche criterion?

Neither.

50% is not the minimal value to satisfy the strict avalanche criterion. For the SAC to hold, the probability that a 1-bit change in input changes any particular bit of output must be exactly 50%, where that probability is computed over the $2^m$ inputs.

The optimal for a cryptographic hash is to behave like a random function, and a random function is extremely unlikely to satisfy the SAC (for $m=2$ that has probability $2^{-h}$, and that goes further down very fast when $m$ grows). If a practical cryptographic hash ($h\ge128$) satisfies the SAC for some $m$ with $2\le m\le50$, that's easily detectable and a weakness in some possible applications. For large $m$ and practical secure hashes, it is computationally impossible to test if $H$ satisfies the SAC or not. Otherwise said, for large messages, a practical secure hash behaves as if it met the SAC for all computational purposes, even though it most likely does not.

Mildly interesting problem: up to what $m$ is it possible to get experimental evidence that a practical hash does not meet the SAC?

  What if a hash-algorithm had a 100% bit-change-probability?

Such function must produce the XOR of its $m$ input bit(s), repeated $h$ times to form a $h$-bit vector, then XORed with a $h$-bit arbitrary value dependent only on $m$. It is not a secure cryptographic hash by any measure. Independently, it does not meet the SAC.


How to prove a cipher resistant to differential cryptanalysis? How do you prove that a cipher is resistant to differential cryptanalysis? It's said that Rijndael has been proven resistance to differential cryptanalysis. How do cryptographers do that?

The design documents for Rijndael explain exactly how the designers proved its resistance to differential cryptanalysis.

Read their submission to the AES competition process, particularly Section 8.2 and the Annex.  To understand their approach, it will probably help to understand differential cryptanalysis and read some of the related literature.  You can find a more detailed explanation in their book, The Design of Rijndael: AES.

You might enjoy the following research papers:

The Wide Trail Design Strategy
Provable Security against Differential and Linear
Cryptanalysis for the SPN Structure