Re: Using SSL private key for cookie's HMAC

[Jason Coombs PivX Solutions <jcoombs () pivx com>]

Peter Conrad wrote:
> erm... factoring is better than brute force, isn't it?

If you've achieved the improbable already by precomputing all possible 
values of n given every possible prime p and q then all you have to do 
is a database lookup for n and you know its prime factors.

Which is more difficult, to factor n quickly when you find out what it 
is, or to locate n in your precomputed product-of-all-primes dictionary?

Of course your point is that it should be simpler to factor n than to 
precompute a multiplication table of all possible prime values p and q.

The difference between the two approaches is that in factoring n, every 
step taken that is not the correct result is a waste of time with 
respect to future cryptanalysis, while every step taken in precomputing 
a prime product lookup table is a precomputed solution to a future 
potential cryptanalytic factoring problem.

Conceptually I prefer to explain the problem as one that has a simple 
and direct solution that does not require factoring, where we only have 
estimates of how long it might take to complete the job given different 
approaches to factoring large numbers, but instead requires only simple 
forward multiplication, which we know is easy but will take enormous 
computing power. The factoring approach leaves people with the sense 
that the attack can only start once they generate and use their key pair 
in the real world, so there is a race against time (in principle) and 
the solution to that problem is key rotation.

My preferred multiplication table precomputation argument demonstrates 
that your key pair is already being cracked, before you even generate 
one, if anyone is bothering to massively precompute n and store it along 
with p and q.

Really this is just an overly-simplified rhetorical approach to 
factoring a specific product n by determining them all in advance.

If you're going to break codes, you may as well break them all at once 
to conserve energy, and then publish the lookup table for all to see.

Regards,

Jason Coombs
jcoombs () pivx com