Subject: [MSEC] RSA signature distributed key cracking attack

From: George Gross <[email-masked]>
Date: Thu, 18 Nov 2004 15:07:38 -0500 (EST)

Hi Brien,

	I was reviewing the v03 draft, and it is certainly very improved
over earlier editions. I think it is largely ready to go proposed
standard. However, while reading section 2.1 that discusses key strength,
I thought about the possibility of the following attack. I don't know if
anyone else has previously identified something along these lines:

	Suppose that an adversary has managed to install an agent program
on a large fraction of the secure multicast group's endpoints. For
example, such an agent program could be distributed via an e-mail virus or
by leveraging the multicast group's routing infrastructure itself. The
agent program would use some distributed algorithm to focus each
compromised endpoint's key cracking efforts on a distinct subset of the
RSA signature private key solution space. Once an agent program broke the
private key, it would unicast the solution to the adversary.

For a large scale group, on the order of 10**6 or 10**7 compromised
endpoints, this parallel cracking effort could yield a noticable reduction
in the key's useful lifetime.

	Although I have not implemented this attack, it seems technically
feasible in principle. The question is, does this hypothetical attack
warrent an adjustment in the section 2.1 text offering key strength
guidelines? The rev'd text could indicate that key strength may need to be
set stronger as a policy for those large-scale groups that are considered
at risk for this attack.

thoughts?

br,
	George

_______________________________________________
msec mailing list
[email-masked]
http://six.pairlist.net/mailman/listinfo/msec

---

From: Brian Weis <[email-masked]>
Date: Fri, 19 Nov 2004 08:59:25 -0800

Hi George,

You bring up a good point. I became aware of the possibility of 
distributed attacks during my research into RSA keypair strength, which 
was necessary in order to write section 2.1. It has been considered 
carefully. 

The most promising method known to find an RSA private key (using 
cryptanalysis) is to factor the modulus. The best known method of 
factoring is some variant of the Number Field Sieve (NFS) algorithm. I'm 
not a cryptographer, so I know that getting too specific here is going 
to get me into trouble. But I'll try to generally describe how NFS works.

There are two phases to NFS: a sieve phase and a matrix reduction phase. 
The sieve phase can indeed be distributed in the way you describe. In 
fact, the solutions for the last several RSA challenges employed a 
distributed technique for this phase (although they did not use a virus 
form of distribution). But the matrix reduction phase is different -- it 
requires a  very large amount of memory. In some cases, the amount of 
memory required is more than the amount of memory a 32-bit processor can 
address! There is no known way to efficiently distribute all of that 
memory and still perform matrix calculations at modern processor speeds. 
The matrix reduction phase therefore is the gating time factor in 
factoring the modulus. In summary, an attacker still needs a fast 
dedicated processor, with much memory, and cannot simply rely upon 
borrowed machinery to perform the full task.

The minimum real time needed to factor a modulus is roughly the maximum 
amount of time a keypair should be used. The references in Section 2.1 
describe some formulae that can be used to make educated guesses as to 
the minimum real time needed to factor a modulus. This was the basis for 
my numbers in Table 1.

However, because so much is based on "educated guesses", I was advised 
by Scott Fluhrer to reduce the recommended times significantly (e.g., in 
case it is discovered that the matrix reduction phase *can* be 
parallelized). So the numbers in Table 1 of the I-D should be considered 
to be extremely conservative values at this point in time.

Thanks,
Brian

-- 
Brian Weis
Advanced Security Development, Security Technology Group, Cisco Systems
Telephone: +1 408 526 4796
Email: [email-masked]

---

From: George Gross <[email-masked]>
Date: Fri, 19 Nov 2004 10:06:19 -0500 (EST)

Hi Brian,

	this was an insightful summary of the problem domain. Given what
you've described, I wonder if the adversary simply has to have the agent
program at each of the compromised group endpoints forward their NFS
computations to the adversary's super-computer for the matrix reduction
phase. I'll grant you, this extra requirement becomes a much harder attack
to orchestrate without detection ;o)

So, the section 2.1 table 1 already has been adjusted for the prospect of
the attacker having to wait for a sequential matrix reduction computation
to complete.

FWIW, would you consider adding a qualifying statement that says the
solution time estimate is dependent on matrix reduction algorithm's state
of the art being a sequential algorithm, rather than a parallel algorithm
that can be distributed across the multicast group?

tia,
	George

---

From: canetti <[email-masked]>
Date: Fri, 19 Nov 2004 23:46:05 -0500 (EST)

George,
I must say that the specific concern of distributing the NFS
computation over the multicast group (as opposed to distributing it in
general) seems to me somewhat of a red herring. If an attacker wants to
distribute computations it has multiple potential ways of doing so, and I
dont see that using the group members is easier than using any other
collecion of unsuspecting Internet users...

Best,

Ran