Reputation
3,622
Top tag
Next privilege 4,000 Rep.
Access 'trusted user' tools
Badges
11 25
Newest
 Revival
Impact
~43k people reached

  • 0 posts edited
  • 2 helpful flags
  • 550 votes cast
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.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
Nevermind, I was assuming you had direct access to the points on the twist. Here you cannot use plain rho.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
The complexity for kangaroo is slighly different when taking the negation map into account. You can use rho in this situation, though, like you would in Pohlig-Hellman.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
$\log(\pi/4 l)/\log(4) = \log(\sqrt{\pi/4 l})/\log(2) = \log(\sqrt{\pi l / 2} / \sqrt{2})/\log(2)$. It's the usual Pollard rho complexity with the negation map taken into account.
Aug
15
comment Subverting the key generation step in RSA public key cryptography
This method subverts the RSA public key in several ways, one of which is by embedding part of the secret prime in the modulus itself. The rest can be recovered in polynomial time.
Jun
19
comment Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates
That should work (modulo a few unlikely corner cases). But keep in mind that will still be slower than affine with batch inversions; for a large enough batch, an inversion costs 3 multiplications, and affine coordinates look much better performance-wise than Jacobian, even assuming the DP check is free.
Jan
13
comment Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?
The only thing that comes close to what you are asking is Edlyn Teske's isogeny trick, mentioned in the other question. Apart from that, there is only speculation about unknown weaknesses.
Jan
13
comment Time complexity to solve Discrete log problem
You're right, of course. Given it's little-oh, that factor can actually be any function, as long as it becomes insignificant at infinity input sizes.
Dec
6
comment Why are these techniques not feasible to crack RSA?
It seems I misunderstood what you said earlier. You're correct.
Dec
6
comment Why are these techniques not feasible to crack RSA?
It's actually equivalent to factoring: you can compute $\phi(n)$ quickly from the factors, and you can find the factors quickly from $phi(n)$. No, $d = 1/e \bmod \phi(n)$. This does not result in a fraction, because we are working in modular arithmetic. There are efficient algorithms to do this.