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.
mo...@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: o...@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