Re: [Sks-devel] RFE: max-*-size and strip-photo-uids

[Robert J. Hansen]

On 5/27/12 7:10 AM, Robert J. Hansen wrote:
> *These feature requests have clear, obvious downsides.*  (Not the least
> of which is they won't work particularly well.)

So, the first question is -- what would be necessary for a solution to
work well?

The brute force and overkill approach: sanity-check each imported
certificate to ensure that the subkeys on the certificate are legitimate
cryptographic keys.

Note: this is barking madness.  If I give you a block of bits and say
this represents two numbers, the first being the product of two large
primes and the second number coprime to the first -- e.g., the (n, e)
tuple of an RSA public key -- the only way to prove it's a legitimate
public key would be to factor the first number and ensure that pq=n with
p and q prime, and that e is coprime to n.  If the only way to prove
that a block of data is a correct RSA key is to break RSA, then we're
absolutely screwed.

So much for the brute force and overkill approach.  We simply cannot
check to ensure that an RSA public key is good.  This may leave the door
open to checking whether an RSA public key is obviously *bad*.

To check for obviously bad keys, we could do trial divisions on all the
primes up to, say, 10,000.  A naive encoding of binary data onto a
purported RSA key would likely have a factor somewhere within that
range.  Presto, we have a way to detect bad RSA keys.

Unfortunately, it's completely bogus.  Someone could simply do a naive
encoding, then keep on adding 1 (well, 2, since they're smart enough to
avoid even numbers) until they found a value that had no small factors.
 To recover the original number they just start subtracting 2 and repeat
until such time as the CRC code in their data checks out.

There may be other such ways to check for bad keys, but I suspect
they're all going to face the same problem.  I don't think there's a
cryptologic solution to this.  It may be more worthwhile for us to look
at the data forensics community, to see if they have any tools that can
quickly and efficiently find media files that may be embedded inside
other files.  (This was part of the DFRWS 2006 challenge, incidentally,
so I know the forensics community has looked into the problem.)

Anyway.  Thoughts?  Ideas?