31,736 reputation
560119
bio website bolet.org/~pornin
location Quebec City, Canada
age 39
visits member for 3 years, 1 month
seen 11 hours ago

Cryptographer, programmer in several languages (C, Java, several assemblies, Pascal, Forth...). I also have a life.


Nov
14
answered Are there practical upper limits of RSA key lengths?
Nov
13
revised Linear Cryptanalysis
rewrote text to phrase it as an actual question
Nov
13
comment Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
@Ricky: if we knew how to handcraft data blocks specifically to trigger a SHA-256 collision, with better success than with random blocks, then this would be advertised as a break on SHA-256. No such break is currently known on SHA-256. Current methods for attacking MD5 and SHA-1 appear unlikely to apply to SHA-256 (this has been tried).
Nov
12
comment What is pre-image resistance, and how can the lack thereof be exploited?
Preimage resistance is needed for time stamping RFC 3161, an combining time stamping with hash trees (as in ERS) opens the possibility of "multi-target preimage attacks" in which you want to find one preimage for any hash value among a rather large set of hash values, which is somewhat easier (down to $O(\sqrt{N})$ for a hash value set of size $O(\sqrt{N})$).
Nov
12
comment What is pre-image resistance, and how can the lack thereof be exploited?
There are no known preimage (or second preimage) attacks on MD5 or SHA-1. There is a theoretical preimage attack on MD4(complexity of $2^{102}$) and also an attack on MD2($2^{73}$).
Nov
11
comment Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
@poncho: $2^{-60}$ per day. So $2^{-120}$ is the probability of encountering two gorillas the same day. You can view it with a time frame: on average, you will meet a gorilla every $2^{60}$ days. You will get a SHA-256 collision every $2^{76}$ days (there was a mistake in my estimate, so 65000 gorillas, not 250000)(assuming you regenerate the $2^{90}$ 1MB blocks every day). So you really get $2^{16}$ gorillas for every collision -- but not in one go, as a massive gorilla army attack ! (that would be spooky)
Nov
11
revised Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
fixed probability of collision (2^{-76}, not 2^{-78})
Nov
11
answered Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
Nov
11
answered Linear Cryptanalysis
Nov
10
comment Is it reasonable to assure that p-1 and q-1 aren't smooth?
@fgrieu: to be precise, testing a given $p-1$ (from a random prime $p$) for smoothness is expensive, while _generating a $p$_ specifically for $p-1$ to be non-smooth is relatively easy.
Nov
9
answered How does one provide a secure and authentic communication channel?
Nov
9
comment Is it reasonable to assure that p-1 and q-1 aren't smooth?
@Paŭlo: you can choose primes that way; as fgrieu points out, this is what NIST recommends for a 1024-bit RSA modulus. But this will not buy you much with regards to security: it is a gain only in the situation where $p-1$ is feasible (possibly for one key in a million) but ECM is not. Since one round of ECM is roughly 10 times more expensive than $p-1$, this is a bad situation anyway: a factor of 10 is not a large security margin.
Nov
9
revised Is it reasonable to assure that p-1 and q-1 aren't smooth?
fixed size of prime factors (512-bit for a classical 1024-bit RSA modulus)
Nov
9
answered Is it reasonable to assure that p-1 and q-1 aren't smooth?
Nov
9
comment How key materials are generated in SSL V3 from master secret
@user5507: the 3DES specification says that the key is a 192-bit words (three 64-bit DES keys). If you follow the specification, you can see that 24 of these bits are totally ignored by the algorithm, so the effective key size (with regards to exhaustive key search) is 168 bits; but the standard key must still be an array of 24 bytes. The "ignored" bits were supposed to be parity control bits (one parity bit for every seven "used" key bits) but nobody bothers setting or controlling them.
Nov
9
comment How much would it cost in U.S. dollars to brute force a 256 bit key in a year?
@Joren: historically, AES has 128-, 192- and 256-bit keys because some inflexible US military regulations mandate the use of three distinct "security levels" (under the assumption that "really secure" cryptosystems are necessarily slow -- which was true in the 1930s, but not anymore). The three key sizes are enough to satisfy these regulations; but nobody said that the lower level had to be weak ! Nowadays, the 256-bit key size is rationalized by talking about quantum computers, but that's an afterthought.
Nov
9
awarded  Nice Answer
Nov
8
comment How much would it cost in U.S. dollars to brute force a 256 bit key in a year?
@Briguy37: I cannot prove it, but some smart people can. Roughly speaking, if we can break a cipher with an $n$-bit key in less than $2^{n/2}$ operations on a quantum computer, then we can break it in less than $2^n$ operations on a classical computer. It is quite technical, but a part of the problem is that even if you have a superposition of many states, the "filtering out" part to get a classical result (a definite 0 or 1) is constrained and cannot be done "at will".
Nov
8
comment How much would it cost in U.S. dollars to brute force a 256 bit key in a year?
The bit about a quantum computer with 14 qubits being able to "try all combinations of 14 bits in one operation" is incorrect. It is a very tempting assumption (a view of quantum computers as zillions of computers all running in parallel through the magic of quantum), but it is wrong -- otherwise, a QC with 256 qubits could break a 256-bit key in time 1. QC does offer (theoretically) a performance boost on exhaustive search, but not to that point: it can reduce a space of size $N$ to $\sqrt{N}$ (hence 256-bit key search with a QC should be as hard as 128-bit "normal" key search).
Nov
8
comment How much would it cost in U.S. dollars to brute force a 256 bit key in a year?
There is something wrong with the figures above. If a "machine" can do $10^{14}$ decryptions per second (a very optimistic figure, by the way), this translates to about $3.2*10^{21}$ decryptions per year, not $3.6*10^{55}$. There is a lost factor of $10^{34}$ here -- also known as "sixteen billions of billions of billions of billions of billions of billions of billions of billions of billions of billions".