32,441 reputation
562124
bio website bolet.org/~pornin
location Quebec City, Canada
age 39
visits member for 3 years, 3 months
seen 2 hours ago

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


Oct
24
comment AES-GCM Disadvantage
One may add a performance issue: the not-too-slow implementations of GCM use tables that exhaust L1 caches on small architectures (like the 32-bit Mips found in cheap home routers). It has been reported that on such systems, EAX mode outperforms GCM.
Oct
23
comment Interpretation of the results of NIST (p)NRG suite
Here it is the other way round. Usually, in statistics, you want to detect a non-random effect (e.g. a correlation between a specific gene mutation and a given illness), so you want a small p-value, that would mean "no way this is pure luck, there must be some correlation". Here we really don't want correlations or biases, so we want big p-values.
Sep
18
comment What is the length of an RSA signature?
That trick can be extended; e.g. you can skip a complete byte (8 bits) if the verifier is ready to compute 256 RSA verifications, while it is trying to guess the missing bits. Maybe more importantly, in ISO/IEC 9796-2, part of the signed data can be embedded "for free" in the signature, so while the signature value has size $n$ bits (or $n-1$ with the trick you describe), the overhead implied by the presence of the signature can be substantially smaller, depending on the situation.
Aug
25
comment Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?
If all possible inputs are known a priori then you can put 64 million entries into exactly 64 million buckets with no collision -- but the mapping will have to know the 64 million entries. And the gist of my answer is that this cannot, in general, be done without using enough ROM or RAM to actually encode the 64 million possible values one way or another.
Aug
12
comment linear computations over bilinear pairings
Two elements in a group are opposite to each other if their product is 1 (or their sum is 0, if you use an additive notation for the group).
Aug
4
comment Point addition equation in projective co ordinates
Yes, you get the same point at the end. That's the idea of non-unique coordinates: you have the choice of representation, but they all stand for the same curve point.
Aug
3
comment Is perfect-forward secrecy achieved with RSA?
One may note that SSL used to support ephemeral RSA keys. It was defined as part of the "RSA_EXPORT" cipher suites, in SSL 3.0 and TLS 1.0 (support was dropped in TLS 1.1). When an RSA_EXPORT cipher suite was chosen and the server's public key length was 513 bits or more, the server had to send a ServerKeyExchange message with a RSA key pair in it. I am not sure many SSL implementations supported it, though.
Jul
15
comment Is RSA of a random nonce with no padding safe?
Using the rightmost (least significant) bits should be safe (the leftmost bits are a bit biased), but the argument is a bit more complex; using a hash function is safer.
Jun
16
comment AES VS PRNG+HASH+XOR
Well, don't forget that when you use a hash function as a stream cipher, you are actually trusting two "pieces of software": the hash function itself, and the construction which turns it into a stream cipher. Either may be subject to design and implementation weaknesses.
Jun
12
comment which of these is more secure (bcrypt vs srp)
@owlstead: there are two distinct points: 1. we don't want to store on the server something which is "password equivalent"; 2. the complete processing, from the password to whatever is stored on the server, must be proper "password hashing" with iterations and salts. You can have that with PBKDF2(password) computed on the client side, and SHA-256(PBKDF2(password)) stored on the server. That way, the server-side operation is very fast, and stealing the server's database still does not grant easy entry.
Apr
22
comment Use cases for CMAC vs. HMAC?
Beware: MD hash functions like SHA-1 are built out of a block cipher, but with the data as key, which apparently allows for better bandwidth. At least we can empirically notice that the SHA-3 competition yielded algorithms which are quite faster than all AES candidates on the same hardware. Even AES-based SHA-3 candidates (e.g. ECHO) turned out to be quite faster than AES itself on the same machine.
Apr
15
comment Can ECDSA signatures be safely made “deterministic”?
RFC are immutable; once published they never change.
Apr
13
comment Perfect Forward Secrecy in TLS
The "RSA" in "DH-RSA" qualifies the public key of the CA which issued the server's certificate. From the point of view of the client, a "DH-RSA" cipher suite means: "I want the server to have a certificate with a DH public key, and I am ready to use RSA to validate that certificate". This was supposed to be used in case a server had several DH certificates, signed with either RSA-based or DSA-based CA: the server would then choose the certificate for which the client had relevant support. This has never worked well in practice (but everybody does RSA anyway).
Apr
3
comment Should we MAC-then-encrypt or encrypt-then-MAC?
@Clément: the confusion comes from the widespread (but wrong) habit of calling MAC "signatures". In fact MAC and signatures are very different things used in very different contexts. Sign-then-encrypt protocols also use a distinct encryption key for each message, which nullifies all padding oracle attacks; and the signature is meant to serve as proof (e.g. in a trial), so it MUST be applied on the plaintext message. In MAC+encrypt contexts, the same symmetric key is often reused, and there is no "proof" requirement.
Mar
27
comment Difference between lightweight, online and low memory Authenticated Encryption schemes
One may also note that there are "semi-online" schemes where the size of the input (but not the contents) must be known from start (e.g. CCM).
Mar
19
comment Efficiency of computing $e(P,Q)$ Vs $g^a \pmod{p}$?
No, it is not always defined over a supersingular elliptic curve. It is defined overs "curves of low embedding degree". Supersingular curves have a low embedding degree, but are not alone in that category. However, parts of the computation must occur with elements from a field which is large enough to resist discrete logarithm (DLP, not ECDLP), and that's quite larger than what is used in normal elliptic curves (say, 1200 bits instead of 200), and that means higher computational cost.
Mar
17
comment Elliptic Curves of different forms
It is intended. In all the rest of the message, we talk about curves in $\mathbb{F}_p$ for some prime $p$. However, the Montgomery ladder has also been adapted to curves in $\mathbb{F}_{2^m}$ ("binary curves") with the same expected characteristics (efficient AND side-channel resistant), and yet the OpenSSL implementation of that ladder on binary curves turned out to leak information. This highlights the idea that having a curve amenable to leak-free implementations does not preclude the existence of an implementation which still leaks heavily.
Feb
8
comment Is there a technique to confirm that a given large integer value is a product of two primes?
@ColeJohnson: actually the OP does not want to distinguish between prime numbers and composites (that one is easy); he wants to distinguish between composites which are the product of exactly two primes, and composites which are products of three primes or more (and for that one, we don't know of any method which is faster than actually factoring the integer, at least partially).
Feb
6
comment What is a Non-Interactive Zero Knowledge Proof?
"Zero-Knowledge" has a precise definition. This MAC protocol is not ZK (though it uses non-interactive ZK-proofs internally).
Feb
5
comment Is MD5 second-preimage resistant when used only on FIXED length messages?
Mmh... optimized Shabal should totally beat optimized SHA-256 into the dust on small ARM platforms (like 3x faster). At least so say my measures. A usual performance-killer is when the code is "too much unrolled" and does not fit in L1 cache; so some tweaking is in order. sphlib (again self-promotion) has optimized C code for many functions, and it has a "small footprint" compilation option which can help a lot on architectures with small L1 cache.