16,808 reputation
12266
bio website
location Paris, France
age
visits member for 2 years, 8 months
seen 3 hours ago

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


3h
comment Hybrid encryption with Textbook RSA
Additional hint: if the use of $m$ in the hint makes it confusing, change that to another letter and it becomes a giveaway.
Apr
16
comment Security of permutation cipher
Among many weaknesses: if $i$ and $j$ are in any segment where only the first permutation changed (including at least $i<255$ and $j<255$), then $c_i=c_j\Longleftrightarrow p_i+i≡p_j+j\pmod{256}$. E.g. "FED" encodes to 3 identical bytes.
Apr
16
comment Is it possible to crack any MD5 hash?
Your question is not answerable: there is no private key in a hash. Also, it is expected that there are several messages that can give any given hash. As pointed by Poncho in the next comment, there is hope if you want the short message that gave this MD5.
Apr
16
comment How can I convert numbers into prime numbers?
You state without reference "Universal hashing gives high density of primes with high probability". I fail to see why, and doubt it. And I fail to see why it would matter, for the input of the universal hash is prime in your method, not the output. -- Trying $p$ until $f(p)=h(x)$ is expected to require $2^{w-1}$ steps where $w$ is the output width of $h$, and thus impractical. -- The method outlined by CodesInChaos seems just fine to me.
Apr
16
comment Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $
Sorry I thought a map was bijective by definition (my math vocabulary in English is less than perfect). I stand corrected.
Apr
16
comment How can I convert numbers into prime numbers?
Addition: the Rabin-Miller probabilistic primality tests has cost in $\mathcal O(\log(n)^3)$ (with the straightforward multiplication algorithm and vanishingly low odds of letting a composite creep).
Apr
15
comment Block cipher and parity of permutation
We do not care to construct a WIDE block cipher with an odd permutation; however this is sometime done in the context of Format Preserving Encryption with small block size.
Apr
15
comment Are AES-256's related-key weaknesses exploitable if it is used to build a hash?
So the successful attacks on AES-256 invalidates arguments/proof of security based on an ideal cipher model, but do not translate into a direct attack that we know, right? -- About the attack explored in your answer: is the ability for the designer of the hash to choose the $IV$ a significant advantage over what users can do: try $M_0$ at random until the resulting $H_1$ has the desired property? And can you detail what's achieved after hypothetically managing to get $IV$ or $H_1$ to the right value?
Apr
15
comment Security of RSA for paranoids with padding?
@Ricky Demer: Yes. SPAKE/ALIKE use something reminiscent (the padded message is random then used to build AES-128 keys, concatenated with the encryption of zero with such a key). See the slides, they are interesting.
Apr
14
comment Turning a cipher into a hashing function
There is a solution to at least the first issue (only 128-bit width) encountered when making a Merkle-Damgård hash with AES-256: a compression function proposed by Shoichi Hirose at FSE 2006. I have opened a question about if the second issue (AES-256 related-key weaknesses) is a practical concern.
Apr
14
comment Are AES-256's related-key weaknesses exploitable if it is used to build a hash?
Yes, with AES, Miyaguchi-Preneel seems more robust: the block cipher is in a known-key setup, rather than chosen-key (Davies-Meyer) or a half-chosen-key (Hirose). However, Miyaguchi-Preneel only gives a 128-bit hash (uncomfortably narrow nowadays w.r.t. collision-resistance), and uses 128-bit blocks rather than Davies-Meyer's 256-bit, making it less efficient by a factor like 2. That would be a high performance penalty to endure if we had reasons to believe attacks exploiting AES related-key weaknesses are likely to forever have cost higher than the expected resistance to brute-force attacks.
Apr
14
comment Are AES-256's related-key weaknesses exploitable if it is used to build a hash?
I notice that one of your paper says from a former one that it has "shown practical attacks on AES-256 in the chosen key scenario, which demonstrates that AES-256 can not serve as a replacement for an ideal cipher in theoretically sound constructions such as Davies-Meyer mode". Can you comment on that?
Apr
13
comment A known-plaintext attack on an LFSR-based stream cipher
Make a table with lines representatives of the successive states, with 4 values on each line: the 3 state bits of the shift register, and its input. You can find what's necessary to fill the table from the output sequence [hint: with a drawing of a Fibonacci (L)FSR, determine how the initial input of the shift register has propagated after 3 clocks]. That table defines the feedback function (which inputs are the state bits, and output is the shift register's input) fully, except for all-zero input. Verify that this function can be built as the XOR of some of its inputs, and identify theses.
Apr
13
comment A known-plaintext attack on an LFSR-based stream cipher
Hints: In a stream cipher, $\text{ciphertext }=\text{plaintext}\oplus\text{keystream}$. Find the keystream. What is its apparent period? What is the minimum number of D flip-flops to achieve this number of states? Assume that number of D flip-flops forming a shift register with a feedback function. How are the initial state and the successive inputs related to the output sequence? Tabulate the feedback function, and check that it can be built with XOR gates, validating the assumption of a LFSR. Cross-check: is the feedback polynomial primitive, and is the period consistent with that?
Apr
12
comment Why are collision attacks important when talking about MAC schemes?
@user54609: 64-bit security against brute force key search is kinda ridiculous nowadays, but a 64-bit MAC is still very strong when the only way to check if it is right or wrong is try on the actual target and that takes 1 microsecond (that figure is unrealistically low even for a direct 10 Gbps Ethernet link): odds of success are worse than 1/500000 per year of continuous attack. Also, it is easy to detect such attacks.
Apr
12
comment Why are collision attacks important when talking about MAC schemes?
@user54609: Yes, this attack works against HMAC with a hash using a 128-bit state, and e.g. allows a forgery of HMAC-MD5 in about $2^{64}$ queries. It does not contradict the fact that HMAC-MD5 remains practically unbroken as far as we know, when MD5 is not secure against collision, as supported by that security argument.
Apr
12
comment Why are collision attacks important when talking about MAC schemes?
@DrLecter: That was not stated again in my last paragraph (now fixed). And it is worth noting.
Apr
12
comment Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?
Would someone care to compose an answer, preferably in zero knowledge for dummies style so that I can catch on?
Apr
11
comment Could RDRAND (Intel) compromise entropy?
Great and very relevant reference!
Apr
11
comment What is the asymptotic complexity of RSA and paillier cryptosystem algorithm?
Welcome to crypto.SE! Some suggestions: A) Do a minimum of research on your own, and summarize your findings in the question. If you stump on something, state what, likely you'll get explanation. B) Confirm you want the time complexity on a fixed-word-size computer. C) Determine if you want the asymptotic complexity for a multiplication algorithm used in cryptographic practice, or a theoretical one; that changes the answer, a lot. D) Ponder the typographical consequence of the etymology of the second cryptosystem in the question.