[Cryptography] NSA Crypto Breakthrough Bamford [was: WhatsApp keying...]

[Ray Dillinger]

On 05/19/2016 02:14 PM, Ray Dillinger wrote:
> 
> 
> On 05/18/2016 01:53 PM, Henry Baker wrote:
> 
>> I tend to agree with Nadia Heninger's conjecture that NSA has broken
>> discrete logs of certain types.
>>
>> It has the right flavor: NOBUS acres of computers.
> 
>> "Logjam" attack on discrete logs:
>>
>> https://weakdh.org/imperfect-forward-secrecy.pdf
> 
> Well, after reading, I suppose you and Bamford are probably right about
> what the breakthrough here probably is, but I strongly dispute NOBUS in
> this case.


Oh crap.  I could be wrong here but I think maybe it's worse than
that.

The Number Field Sieve algorithm for finding vectors of coefficients
for index calculus has a lot of sub-parts which don't depend on the
particular modulus being considered.  Those intermediate results can be
applied to precalculations on multiple moduli.  Some fraction of the
work you do when precomputing for modulus x can be reused when doing
precomputation for another modulus y.

It's a small fraction, but an opponent trying to build these
databases for a large number of different moduli (on the order of a few
thousand groups) could eventually realize a benefit from many such
small fractions that reduces the compute time required by ???  Uh,
back of the envelope says maybe two orders of magnitude? The costs
in data storage and the degree to which your calculations
get I/O bound, get steeper the more of a speedup you ask for.

I don't quite know if this is a practical technique; it depends on
whether the I/O requirements are light enough that the computation can
proceed at speed. It might be so I/O bound for significant advantage
that it's not worth it.  Also I'm still trying to figure out whether
the intermediate data storage requirements for a 2-order speedup are
merely very large (a few exabytes or less) or ludicrous (larger than a
few yottabytes).

ObNothingInParticular, we're getting close to needing more SI prefixes
to describe our storage media.

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160519/3eb1a640/attachment.sig>