Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

From: "A. Huelsing" <[email-masked]>
Date: Tue, 2 Feb 2016 12:01:40 +0100

On 01/28/16 18:54, Mike Hamburg wrote:
>
> Sent from my phone.  Please excuse brevity and typos.
>
>> On Jan 28, 2016, at 08:47, A. Huelsing <[email-masked]> wrote:
>>
>>
>>
>>> On 01/28/16 16:04, Phillip Hallam-Baker wrote:
>>> On Thu, Jan 28, 2016 at 5:16 AM, Stephen Farrell
>>> <[email-masked]> wrote:
>>>>> On 28/01/16 03:25, Benjamin Kaduk wrote:
>>>>> There is also the question of what the realm topology would look like --
>>>>> in other contexts there was talk of a central "clearinghouse" realm that
>>>>> would share keys with anyone that asked, leaving trust decisions to the
>>>>> end parties.  But that is not the only possible model...
>>>> That topic ("realm topology"), including who trusts whom for what,
>>>> might be a fine thing for a small group of folks to try sketch out in
>>>> case we needed such. The content might be initial attempts to answer
>>>> the question "what if we had to use Kerberos everywhere we now use
>>>> (EC)DH or RSA key transport, what'd that look like at Internet scale?"
>>>> That work might identify bits of work that could be taken up by the
>>>> IETF kitten WG later on.
>>>> Let us imagine that Alice has a shared secret with three distribution
>>>> centers run by the likes of Comodo, Symantec, etc. that have been
>>>> established in case of future need. There are 5 billion Internet users
>>>> and approx 50% have that type of backup plan but no applications are
>>>> going to use it at all until the need is proven.
>> I am honestly slightly confused that this is truly considered a possible
>> solution that needs analysis. A Kerberos-based web-security model would
>> mean that the trusted third parties can listen to any "secured"
>> communication between a user and a service. While this would already be
>> possible in todays Web-PKI setting (which is horrible enough), the new
>> issue is that no one could ever detect this attack in the new setting.
>> This would be the de-facto abolishment of Internet privacy.
>>
>> So you would honestly want to sell privacy just because signatures and
>> ciphertexts (for public key encryption) would slightly grow when using
>> post-quantum crypto? (Compared to the increase in size of user data like
>> an average Webpage over the last years the increase in size for
>> pq-crypto is really small.)
>>
>> -- Andreas
> This seems like it would only be useful in the event that PQ public key encryption turns out to be infeasible, or if we can't find a scheme we trust. Remember, we're very confident that hash-based signatures are PQ-secure, but not quite as much about the encryption or key exchange options.
>
> -- Mike
>
Well, while McEliece is not considered as sexy as lattice-based key
exchange, it does the job (although at the cost of a large public key).
The scheme is as mature as RSA, so probably even better understood than
ECC and the underlying problem has other real-world applications
motivating also people from outside crypto to look at it. Of course, you
will not find many works on McEliece in the big crypto conferences as it
seems like "everything important is already done" but I guess this is
the kind of scheme CFRG should look at for the worst-case.

If we start considering scenarios where quantum computers can break all
public key schemes, then we also have to consider cases where they can
break all symmetric crypto. This is as likely as the aforementioned
case. The reason: So far we only know that if we consider block ciphers
/ hash functions etc. as a black box then we only get a square-root
speed-up. However, obviously this does not apply in general (consider
VSH which is a hash function but clearly broken by quantum computers).
There are currently first approaches to apply quantum algorithms to the
analysis of symmetric primitives, unclear where this will lead.

-- Andreas