16,773 reputation
12266
bio website
location Paris, France
age
visits member for 2 years, 8 months
seen 1 hour ago

I'm an engineer with experience in applied cryptography, in particular in Smart Card systems.


Mar
21
comment Why is DDH not hard over $\mathbb{Z}^*_p$?
@user2771151: My reading is that the title and body of the question do not match! A distinguisher for the Decisional Diffie–Hellman problem over $\mathbb{Z}^*_p$ can be built from DrLecter's remark, but that does not break Diffie-Hellman key exchange over $\mathbb{Z}^*_p$, especially if $(p-1)/2$ is prime and $p$ is wide enough (thousands bits).
Mar
21
comment Entropy when iterating cryptographic hash functions
I asked the question on math.se, with reference to this answer.
Mar
20
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
HMAC_SHA256(message,key) has a security proof; we do not have a ready-made one for SHA256(key1+message+key2). That's quite an argument. That said, for reasons similar to HMAC_SHA256, SHA256(key1+message+key2) intuitively seems quite strong: there's a key1 initially, making collision hard; then a final key2, further increasing security. However the lack of alignment to block boundary in SHA256(key1+message+key2) makes it quite hard to devise a proof.
Mar
20
comment Entropy when iterating cryptographic hash functions
@Stephen Touset: the question would be more general if it asked the entropy in $H^i(x)$ with $x$ uniform, for some hash $H(x):\{0,1\}^{n}↦\{0,1\}^{n}$, as instantiated for $n=128$ by $x↦H(x)=\operatorname{SHA-256}(x)\mid_{128}$. In fact, that's what the present answer is about. It would be fine with me if the question was changed to that (I can remove my comments to the question, which only are about the different location of the truncation).
Mar
20
comment Distinguishing Attack on CBC-MACs
For why odds of collision are better than 50% after $2^{(n+1)/2}$ queries but not $2^{n/2}$, study the birthday problem, focusing on the case of a large set. Note: Here, $2^{(n+1)/2}$ is written $2^{(n+1)/2}$
Mar
19
comment Probability of an ed25519 selective forgery?
"astronomical" is in the right ballpark when trying signatures at random. Penrose estimates the number of baryons in the observable universe to be of the order of $10^{80}$ (1 followed by 80 zeroes), we are talking more zeroes, but not many time more zeroes.
Mar
19
comment Probability of an ed25519 selective forgery?
The question is closer to well formed. However Probability in the title and trials in the body of the question suggests an approach where signatures are tried at random until one is acceptable, and that it is asked the (average) number of trials for that strategy to succeed. That number is way to huge for that attack to be worth practical consideration. There are much better attacks to selectively forge ed25519, starting with the obvious one (also the best known AFAIK): finding the private key from the public key using parallelized Pollard Rho, which then allows signature forgery.
Mar
19
comment Probability of an ed25519 selective forgery?
Your intuition is right. In cryptography, we assume a malicious adversary. When dealing with signatures, we assume the adversary is trying hard (including with a plausible number of parallel processors) to forge a signature without the signing key. By design, that should not be possible, including in some rather extreme scenarios, like: the adversary chooses billions of messages and can obtain their signatures from a rightful signer; that should not allows making any extra signature for any message, no matter how senseless. In modern systems like ed25519, there's some level of proof of that.
Mar
19
comment Probability of an ed25519 selective forgery?
There's not an infinite amount of parallel processors. I try dealing with real issues.
Mar
19
comment What is the importance of the $r$ and $c$ values for the Sponge Construction?
I love that drawing, worth the proverbial thousand words! @user3201068: The state/water capacity of the sponge is $s=r+c$ bits. $r$ is the amount of entropy/water that enter/exit the sponge at each round/press of the sponge. $c$ bits are out of reach of the adversary/remain in the sponge when pressed, that is A) impossible to put in a particular state with odds better than random: B) unknown if the initial state is unknown as assumed in the Random Oracle model.
Mar
19
comment Randomness test question from FIPS 140-1 and comparison with 140-2
@user3428187: Testing the raw source is very useful, especially if the source is in the wild (as in a Smart Card or HSM): adversaries do all king of creative things like immerse the source in a liquefied gaz, or/and inject a signal they control at the detector of the source (with the actual source frozen, that can be as simple as adding a square wave signal to the power supply). It is much harder to detect that after the VNE than before, especially if the ratio of input/output bit of the VNE is not available (that ratio should be close to 4 for a VNE receiving a fair input).
Mar
19
comment Entropy when iterating cryptographic hash functions
One critic: I do not see that that $f_{i+1}\approx1-e^{-f_i}$ takes into account the fact that the same function $F$ is iterated. Granted that makes no significant difference for small $i$, but I see no argument that it extends indefinitely (in particular, past the stage where most $n$-bit inputs have reached a cycle).
Mar
18
comment Problem implementing MixBytes functionality in Groestl
My only functional change is replacing == with != to match the C code. Each mulz is performing multiplication by constant z (that is, the functional equivalent of z additions) in $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ (that comes from 0x1b).
Mar
18
comment Meet in the middle attack - message and key
In addition of 8 aligned bytes of known plaintext, this attacks requires the ability to check which of about $2^{48}$ candidate keys are correct. This can be accomplished with about 6 other bytes of known plaintext (not necessarily aligned).
Mar
18
comment Problem implementing MixBytes functionality in Groestl
You have the test in mul2 reversed. As an aside, the unsigned right shift in Java is >>>, not >> as in C, but in the context that makes not difference. Try public byte mul2( byte b ) { return ( byte )((0 != (b>>>7))?((b)<<1)^0x1b:((b)<<1)); }. Ah, and this is just test code, not intended for actual use, right? Because the C code you start from is not intended for actual use, and Java is a dubious choice for low-level crypto.
Mar
18
comment Purpose of outer key in HMAC
This newer reference New Proofs for NMAC and HMAC: Security without Collision-Resistance (M. Bellare, Crypto 2006) gives an argument that HMAC is secure even if the compression function in the underlying hash has properties insufficient to make the hash collision-resistant. Independently: I like this intuitive argument that the outer hash kind of re-enciphers the result of the previous one; much like adding rounds in a block cipher, that makes recovering the key or otherwise distinguishing results from random much harder.
Mar
18
comment Why concatenate the key a second time in HMAC?
silly me: I answered a clear duplicate.
Mar
18
comment Randomness test question from FIPS 140-1 and comparison with 140-2
@user3428187: Indeed a Von Neumann Extractor eases passing tests with FIPS 140-2 thresholds, but beware: A) you need to avoid hanging if the source stalls; B) a source that periodically stalls and restarts with a mildly complex fixed pattern may pass; C) the source's throughput is divided by about 4 (of course you must not use the raw source if it is tested after VNE). I rather recommend staying with FIPS 140-1 thresholds if the false positive rate REALLY is acceptable (which is hard to ascertain if your source is going to be mass-manufactured or/and used in diverse conditions).
Mar
17
comment Randomness test question from FIPS 140-1 and comparison with 140-2
@user4982: If a statistical test with low odds of false positive can be redone automatically in case of failure, even once, the original threshold becomes all but pointless. And if it is the case that some automatic recovery procedure is possible, I do not see it mentioned.
Mar
17
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
After hesitations, I chose this for the bounty, rather than the excellent and more intuitive other candidate proof, because D.W.'s answers centers on a simple and robust lemma, and I found it less difficult to try to verify the proof (I'm at least confident that if I missed something, it must be minor and repairable locally).