[9fans] one weird trick to break p9sk1 ?

[Richard Miller <9fans@hamnavoe.com>]

I'm using a new subject [was: Interoperating between 9legacy and 9front]
in the hope of continuing discussion of the vulnerability of p9sk1 without
too many other distractions.

moody@posixcafe.org said:
> If we agree that:
> 
> 1) p9sk1 allows the shared secret to be brute-forced offline.
> 2) The average consumer machine is fast enough to make a large amount of attempts in a short time,
>    in other words triple DES is not computationally hard to brute force these days.
> 
> I don't know how you don't see how this is trivial to do.

I agree that 1) is true, but I don't think it's serious. The shared secret is
only valid for the current session, so by the time it's brute forced, it may
be too late to use. I think the bad vulnerability is that the ticket request
and response can be used offline to brute force the (more permanent) DES keys
of the client and server. Provided, of course, that the random teenager somehow
is able to listen in on the conversation between my p9sk1 clients and servers.

On the other hand, it's hard to know whether to agree or disagree with 2),
without knowing exactly what is meant by "large amount", "short time",
"computationally hard", and "trivial".

When Jacob told me at IWP9 in Waterloo that p9sk1 had been broken, not
just theoretically but in practice, I was looking forward to seeing publication
of the details. Ori's recent claim in 9fans seemed more specific:

> From: ori@eigenstate.org
> ...
> keep in mind that it can literally be brute forced in an
> afternoon by a teenager; even a gpu isn't needed to do
> this in a reasonable amount of time.

I was hoping for a citation to the experimental result Ori's claim was
based on. If the "it" which can be brute forced refers to p9sk1, it
would be very interesting to learn if there are flaws in the algorithm
which will allow it to be broken without breaking DES. My assumption
was that "it" was referring simply to brute forcing DES keys with a
known-plaintext attack. In that case, a back of the envelope calculation
can help us to judge whether the "in an afternoon" claim is plausible.

In an afternoon from noon to 6pm, there are 6*60*60 seconds. To crack
a single DES key by brute force, we'd expect to have to search on average
half the 56-bit key space, performing about 2^55 DES encryptions. So how
fast would the teenager's computer have to be?

        cpu% hoc
        2^55/(6*60*60)
        1667999861989
        1/_
        5.995204332976e-13

1667 billion DES encryptions per second, or less than a picosecond
per encryption. I think just enumerating the keys at that speed would
be quite a challenge for "the average consumer machine" (even with a GPU).

A bit of googling for actual results on DES brute force brings up
https://www.sciencedirect.com/science/article/abs/pii/S1383762122000066
from March 2022, which says:
 "Our best optimizations provided 3.87 billion key searches per second for Des/3des
 ... on an RTX 3070 GPU."

So even with a GPU, the expected time to crack a random 56-bit key would be
something like:

        cpu% hoc
        2^55/3.87e9
        9309766.671567
        _/(60*60*24)
        107.7519290691

More than three months. The same paper mentions someone else's purpose-built
machine called RIVYERA which "uses 128 Xilinx Spartan-6 LX150 FPGAs ... 
can try 691 billion Des keys in a second ... costs around 100,000 Euros".
Still not quite fast enough to break a key in an afternoon.

When Jacob says "triple DES is not computationally hard to brute force these days",
I assume this is just a slip of the keyboard, since p9sk1 uses only single DES.
But if we are worried about the shaky foundations of p9sk1 being based on
single DES, Occam's Razor indicates that we should look for the minimal and simplest
possible extension to p9sk1 to mitigate the brute force threat. The manual entry for
des(2) suggests that the Plan 9 authors were already thinking along these lines:

     BUGS
          Single DES can be realistically broken by brute-force; its
          56-bit key is just too short.  It should not be used in new
          code, which should probably use aes(2) instead, or at least
          triple DES.

Let's postulate a p9sk3 which is identical to p9sk1 except that it encrypts the
ticket responses using 3DES instead of DES. The effective keyspace of 3DES is
considered to be 112 bits because of the theoretical meet-in-the-middle attack.
So brute forcing a 3DES key with commodity hardware (including GPU) would be
expected to take something like:

        cpu% hoc
        2^111/3.87e9
        6.708393874076e+23
        _/(60*60*24*365.25)
        2.125761741728e+16

That's quadrillions of years. Not what most people would call "trivial".
And that's generously assuming the implementation of meet-in-the-middle
is zero cost. Without meet-in-the-middle, we're looking at a 168-bit
keyspace and an even more preposterous number of years.

I was looking forward to the "proof of concept". Even if we can't see
the details, it would be intriguing to know if it was specifically about
breaking p9sk1 or just cracking DES keys, and what assumptions were made
about practical speed of operation.


------------------------------------------
9fans: 9fans
Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Mc7caa71e6900a435bbe4a9b6
Delivery options: https://9fans.topicbox.com/groups/9fans/subscription