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

[ianG]

On 17/08/2015 18:56 pm, Viktor Dukhovni wrote:
> 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.


NSA is now pushing the notion that quantum vulnerable algorithms are to 
be avoided [0] [1].

fwiw, my understanding is in responding to quantum, we prefer large RSA 
in the medium term (8k?) and switch to NTRU [2] in the longer term.  We 
avoid ECC.


> 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?



Right, dial down to 128 level.  Or, we go to second order risk analysis 
-- who is our likely attacker, and is he likely to have quantum attack? 
  For most people most of the time, NSA isn't our attacker, so maybe we 
accept this risk.

Problem is, once the NSA has shifted in this direction, NIST comes out 
with standards for USG.  Then, people who don't do their own security 
risk analysis copy NIST and the sheep move to protecting whatever it is 
that NSA was worried about.



iang



[0] I posted this hint last week
http://www.metzdowd.com/pipermail/cryptography/2015-August/026287.html

[1] John Young posted this hint too:
http://www.metzdowd.com/pipermail/cryptography/2015-August/026303.html

CNSS Advisory Memo on Use of Public Standards for Secure Sharing of 
Information Among NatSec Systems 08/11/15

This Advisory expands on the guidance contained in CNSS Policy No. 15, 
National Information Assurance Policy on the Use of Public Standards for 
the Secure Sharing of Information Among National Security Systems 
(Reference a). Based on analysis of the effect of quantum computing on 
Information Assurance (IA) and IA-enabled Information Technology (IT) 
products, the policy’s set of authorized algorithms is expanded to 
provide vendors and IT users more near-term flexibility in meeting their 
IA interoperability requirements. The purpose behind this additional 
flexibility is to avoid vendors and customers making two major 
transitions in a relatively short timeframe, as we anticipate a need *to 
shift to quantum-resistant cryptography in the near future*.

[2] NTRU: https://en.wikipedia.org/wiki/NTRU