sorry for ignoring your ideas about a p9sk3, but is your mentioning of ocam's razor implying that dp9ik is too complicated? is there any other reason to stick with DES instead of AES in particular? i'm not a cryptographer by any means, but just curious.
On Sun, May 12, 2024 at 3:17 PM Richard Miller <9f...@hamnavoe.com> 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. > > 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-M2b019138d47049a2ec5d3ecb Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
