19,756 reputation
12779
bio website
location Paris, France
age
visits member for 3 years
seen 5 hours ago

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


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.
Jun
11
comment Attack on a key-exchange,symmetric-key cryptography protocol
@user3283751: Other that the difficult article I quoted, no I do not have a formal definition of DY. But intuitively: without a common time reference, the best a secure protocol authenticating Bob to Alice can do, is ensure that Bob was part of the protocol at a moment in time later that the first message Alice sends in the normal protocol. A replay of an earlier session to Alice that works using past involvement from Bob would break that. But e) is NOT among that because Bob is actively involved at step 2' of attack, AND that's after Alice started the protocol form her standpoint at step 1.
Jun
9
comment Attack on a key-exchange,symmetric-key cryptography protocol
@user3283751: in e), the adversary is relaying unmodified messages to intended recipients, and impersonates as Bob to Alice by making Bob part of the protocol; this is NOT an attack in the Dolev-Yao model, and is unavoidable with common networks like Internet. In Ricky Demer's reflexion-to-different-instance attack, Bob is impersonated though not involved, therefore this is a valid attack in the Dolev-Yao model. This is avoidable assuming $E$ is not malleable [for example, by using a different $K_{BA}$ when Bob initiates the connection, or including identity aside $nounce$ in steps 2/3].
Jun
9
comment Attack on a key-exchange,symmetric-key cryptography protocol
@user3283751: It works enough to allow Mallory to authenticate as Bob without Bob, arguably breaching "bilateral authentication" of steps 1/2/3. My reading of Danny Dolev and Andrew C. Yao's article "On the Security of Public Key Protocols" [IEEE Transactions on Information Theory, 1983] is that it counts as a valid attack. But I'm getting tired of making sense out of that problem, poorly worded at least when re-purposed for audience that did not attend the course; have deleted my over-detailed answer; and will move on.
Jun
9
comment Attack on a key-exchange,symmetric-key cryptography protocol
The more I think about it, the more I'm convinced Ricky Demer has the best answer, and the problem's author considers that $\;$ A) a reflexion attack is not a man-in-the-middle attack; $\;$ B) It is not worth stating that $E$ is non-malleable encryption, because that's what the Dolev-Yao model applied to symmetric cryptography considers, even though many common secure encryption schemes are malleable and would make the protocol insecure.
Jun
8
comment Security of a security protocol for key exchange, using symmetric-key cryptography
Yes, the index in your answer is consistent with what instance of Alice generates $k_1$ and $k_2$. $\;$ However the original statement numbers $k_1$ and $k_2$ in order of appearance rather than according to who generates them, and due to that change in convention, when matching the question and the answer, $k_1$ of the question matches $k_2$ of the answer, and vice versa, in every 4 occurrences. One option that would reconcile the conventions would be to have $A_2$ the initiator of the exchange.