Thomas Pornin
Reputation
43,735
134/100 score
 Apr 23 comment What is the fastest block cipher in the (Intel) world? On a Core2, Kasper and Schwabe implemented AES at 7.59 cpb, which is substantially better than 11 cpb. This implementation runs 8 instances in parallel, which is fine for CTR, not so much for CBC encryption (CBC decryption can be done in parallel, though); as an added bonus, it is constant-time. Apr 21 comment Unknown cipher. Anyone recognizing what it could be? I'm voting to close this question as off-topic because this is not, in fact, about cryptography. Apr 21 comment Unknown cipher. Anyone recognizing what it could be? Time to learn a new trick: Base64. Apr 19 comment Is there a theorem to determine the elliptic curve parameters based on the group order? Take care that these curves have embedding degree 2, so they are much weaker than usual curves for "normal sizes" (e.g. 256 bits). This is a nice curve if you want to use a pairing and know what you are doing. Apr 18 comment understanding a length extension attack @MehranTorki: the length which is encoded in the padding is the length. Not "the length modulo the block size". It is a multiple of 512, but you must still know which multiple of 512 it is. Is it 512, 1024, 1049088? Apr 18 comment understanding a length extension attack @MehranTorki: to actually compute SHA-1 of m||p||z you need to process m||p||z||p' where p' is the padding that corresponds to the length of m||p||z. You don't have to know m||p because you (as the attacker) start from the known hash value (SHA-1 of m) but you still need to assemble a proper p', and that entails knowing the length of m||p||z -- which basically requires knowing the length of m within a few bytes. Apr 18 comment understanding a length extension attack @MehranTorki: to complete the hash computation, the attacker must append its own padding, that encodes the length of m||p||z, so the attacker must know the length of m||p. Thus, he must know the length of m at least approximately (within one block of the true length). Apr 15 comment What is necessary for generating an elliptic curve? Classic implementations of EC will be cubic, just like RSA (so a 2048-bit curve will imply computations 512 times slower than a 256-bit curve). You can go down to quadratic if you limit exponent size (you work in a 256-bit subgroup of the whole curve) but then generating the curve with such a subgroup will be very challenging (not counting usage issues such as point validation). With a special-format prime you can gain some cycles (Karatsuba for n*log n multiplications) but it won't show up that much for that kind of operand size. Apr 14 comment What is necessary for generating an elliptic curve? The formulas above work only for Koblitz curves, which are very few, and, arguably, won't be generated -- they are already there, so to speak. Also, with a non-prime $m$ (and $m = 2048$ is certainly non-prime), this necessarily implies that there will be non-trivial subgroups, which is harmful to security. Apr 11 comment Is GCM still recommended? A main reason is that proper generation of random values is one of the hardest problems when implementing crypto on embedded devices -- in particular because the quality of the randomness cannot be really tested. Apr 11 comment Inserting a backdoor into a cryptographic hash function I came up with that example by my own thinking (I was initially looking for a way to make a hash function based on elliptic curves and with a security that could reduced to that of discrete logarithm). I am not aware of any publication of that construction, other than this answer (whether a StackExchange answer counts as "publication" is another question). Mar 26 comment How were the DES S-box values determined? I found it back on the Internet Archive Wayback Machine. Feb 29 comment How to check that you got the right key when brute forcing an encryption? In RSA the public key consists in two integers, the larger of which is the "modulus". It is a non-prime integer. If you know the prime factors of the modulus, then you know the private key, because these prime factors are the private key. Of course, obtaining the prime factors is hard, to the point that it is infeasible if the modulus is large enough -- which is why we can make the modulus public: it does not reveal the prime factors. Feb 17 comment Layman's explanation of encryption backdoors To be precise, backdoors in PRNG offer plausible deniability because these things are hard to do properly, so if the backdoor is found, the public relations damage is more easily contained by claiming mere incompetence. Jan 29 comment How does one calculate a primitive root for Diffie-Hellman? @Broseph: actually $q$ needs to be more than $2t$ bits long. The reason is that a discrete logarithm can be broken in two ways: either generically (based on the size of $q$), or with index calculus (based on the size of $p$). Index calculus is sub-exponential, meaning that you must make $p$ much bigger. In practice, to get "80-bit security", you need $q$ to be at least 160 bits, and $p$ should be at least 1000 bits. If you choose $p = 2q+1$, then the criterion on $p$ is the one that matters (for an 1000-bit $p$, a 999-bit $q$ is overkill, but you need a $p$ that big anyway). Jan 23 comment ECDSA Compressed public key point back to uncompressed public key point @Myath: in binary curves it is a bit more complex to explain, but a rather efficient compression method still exists. I have updated my answer with some extra explanations. Jan 3 comment Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5? @Myath: ah no, that's the tricky point. If the server proceeds with a random key in case of bad padding, an inconsistent Finished does NOT reveal that the padding was bad -- maybe the padding was good, and the server merely used whatever pre-master secret it thus obtained (and is unknown to the attacker). Nov 5 comment Can ECDSA signatures be safely made “deterministic”? 32 bytes, so 256 bits. There are roughly 2^256 valid signatures for a given message and private key. They correspond to the roughly 2^256 possible values for the internal value k (the one which is supposed to be generated randomly in "standard ECDSA", and is generated deterministically in deterministic ECDSA). Nov 1 comment Is it possible to reduce the size of an RSA key? Since a 2048-bit RSA key is commonly said to be "112-bit equivalent", we could even lower the seed length to 112 bits with no loss in security. We may even scrape a few bits because each try in brute force attack would require, on average, a few hundreds of GCD with big integers, and that's not exactly cheap. On the other hand, take note that regenerating the key from the seed will be rather expensive, likely intolerably so in many embedded systems. Oct 11 comment Weaknesses of RFC6628 We can add that for all password-based authentication protocols, what the server knows must allow for offline dictionary attacks, since an attacker who could get a complete snapshot of the server could simulate a client and a server on his own machines, and see when the simulated server is content with the password provided by the simulated client. This is rather unavoidable; thus, it is not a vulnerability of SRP specifically, but rather a vulnerability of authenticating clients with passwords.