19,453 reputation
12677
bio website
location Paris, France
age
visits member for 2 years, 11 months
seen 5 hours ago

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


Jun
30
comment Does collision resistance imply (or not) second-preimage resistance?
@CodesInChaos: Following your comment, I've been trying to construct a sponge-based hash with capacity $n$, an argument of collision-resistance with effort about $2^{n/2}$, and an explicit second-preimage attack with effort $2^{n/2}$ (rather than a proof of security to effort $2^{n/2}$); but failed. Am I missing the obvious, or is that worth a separate question?
Jun
30
comment Associative standard cryptographic hash function
Probably the simplest collision-resistant answer to the question as currently worded!
Jun
26
comment Convert m-Sequence into a de Bruijn Sequence
@e-sushi: You are looking for x=x>>1^0x8016&-(x&1); to implement the Galois LFSR $x^{16}+x^{14}+x^{13}+x^{11}+1$. This form allows using any polynomial of degree $\mathtt{n}$, if x is at least $\mathtt{n}$ bits, by changing a single constant. The constant is obtained by removing the term $x^\mathtt{n}$ from the poly, and ORing 1<<(n-1-k) for each $x^\mathtt{k}$ term, including 1<<(n-1) for the $1$ term of the poly. E.g. 0x8016 is 1<<(16-1-14)|1<<(16-1-13)|1<<(16-1-11)|1<<(16-1). By contrast, in the formula of this answer (using the Fibonacci construct), each term adds to the code.
Jun
26
comment Is it possible to get better randomness by using multiple PRNGs?
@Stephen Touset: Yes, and in my comment above I'm also making that assumption of seed independence past the first sentence. The rest is to stress that such assumption is NOT enough to ensure that the XOR of the PRNGs behaves at least as well as the worst of the originals in a particular practical test intended to assert a PRNG's quality.
Jun
26
comment Is it possible to get better randomness by using multiple PRNGs?
@Stephen Touset: that's true in an information-theoretic sense, and only with the critical assumption that the PRNGs are seeded from independent sources. However it is possible to devise (bad) PRNGs that individually have output in any particular run indistinguishable from random, but which XOR has horrible properties, even when both are seeded with true random. A trivial example is two identical CSPRNGs modified to entirely ignore their seed input; but it is possible to extend this to make the generators pass many, perhaps any fixed test.
Jun
24
comment Description of signatures with message recovery (as in ISO/IEC 9796-2 and EMV Signatures)
In an EMV context, yes $m\equiv n\equiv 0\pmod 8$ holds, because (for $m$) all messages are bytes, and (for $n$) public modulus has size multiple of 8 (and even 32, perhaps 64) by some (AFAIK unwritten) rule, as demonstrated (AFAIK, only) by the fact that EMV's ISO/IEC 9796-2 padding starts with '6A' (yes that's circular). However, $n\equiv 0\pmod 8$ does NOT hold in a PKCS#1 context. Messages with a number of bits not multiple of 8 are a rarity, but ISO/IEC 9796-2 also covers that.
Jun
23
comment Functions that are only second-preimage resistant?
@otus: yes, $H′(0)=H′(1)$ imply $H'$ isn't collision resistant; that's because from the definition of $H'$ we know a particular $(a,b)$ [that is, $(0,1)$] such that $a\ne b$ and $F(a)=F(b)$. We assume the adversary knows this definition too, and is at least as smart as we are.
Jun
22
comment Description of signatures with message recovery (as in ISO/IEC 9796-2 and EMV Signatures)
Can you restrict to ISO/IEC 9796-2 scheme 1, both message and modulus of size multiple of 8 bits, and implicit use of SHA-1 as the hash (as in the linked paper, and EMV)? If yes, is there anything not clear after reading EMV 4.3, Book 2, Annex A2.1?
Jun
18
comment Length-preserving all-or-nothing transform
@D.W.: The construction that you describe requires 6 hashes, and can at most operate on twice the hash size. In the context I was considering, of formatting the message representative for a 2048-bit RSA signature, and SHA-256, it does not cut it. It is easy to make a 1024-bit wide hash from SHA-256, but the resulting 2047-bit AoNT has 6 rounds, 4 hashes per round, 3 compression functions per hash, for 72 compression functions total. That's non-trivial overhead. And things are worse with AES as a building block. I still think we lack simple and efficient AoNT for wide (>1000 bit) blocks.
Jun
18
comment Length-preserving all-or-nothing transform
Yes; but your answer does not explicitly construct a public random permutation of arbitrary size, from fixed-size primitives. For large size it is not trivial, as shown by the comment proposing a construction using CBC (which is not AoN). $\;$ In fact, a AoNT would be an ideal building block in RSA signature schemes (especially those with message recovery and deterministic), but ISO/IEC 9796-2 scheme 3 seems to uses something lesser, perhaps because a simple yet efficient AoNT is not so easy to build.
Jun
18
comment Length-preserving all-or-nothing transform
@StephenTouset: your construction is not AoN. For example, we can recover $m_0$ from the last two blocks of cihertext.
Jun
18
comment Trial divisions before Miller-Rabin checks?
@noloader: You are right that $\lg$ is used for base-2 logarithm, I (hopefully) fixed the update section in my answer. It remains that ceil( (log(k)/log(2))/2 ) is faulty, and errs quite on the unsafe side below 250 bits, at least compared to table 4.4. I should be ceil( (k/log(2))/2 ) if you want the bound that the HAC derives, and discusses on page 165. $\;$ I'm glad I wrote it is notoriously hard to validate primality-testing code before finding that issue in the question's formula, and you found the (lesser) one in my update pointing it!
Jun
17
comment Functions that are only second-preimage resistant?
Hint: assume a compressing function that satisfies all three properties; tweak it by changing the image of a single element to break collision resistance.
Jun
17
comment Functions that are only second-preimage resistant?
@CodesInChaos: you are right that proving collision resistance implies second-preimage resistance won't help.
Jun
16
comment Trial divisions before Miller-Rabin checks?
I find no reference other that the original question suggesting $t = \lceil(\lg k) / 2\rceil$, and it does NOT seem overkill, or even demonstrably safe: for $k=400$ bits that gives 3 rounds of RM, when common wisdom and the quoted table asks for 7 for $2^{-80}$ confidence. On the other hand, $t = \lceil(\lg n) / 2\rceil$ (which is overkill) would perceivably slow down generation.
Jun
16
comment Trial divisions before Miller-Rabin checks?
I knew using the CRT to generate $p$ such that $p\equiv1\pmod{p_1}$ and $p\equiv-1\pmod{p_2}$ for $p_1$ and $p_2$ previously generated random primes, but did not realize that it could also (or in addition) be used to replace trial division.
Jun
14
comment RSA decrypting of a huge file by parts
If the data is really already encrypted, give us the encryption format used; "RSA" just does not cut it. Else, change the question on the tune of "what would be an appropriate RSA-based file encryption format given that I want to..". In any case, please tell us your security goals; in particular, if it is an issue that an adversary can guess something about the relation between old and new data (including but not limited to: what changed?) [reposted with fix]
Jun
12
comment Compact digital signature for noisy data
@jbms: Yes, that works (provided the ECC scheme adds extra information to the original message, as does Reed-Solomon). The ECC is used in an unusual setup where the added ECC info is never damaged, but that's a minor loss of bandwidth. However the ECCs I know are intended to correct individual bit errors, and would work quite poorly (take a lot of space) for the $M$ consisting of symbols each $b$-bit, because a minor error on one symbol affects many bits, perhaps all (e.g. 127->128 changes 8 bits).
Jun
12
comment Compact digital signature for noisy data
@Ricky Demer: I now understand; thank you! Yes, noisetolerantsignature(M) = sketch's_helper_data(M) || standardsignature(M) works, including with the sketch an ECC (as suggested by @jbms) consisting of an appendix (e.g. Reed-Salomon), if that has error-correction capacity matching $β$. The recovery procedure computes the alleged $M$ from the noisy $X$ and helper data, checks standardsignature(M), and checks $Δ(M,X)\leβ$ where $X$ is the noisy message. We get property 1 regardless of $α$. Optionally we can sign the helper data, or/and the verifier can recompute and check it.
Jun
11
comment Given $n$ bits, how many “truly random” sequences/numbers can be constructed?
What matters to entropy is what the sequence could be, not what it happens to be.