30,946 reputation
557114
bio website bolet.org/~pornin
location Quebec City, Canada
age 39
visits member for 3 years
seen 2 days ago

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


Nov
14
comment Are there practical upper limits of RSA key lengths?
@jug: Karatsuba, Schönage-Strassen and their ilk, are for multiplication of plain integers; for RSA, we need modular multiplications. Even if we optimize the "multiplication" part with a sub-quadratic algorithm, the modular reduction is still quadratic. I am not aware of any modular exponentiation algorithm which goes below $O((\log n)^3)$ complexity. Edit: it seems such algorithms actually exist, see this presentation.
Nov
14
comment Are there practical upper limits of RSA key lengths?
@Paŭlo: it is $(\log n)^2$ operations for a modular multiplication, and there are $\log n$ of them in an exponentiation, so $(\log n)^3$. I do not know where your exponent $4$ comes from. For primality testing, a basic Miller-Rabin test is $O((\log p)^3)$ and you will need to do about 200000 of these (on average), if you select candidates for $p$ and $q$ with some care; so that's roughly the cost of 25000 private key operations. But at least key pair generation can be distributed over several cores / nodes.
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".