Reputation
4,122
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
15 28
Impact
~54k people reached

  • 0 posts edited
  • 2 helpful flags
  • 581 votes cast
Feb
4
comment How does a non-prime modulus for Diffie-Hellman allow for a backdoor?
@poncho Perhaps better than picking a 64-bit prime factor for $p-1$ would be to pick a set of high prime powers. Say, $p-1 = 2^i 3^j 5^k$. This would still ensure instant discrete logs with Pohlig-Hellman, but no regular usage of $p-1$ factoring would be able to get at it. You could even make one of the prime factors of $p-1$ be, e.g., $(2^{32}-c)^{16}$ for good measure.
Feb
3
comment How does a non-prime modulus for Diffie-Hellman allow for a backdoor?
As long as the order of the multiplicative group order of each factor $p_i^{e_i}$ is smooth, i.e., whether $p_i^{e_i - 1}(p_i - 1)$ is smooth, Pohlig-Hellman will work quickly. The factors themselves can be arbitrarily large. But this cannot be the case, otherwise the number would be easily factorable with the $p-1$ method.
Jan
21
comment Are there any successful preimage attacks?
Maraca had a pretty catastrophic preimage attack. On the more theoretical side, MD2, MD4, and Snefru have known preimage attacks.
Nov
30
comment Cryptographic operations for NISTP256 can be implemented using montgomery method?
The Montgomery ladder does exist for any group. What is not doable is to work with P-256 in Montgomery coordinates, since as @abejoe correctly points out, Montgomery curves are necessarily of order divisible by 4.
Oct
18
comment What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?
Turtle's high-level structure is also known as the "Russian Dolls" construction, which was analyzed by Patarin and Seurin. It is secure, but requires a lot of key material (cf. §4).
Oct
13
comment Using a product of a series of curve25519 scalars as a private key
Yes; it is perfectly fine to multiply scalars together, but you will have to ensure implementation correctness yourself.
Oct
13
comment Using a product of a series of curve25519 scalars as a private key
Your other question regarding the higher bits is answered here.
Aug
18
comment Why not to use curve over field of $p^m$ with $p > 2$ for ECDSA?
$\mathbb{F}_{p^m}$ can work, but it is a more brittle choice since a larger number of attacks have to be considered. It is not idiotic, but the (speed) advantages had better be worth it. As of right now, the only fields where there are considerable advantages are of the form $\mathbb{F}_{p^2}$ for large $p$.
Aug
18
comment Why not to use curve over field of $p^m$ with $p > 2$ for ECDSA?
Which ECDSA paper is that? The NIST one? If so, it is likely that it restricts to $\mathbb{F}_p$ and $\mathbb{F}_{{2}^{m}}$ because those are the only standardized curves.
Jun
11
comment RSA public key recovery from signatures
Vanilla Python will likely be too slow here. Instead, try Sage or, if you do not want a gigantic package, use gmpy to use GMP for the arithmetic. It will be much faster than Python's native quadratic algorithms.
Jun
10
comment RSA public key recovery from signatures
With $e=3$ it should be nearly instantaneous---the $\gcd$ of two $1536$-bit numbers is pretty cheap. $e = 65537$ takes around 30 seconds in my machine.
May
23
comment Logjam on Elliptic Curves?
The first logarithm requires $\sqrt{\pi n / 2} / 2^k$ storage, where $k$ is, as above, the number of bits defining a distinguished point. For a 256-bit curve, your $2^{60}$ storage bound implies $k \ge 68$, since that is the amount of storage needed for a single discrete log. Bernstein and Lange suggested (eprint.iacr.org/2012/318) $k = 86$ and a precomputation of $2^{86}$ distinguished points---at a cost of $2^{172}$---making individual logarithms computable with $2^{86}$ effort. Reducing $k$ greatly increases the amount of work; I doubt $2^{30}$ speedup would be achievable.
May
7
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
Thanks, changed. Also added a note stressing the importance of padding.
May
6
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
Correct; that applies to the version without the $10^t$ padding. Yasuda notes: "We note that it is the lack of appropriate filling between the message M and the last key K, rather than the usage of a single key, that contributes to this key recovery attack."
May
6
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
Being the envelope MAC was the point! A single key is enough to be secure, though two independent keys are also fine.
May
6
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
OK, changed it to a less confusing formula, that matches Yasuda's paper.
May
6
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
$1$, followed by enough $0$s to pad out to block length. I think it should be intelligible now?
May
6
comment How is HMAC(message,key) more secure than Hash(key1+message+key2)
Right, I got the message padding wrong. Fixed now.
Dec
17
comment N way collision of hashes
The exact work factor is worked out in Suzuki et al: $(n!)^{1/n}\cdot T^{1-1/s}$.
Nov
19
comment Do data-dependent rotations have any advantage over fixed rotations?
Probably. Analysis is still more difficult on data-dependent rotations, and so it may be wise to assume the attacker can force them to have no difference. This is especially the case in hash functions, where the attacker controls almost everything; here's an example. When assuming no differences in the rotations, fixed rotations start to seem like the better choice.