Re: [9fans] one weird trick to break p9sk1 ?
Jacob Moody: > I'm very glad we were able to communicate this and thank you for taking > the time to talk about this here in this thread. And thanks to you for pointing me to the GTX 4090 and https://crack.sh Both real eye openers. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M2c85ac49e8d6a52c1732cc2c Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
> My point was only about the advantage of p9sk3 over p9sk1, not to > compare it with anything else. The intent was to counter the implication > that p9sk1 is terrible and completely broken, by suggesting that the One error in our naming is that it might imply dp9ik completely replaced p9sk1. quickly googling for the terms reveals others have amplified this misunderstanding. Instead, dp9ik *extends* the p9sk1 by an additional authentication procedure. Forgive the confusion everybody. > (with no change to the protocol on-the-wire). Of course it doesn't mitigate > the problem of users negligently choosing weak passwords. dp9ik has the > extra advantage of doing that too, by removing the opportunity for offline > dictionary attacks. Thank you for finding a better way to phrase that one also. This was indeed one of cinap's design goals. It is pretty near to the minimal amount of changes needed in the system that would achieve secure continued use of passwords with the same user experience as before. I have not seen another implementation that does quite the same either in the real world. Remember, everybody else just gave up on passwords, while here, passwords are now secure by design: Secure your authservers well, and you will have a very very modern and extremely unique security system, unalike anything else out there. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M5da7bb9c49b6387cc74e0a3b Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
On 5/13/24 05:18, Richard Miller wrote: > Jacob and Ori, thank you for filling in some more details. Without > the specifics I had been making some wrong assumptions about where > the exact threat was. > > I think I now have a clearer picture: > > It's not particularly p9sk1 which is vulnerable, but the protocol > for ticket request / response, which leaks enough information to > allow offline exploration of user keys. The contribution of p9sk1 > is that its handshake protocol helpfully reveals a valid user name - > ie the authid - which can be used by an attacker to make a legitimate > ticket request, without any need for eavesdropping or guessing at > user names. Yes that is how I understand it. > > So, if you have an authentication service exposed to the ipv4 > internet (or to the ipv6 internet with a findable address), and > your authid or a known or guessable userid has a weak enough > password to succumb to a dictionary search, it's probably right > to say that a random attacker could make a cpu connection or > mount your file service with an afternoon's work on consumer > hardware. > > Nobody needs to have weak passwords, though. Using the !hex attribute > instead of !password with factotum, and/or using secstore(1), makes it > easy to have a randomly generated DES key with the full 56 bits of > entropy. This makes the attacker do more work ... but not all that > much more. I hadn't kept up with how powerful commodity GPUs have > become. (My most recent experience with High Performance Computing > involved transputer arrays and Cray T3Ds. Nowadays I specialise in > low performance computing.) It appears that investment of a few > thousand dollars and a few days compute time (maybe less if using > cloud services) is enough for a full brute-force exploration of the > single-DES keyspace. I'm very glad we were able to communicate this and thank you for taking the time to talk about this here in this thread. Thank you, Jacob Moody -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Me0355c116b61ac991520ac58 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
>> (OK, I know that's delusional because I've installed go. But maybe >> not for much longer, as google seems determined to introduce python3 >> as a dependency.) > > wat!?? The Go team is willing to replace the CI builders written in Go by the Chromium builders, which are written in Python 3. So the CI will depend on Python to build Go and run tests. -- David du Colombier -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M0d3f319c9a3405266fa53279 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
> > (OK, I know that's delusional because I've installed go. But maybe > not for much longer, as google seems determined to introduce python3 > as a dependency.) wat!?? On Mon, 13 May 2024 at 13:48, Richard Miller <9f...@hamnavoe.com> wrote: > cro...@gmail.com: > > As for the proposed strawman `p9sk3`, I fail to see what advantage > > that would have over dp9ik > > My point was only about the advantage of p9sk3 over p9sk1, not to > compare it with anything else. The intent was to counter the implication > that p9sk1 is terrible and completely broken, by suggesting that the > threat of brute-forcing the entire keyspace can be mitigated with a > small, local and very easy to understand variation to the ticket service > (with no change to the protocol on-the-wire). Of course it doesn't > mitigate > the problem of users negligently choosing weak passwords. dp9ik has the > extra advantage of doing that too, by removing the opportunity for offline > dictionary attacks. > -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Ma0d5d024db1989861dc8d9aa Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
cro...@gmail.com: > As for the proposed strawman `p9sk3`, I fail to see what advantage > that would have over dp9ik My point was only about the advantage of p9sk3 over p9sk1, not to compare it with anything else. The intent was to counter the implication that p9sk1 is terrible and completely broken, by suggesting that the threat of brute-forcing the entire keyspace can be mitigated with a small, local and very easy to understand variation to the ticket service (with no change to the protocol on-the-wire). Of course it doesn't mitigate the problem of users negligently choosing weak passwords. dp9ik has the extra advantage of doing that too, by removing the opportunity for offline dictionary attacks. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M86b283cc4c651efabdf9c3da Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
me: >> I try to take a >> minimum-intervention approach ... cro...@gmail.com: > Forgive my saying it, Richard, but I think this is a somewhat overly > staid view of things. You're welcome to say it. My minimalist attitude amounts to a religion, and therefore I don't need to justify it ☺. I know I'm at one extreme end of the scale. None of my machines are even running 9legacy, it's all 4th edition with enough hand-picked patches to make it useable for me. I wouldn't dream of pushing anyone else to follow my example. But personally, my Plan 9 network is a refuge from 21st century complexity, where I can in theory read and understand the infrastructure from top to bottom. (OK, I know that's delusional because I've installed go. But maybe not for much longer, as google seems determined to introduce python3 as a dependency.) -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M7407b85b6cdcbb4f959b4ae9 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
> Have a look at authsrv(6) in the manual. The authenticator sends a > pair of tickets to the client, one encrypted with the client's own > key and one encrypted with the server's key. That's what allows > both the client and server to authenticate each other. i stand corrected. also i confused cpuserver and authserver. and i still don't have the details paged in, so thank you for contributing another good summary :) > Yes, I think you're probably right. I was thinking in terms of minimum > lines of code to change, but other factors are also important. i generally use the same tactic in regards to minimal changes, and i certainly see it isn't used often enough in the field. i think the rule also doesn't conflict with what happened: replacement of outdated systems without good incremental path for future improvements, with useful high-quality software developed from scratch. it can happen, despite the late hype around "enshittification". lastly, rules are meant to be broken. the details just happen to matter more than the rule of thumb here. and again, anybody who knows crypthographers, since the approach is rather modern, please help share cinap's paper, maybe even the code, have a look, the more eyes the more better ;) -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M925311bc2b8c990e6ba917ed Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
> So, if you have an authentication service exposed to the ipv4 > internet (or to the ipv6 internet with a findable address), and > your authid or a known or guessable userid has a weak enough > password to succumb to a dictionary search, it's probably right > to say that a random attacker could make a cpu connection or > mount your file service with an afternoon's work on consumer > hardware. not only will they be able to make the connection, but they will be authenticated as a user that is probably more permissive than the 'none' user. for all the newbies reading this thread, this is the second reminder to read the auth paper. it is truly excellent ;) -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Md3a8fecbefcca9c49ceeb87e Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
23h...@gmail.com: > ... the server and client keys are the > same in p9sk1 as far as i understood. i would welcome public/private > key system though (is that what you were thinking of when separating > "server key" and "client key". that would add yet another set of > features that are currently missing. Have a look at authsrv(6) in the manual. The authenticator sends a pair of tickets to the client, one encrypted with the client's own key and one encrypted with the server's key. That's what allows both the client and server to authenticate each other. 23h...@gmail.com: > ... it seems to me that > concentrating on 3DES just for the sake of similarity to DES is taking > ocam's razor slightly too far. Yes, I think you're probably right. I was thinking in terms of minimum lines of code to change, but other factors are also important. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Mbc9a161e11837e5c464b2cd7 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
Jacob and Ori, thank you for filling in some more details. Without the specifics I had been making some wrong assumptions about where the exact threat was. I think I now have a clearer picture: It's not particularly p9sk1 which is vulnerable, but the protocol for ticket request / response, which leaks enough information to allow offline exploration of user keys. The contribution of p9sk1 is that its handshake protocol helpfully reveals a valid user name - ie the authid - which can be used by an attacker to make a legitimate ticket request, without any need for eavesdropping or guessing at user names. So, if you have an authentication service exposed to the ipv4 internet (or to the ipv6 internet with a findable address), and your authid or a known or guessable userid has a weak enough password to succumb to a dictionary search, it's probably right to say that a random attacker could make a cpu connection or mount your file service with an afternoon's work on consumer hardware. Nobody needs to have weak passwords, though. Using the !hex attribute instead of !password with factotum, and/or using secstore(1), makes it easy to have a randomly generated DES key with the full 56 bits of entropy. This makes the attacker do more work ... but not all that much more. I hadn't kept up with how powerful commodity GPUs have become. (My most recent experience with High Performance Computing involved transputer arrays and Cray T3Ds. Nowadays I specialise in low performance computing.) It appears that investment of a few thousand dollars and a few days compute time (maybe less if using cloud services) is enough for a full brute-force exploration of the single-DES keyspace. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M2867926d1deafb39060269df Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
On Sun, May 12, 2024 at 12:44 PM Richard Miller <9f...@hamnavoe.com> wrote: > 23h...@gmail.com: > > 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. > > My comments are about p9sk1; I'm not implying anything about other > algorithms. When working with other people's software, whether > professionally or for my own purposes, I try to take a > minimum-intervention approach: because it's respectful, because of > Occam's Razor, because of Tony Hoare's observation that software can > be either so simple that it obviously has no bugs, or so complicated > that it has no obvious bugs. Forgive my saying it, Richard, but I think this is a somewhat overly staid view of things. Software, as a constructed object, is maybe unique in that it is almost infinitely malleable, and the "minimum intervention" approach is often not terribly useful. As for being respectful of other people's software, who are these other people? The original authors of plan 9 are no longer involved, and indeed, the intellectual property has been transferred to the foundation, and by any reasonable standard the "community" has been given responsibility for the evolution of the code. As for the proposed strawman `p9sk3`, I fail to see what advantage that would have over dp9ik, except perhaps a less silly name. The person who wrote the paper on plan 9 security sees it being superior to what's there now, after all, and frankly he'd know better than either Occam or Tony Hoare. - Dan C. > I thought of 3DES in the first instance because of this desire to be > minimally disruptive. Support for DES is already there and tested. > 3DES only needs extra keys in /mnt/keys, and because 3DES encryption > with all three keys the same becomes single DES, there's a graceful > fallback when users have access only via an older client with > unmodified p9sk1. Obviously the server ticket would always be protected > by 3DES. > > This is only the first scratching of an idea, not implemented yet. > > I've got nothing against AES. I'm not a cryptographer either, but I did once > have to build a javacard implementation for a proprietary smartcard which > involved a lot of crypto infrastructure, and had to pass EMV certification. > Naturally that needed AES, elliptic curves, and plenty of other esoterica > to fit in with the existing environment and specifications. > -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M76fe847d3ed83b053ad32e0f Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
On Sun, May 12, 2024 at 02:16:47PM +0100, Richard Miller wrote: > > 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. Meanwhile, sweet32 exists, all this shit has already been prosecuted on other venues, and NIST shitcanned 3DES entirely last year. Not deprecated. Disallowed. Why? Because no matter how many numbers you paste into an email, it costs thirty bucks to crack it on someone else's ASIC farm. Pretending that getting access to $100k hash-cracking arrays is any more inconvenient than Uber Eats is straight-up disingenuous. It is extremely gross to be defending 3DES in 2024. You should know better. I don't particularly care if 9legacy adopts dp9ik, but there are people who will come reading this list archive down the road, and they'll be under the assumption that your arguments are in good faith. I hope they are not, because this crap is at best irresponsible. Occam's razor does not advocate ignoring the entire standardized best practices of the industry because you have emotional attachments to broken software and have used a pocket calculator to convince yourself you know better than everyone else on Earth. Advocating a switch to 3DES because it's backward-compatible with DES if you use it wrong is magnificent trolling, or depressing malpractice, depending on your intent. I can't ever know that, so I'll just state for posterity: kids, don't do this. It's a terrible plan. Do better, khm -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M6ef048148514ce58cf76ead5 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
Quoth o...@eigenstate.org:
> Quoth Richard Miller <9f...@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.
> >
> > 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:
> >
>
> The intial exchange sends across the challenges:
>
> C→S: CHc
> S→C: AuthTreq, IDs, DN, CHs, -, -
>
Oops -- wrong messages; these are the ones
you want to be breaking:
C→A: AuthTreq, IDs, DN, CHs, IDc, IDr
A→C: AuthOK, Kc{AuthTc, CHs, IDc, IDr, Kn}, Ks{AuthTs, CHs,
IDc, IDr, Kn}
Thanks to cinap for pointing that out.
--
9fans: 9fans
Permalink:
https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M396fa4f83c1770df9b18c6f1
Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
Quoth Richard Miller <9f...@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.
>
> 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:
>
The intial exchange sends across the challenges:
C→S: CHc
S→C: AuthTreq, IDs, DN, CHs, -, -
Because the challenge and IDs are sent as plain text, if I
can decrypt the client message with a key and find my known
plain text, that key will work to authenticate the client.
For example, if I have a ticket, and a trace of the first
few packets of the key exchange, I have enough information
to do something like this:
ticketpair = {
Kc{AuthTc, CHs, IDc, IDr, Kn},
Ks{AuthTs, CHs, IDc, IDr, Kn}
}
cmsg = ticketpair[0]
for(k in keyspace){
m = decrypt(k, cmsg)
if(m.CHs == CHs && m.IDs == IDs)
probably_bingo()
}
At that point, I need to guess the username, but this often
is relatively easy -- often, this is posted publicly; you
can probably guess that my user is 'ori' without trouble.
With those bits of information, you're able to complete a
new exchange as the client, and log in successfully.
The EFF was cracking DES keys in 22 hours back in 1998.
https://en.wikipedia.org/wiki/EFF_DES_cracker
Hardware, in particular GPUs, have gotten quite a bit
better since then.
--
9fans: 9fans
Permalink:
https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-Mbe7e83e1e06339063e6d8e8f
Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
> I thought of 3DES in the first instance because of this desire to be > minimally disruptive. Support for DES is already there and tested. > 3DES only needs extra keys in /mnt/keys, and because 3DES encryption > with all three keys the same becomes single DES, there's a graceful > fallback when users have access only via an older client with > unmodified p9sk1. Obviously the server ticket would always be protected > by 3DES. it is not obvious to me. but then, you know more about 3des than me. ;) there are some fundamental features in dp9ik that are still missing even when you increase the "quality" of the DES key by giving it arbitrarily longer lengths. also, the server and client keys are the same in p9sk1 as far as i understood. i would welcome public/private key system though (is that what you were thinking of when separating "server key" and "client key". that would add yet another set of features that are currently missing. > This is only the first scratching of an idea, not implemented yet. i can offer strictly less than that even. but it seems to me that concentrating on 3DES just for the sake of similarity to DES is taking ocam's razor slightly too far. though i do find it generally happens that security mechanisms are claimed to be "outdated", resulting in less scientific processes and more popularity contests than anything else, so putting extra scrutiny is highly welcome. on my part i'm simply trusting cinap on his intent and research as i have no hope to ever understand any details. but the dp9ik approach has some novelties which should make it worthwhile for security researchers to study. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M3d84204e405a926acc80c609 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
23h...@gmail.com: > 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. My comments are about p9sk1; I'm not implying anything about other algorithms. When working with other people's software, whether professionally or for my own purposes, I try to take a minimum-intervention approach: because it's respectful, because of Occam's Razor, because of Tony Hoare's observation that software can be either so simple that it obviously has no bugs, or so complicated that it has no obvious bugs. I thought of 3DES in the first instance because of this desire to be minimally disruptive. Support for DES is already there and tested. 3DES only needs extra keys in /mnt/keys, and because 3DES encryption with all three keys the same becomes single DES, there's a graceful fallback when users have access only via an older client with unmodified p9sk1. Obviously the server ticket would always be protected by 3DES. This is only the first scratching of an idea, not implemented yet. I've got nothing against AES. I'm not a cryptographer either, but I did once have to build a javacard implementation for a proprietary smartcard which involved a lot of crypto infrastructure, and had to pass EMV certification. Naturally that needed AES, elliptic curves, and plenty of other esoterica to fit in with the existing environment and specifications. -- 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M2003e6b5eb34ea3270a33bec Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
Re: [9fans] one weird trick to break p9sk1 ?
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. > > 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. 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: 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/S138376212266 > 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
Re: [9fans] one weird trick to break p9sk1 ?
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/S138376212266 > 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 >
[9fans] one weird trick to break p9sk1 ?
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/S138376212266 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
