Re: [9fans] one weird trick to break p9sk1 ?

[Jacob Moody <moody@posixcafe.org>]

On 5/12/24 08:16, Richard Miller wrote:
> 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.

You do not need to listen between clients in order to get the DES key to begin
brute forcing of the password. A malicious client can initiate an authentication
attempt without any current information about the user and leave with the encrypted
DES key to perform the known plaintext attack.

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

There are unfortunately some issues with the original paper done by my
friends that have prevented me from posting it publicly.
I think it would still be good to document this issue in a more concrete
fashion, I am sorry this has turned in to such a mess.

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

From what I found online a GTX 4090 has a single DES hash rate of 146.6 GH/s

cpu% hoc
2^55/146.6e9
245762.599038
_/(60*60*24)
2.8444745259

So Dan's guess of a couple of days is more accurate then Ori's hyperbole, but not by much.

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

Yes that is a mistake my mistake, it is indeed single 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.

Yes this would move it out of the reach of some random teenager, however
this is entirely discounting a dictionary attack. I guess you could do that if you
have confidence that your password is globally unique.

Also take a look at: https://crack.sh/
Seems single or triple DES, this website can do the job for you for quite cheap.

> 
> 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.
> 
The issue is both getting the "point and shoot" nature of getting the encrypted
DES key from a running p9sk1 server starting from zero knowledge, as well as the
current bruteforceble encryption is what makes it a problem.


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