[Cryptography] SHA-3 FIPS-202: no SHAKE512 but SHAKE128; confusing SHAKE security

[Viktor Dukhovni]

On Mon, Aug 17, 2015 at 07:59:26AM -0700, Ray Dillinger wrote:

> > "RSA really hits diminishing returns above 2048 bits."
> > 
> >  If we want to get to 2^256 work factor we need to more than double the
> > number of bits, we need 15360 bits which is ridiculous.
> 
> I don't believe it's ridiculous.  I mean, yes, large, but still under
> 2k.  We already had keys of such a length that nobody was going to
> enter them by hand, and 2k is near-epsilon with regard to today's
> protocols.
> 
> It probably lets the bottom tier devices have a decent excuse not to
> implement it, but other than that it's fine.

The performance cost is ridiculous:

		      sign    verify    sign/s verify/s
    rsa 1024 bits 0.000467s 0.000022s   2143.0  44570.3
    rsa 2048 bits 0.002530s 0.000074s    395.3  13592.8
    rsa 4096 bits 0.014179s 0.000198s     70.5   5047.2

What sort of numbers do you expect for RSA at 15k bits?  I would
conjecture around 2 signatures per second, and thus entirely
unsuitable for key agreement.  Perhaps still usable for verifying
certificate signatures, but with enough such certificates in a
chain, the chain will exceed TLS message size limits.

For the record I don't see a compelling difference between a 112-bit
work-factor and a 128-bit work-factor, provided the estimates hold
up reasonably well.  Also it seems that memory requirement for the
matrix stage of GNFS for large moduli are quite prohibitive.  Are
the work-factor estimates for large RSA moduli too conservative?

-- 
	Viktor.