[Cryptography] composing EC & RSA encryption?

[ianG]

On 25/10/2015 22:47 pm, Tony Arcieri wrote:
> On Sun, Oct 25, 2015 at 5:42 AM, ianG <iang at iang.org
> <mailto:iang at iang.org>> wrote:
>
>     The recent "distancing" news from NSA concerning ECC and their view
>     that QC is coming sooner [0] rather than later has somewhat upset
>     things.
>
>     An EC/RSA signing form is easy - just make one signature in RSA and
>     one in EC, and we're done.  At least at a trivial level, this works,
>     although I imagine it might be possible to do better - interesting
>     work for a grad student perhaps.
>
>     But what about encryption?
>
>
> First, if your worry is QCs, then trying to combine ECC and RSA isn't
> going to help you as they'll both be obliterated by QCs.


My worry really isn't QC - the notion that the aussies can build a 
million qubit machine in 5 years only makes sense if they're in 
Queensland, where we have it on good authority that the dope they grow 
is better than God's Dope [0].

My real worry is that the working groups are going to *add more 
algorithms* and thus make the protocols more brittle.  They are not 
going to take away.  They've been aware of this flaw in their process 
for a decade now [1], but still have no real consensus on how to 
deprecate a cipher suite and rollover to modern stuff.

Thought for today:

     Every RFC Security section has to have the rollover plan.

Point being that ad hoc thinking & talking about problems in the future 
hasn't worked.  But maybe if we force the RFC authors to make a stab at 
it in words, we can see what works and what doesn't in 2025?


> However, the general idea of combining multiple algorithms isn't
> inherently bad. What you would *actually* want to do is combine e.g. ECC
> with an as-yet-unproven quantum algorithm, like Ring-LWE (possibly not a
> good idea due to patents, but let's go with it for now)
>
> In that case, you can do a key exchange with both algorithms, and feed
> the results of both into a KDF (e.g. concatenating the keys exchanged
> together as KDF inputs)
>
> This sort of scheme should be at least as strong as the strongest of the
> two.


Yep, same as Jerry.

While we're having fun here [2], one more:  Adi Shamir's secret sharing 
is supposed to be information theoretic secure - not just 
computationally secure.  Is there mileage here?  How does it perform 
against QC?



iang



[0] inside reference to an old popular aussie song

[1] Steven M. Bellovin and Eric K. Rescorla. Deploying a new hash 
algorithm. In Proceedings of NDSS '06, 2006.
https://www.cs.columbia.edu/~smb/papers/new-hash.pdf
Abstract: The strength of hash functions such as MD5 and SHA-1 has been 
called into question as a result of recent discoveries. Regardless of 
whether or not it is necessary to move away from those now, it is clear 
that it will be necessary to do so in the not-too-distant future. This 
poses a number of challenges, especially for certificate-based 
protocols. We analyze a number of protocols, including S/MIME and TLS. 
All require protocol or implementation changes. We explain the necessary 
changes, show how the conversion can be done, and list what measures 
should be taken immediately.

[2] The penny drops. This is why the NSA is illegally harvesting all the 
Internet it can get. Because it will then be able to go back and break 
all those RSA keys while the machines are waiting for hi-prio traffic 
... and decrypt huge continents-worth of secret stuff ... of people who 
thought they were secured. Run the traffic through the word-list 
detector and build a bigger graph of who was a bad boy 20 years back...

So, it's willing to run the risk of breaking the law because this bounty 
won't be around forever. It ends once everyone realises all their past 
comms is going to be harvested.

Problem is, this kicker also kicks them - if the Chinese & Russkies are 
busy hoovering up all the traffic now from borked routers around 
Washington DC and all military companies, then it will bite back much 
harder.

That's why the announcement has a sense of panic - the USG is in the 
worst position of all because its data is more valuable. Hold your 
breath while USG moves to lower the boom of ITAR on all QC.

Hence a further (advanced) question isn't just over RSA (the bulk) but 
also over RSA + PFS (protocol forward secrecy) modes...