From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: * X-Spam-Status: No, score=1.7 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, HEADER_FROM_DIFFERENT_DOMAINS,LOTS_OF_MONEY,MAILING_LIST_MULTI, MONEY_NOHTML,RCVD_IN_DNSWL_NONE autolearn=no autolearn_force=no version=3.4.4 Received: from tb-ob0.topicbox.com (tb-ob0.topicbox.com [64.147.108.117]) by inbox.vuxu.org (Postfix) with ESMTP id AA54023D55 for ; Sun, 12 May 2024 17:20:14 +0200 (CEST) Received: from tb-mx1.topicbox.com (tb-mx1.nyi.icgroup.com [10.90.30.61]) by tb-ob0.topicbox.com (Postfix) with ESMTP id 433B6342BF for ; Sun, 12 May 2024 11:20:14 -0400 (EDT) (envelope-from bounce.mM5504c6a2ecd4ee22e4d99e8d.r522be890-2105-11eb-b15e-8d699134e1fa@9fans.bounce.topicbox.com) Received: by tb-mx1.topicbox.com (Postfix, from userid 1132) id 3CC3B1905EC2; Sun, 12 May 2024 11:20:14 -0400 (EDT) ARC-Authentication-Results: i=2; topicbox.com; arc=pass; dkim=pass (1024-bit rsa key sha256) header.d=posixcafe.org header.i=@posixcafe.org header.b=L1mwSZSn header.a=rsa-sha256 header.s=20200506 x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=posixcafe.org; spf=pass smtp.mailfrom=moody@posixcafe.org smtp.helo=mail.posixcafe.org; x-internal-arc=fail (as.1.topicbox.com=pass, ams.1.topicbox.com=fail (message has been altered)) (Message modified while forwarding at Topicbox) ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=message-id:date:mime-version:subject:to :references:from:in-reply-to:content-type :content-transfer-encoding:list-help:list-id:list-post :list-subscribe:reply-to:list-unsubscribe; s=sysmsg-1; t= 1715527214; bh=CumPhGIx/ewnsBJMmGmJRepcjUEwZm1SDlDLPZbyQ4Y=; b=j rq1+Jo9aaD+umc+KBWzD7KDz5S71UBRD7uOuj1+utxR0z+JLAhAkur59lMbdfYvt eaXe0wR6D2yr0WdcPMr1XMdmNgE8+lOouhDCSo/2/HjNUIi/a5fy2NGH5NAC70Kt qGgt+Xh3kb7I+3vmCDida0gBx8iuX3+M3eL9ItpX+Q= ARC-Seal: i=2; a=rsa-sha256; cv=pass; d=topicbox.com; s=sysmsg-1; t= 1715527214; b=BNVTXfbv7ejjVHREjbowK7eZ5S7hDrwAr/spu5jJ3I1lp+YSG4 PrtD2Zo2+4VhoNQcQvC8UN1vV8y6zfVzijxh4nK5yH3OGwojEVPFy3re0DT/ETtn 7X9oNu18VWBCwOOxAHw96aERtdGFzUV6+z3GqHk16M58rQobjDaeRcW24= Authentication-Results: topicbox.com; arc=pass; dkim=pass (1024-bit rsa key sha256) header.d=posixcafe.org header.i=@posixcafe.org header.b=L1mwSZSn header.a=rsa-sha256 header.s=20200506 x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=posixcafe.org; spf=pass smtp.mailfrom=moody@posixcafe.org smtp.helo=mail.posixcafe.org; x-internal-arc=fail (as.1.topicbox.com=pass, ams.1.topicbox.com=fail (message has been altered)) (Message modified while forwarding at Topicbox) X-Received-Authentication-Results: tb-mx0.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC Policy is not at enforcement); dkim=pass (1024-bit rsa key sha256) header.d=posixcafe.org header.i=@posixcafe.org header.b=L1mwSZSn header.a=rsa-sha256 header.s=20200506 x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=posixcafe.org; iprev=pass smtp.remote-ip=45.76.19.58 (mail.posixcafe.org); spf=pass smtp.mailfrom=moody@posixcafe.org smtp.helo=mail.posixcafe.org; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=mail.posixcafe.org policy.ptr=mail.posixcafe.org; x-return-mx=pass header.domain=posixcafe.org policy.is_org=yes (MX Records found: mail.posixcafe.org); x-return-mx=pass smtp.domain=posixcafe.org policy.is_org=yes (MX Records found: mail.posixcafe.org); x-tls=pass smtp.version=TLSv1.2 smtp.cipher=ECDHE-RSA-AES256-GCM-SHA384 smtp.bits=256/256; x-vs=clean score=0 state=0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=9fans.net; h=message-id :date:mime-version:subject:to:references:from:in-reply-to :content-type:content-transfer-encoding:list-help:list-id :list-post:list-subscribe:reply-to:list-unsubscribe; s=dkim-1; t=1715527214; x=1715613614; bh=4DBBJ7u2l3DqL6MP9ZYFScwcSCKAvQgT r3h8PGCBnb8=; b=PFdM8/NoIn5te49v/028VtGEpqHhbKAzKUd5nMjld+yROeTI +uox9m77kU5898C1C3apQmjSpBoDZywkSSxiU914gIfIWEF1cbUQ6/mMTO3Hd19i KO1Wl35dia/z0uIa8vTQ3RVTIKep3kKMoUrqBWYSP5vvWdIBRPVEQ/BrBIk= Received: from tb-mx0.topicbox.com (localhost.local [127.0.0.1]) by tb-mx0.topicbox.com (Postfix) with ESMTP id 629F5186015C for <9fans@9fans.net>; Sun, 12 May 2024 11:19:58 -0400 (EDT) (envelope-from moody@posixcafe.org) Received: from tb-mx0.topicbox.com (localhost [127.0.0.1]) by tb-mx0.topicbox.com (Authentication Milter) with ESMTP id 272B2D8D190; Sun, 12 May 2024 11:19:58 -0400 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1715527198; b=Ce63DHef8Xz5dguklwnrHwA+a6FbN6epVCkn1shdOGxMcCBNL4 Ei1mUesyJFZPOB3ebNs4J0WKj2+j00X/z0tAUFHul+4QcKu2lcIHspxPIBXvfmHd TTbbbMOKsMrS1eerAhs5Ve+usxWhgkHqZ4xK9S2lREuGkylM4kdLXYUVEML7VibQ /03gOe4RuSSdnl6Rgb3O6MviFPyc6dzLcNrs1TGS82mkRGOaaEYorBvycHr3IvKe s3SA+3P3rIknXBUf+QGVrKfkJMEUW7mFApYfqeu5AwbkrYKUcwrwPrcaqsg4XoJd jOBfkpp3Vdd2WOtJ4uTJ6i9JWYNEatVGvE0g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=message-id:date:mime-version:subject:to :references:from:in-reply-to:content-type :content-transfer-encoding; s=arcseal; t=1715527198; bh=9aodmj0c /Di/rN3gb4t4WXNJItmiAqCoPTmALjiuWls=; b=ZZr2XhkrFQV398blorRFBRLJ f4zZZ90BwMy/it9ZJrrpTzmEl6KENSUvY/W7R3eysDAFYZTo/UJlJfwERP0IXoQg 5sLazSuJCemcApR9Xfoeb68BFIQs18cMymupjqmwpNY/r6lOwBVlPtYquU5cO56b haNSpxoG4ZvsFX2vzJ2GLdAahNJHba6sHMJT2SkwfklOUYlGm5/DEY92J94dm4My l1oNQeBgAa5V4Yo8H6Q3wEVEx4QfOxzi+oy2+4DsB4c/nYAskJzA9FGhTWoEeHTa 936UnM84KymqJOHlLUv+mUsQ+rCWDA6BA5MoKaAcTJ1lMRnPCWhY3KK32X3ROQ== ARC-Authentication-Results: i=1; tb-mx0.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC Policy is not at enforcement); dkim=pass (1024-bit rsa key sha256) header.d=posixcafe.org header.i=@posixcafe.org header.b=L1mwSZSn header.a=rsa-sha256 header.s=20200506 x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=posixcafe.org; iprev=pass smtp.remote-ip=45.76.19.58 (mail.posixcafe.org); spf=pass smtp.mailfrom=moody@posixcafe.org smtp.helo=mail.posixcafe.org; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=mail.posixcafe.org policy.ptr=mail.posixcafe.org; x-return-mx=pass header.domain=posixcafe.org policy.is_org=yes (MX Records found: mail.posixcafe.org); x-return-mx=pass smtp.domain=posixcafe.org policy.is_org=yes (MX Records found: mail.posixcafe.org); x-tls=pass smtp.version=TLSv1.2 smtp.cipher=ECDHE-RSA-AES256-GCM-SHA384 smtp.bits=256/256; x-vs=clean score=0 state=0 X-ME-VSCause: gggruggvucftvghtrhhoucdtuddrgedvledrvdegvddgkeejucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpefkffggfg fuvfhfhfgjtgfgsehtjeertddtvdejnecuhfhrohhmpeflrggtohgsucfoohhougihuceo mhhoohguhiesphhoshhigigtrghfvgdrohhrgheqnecuggftrfgrthhtvghrnhepgfelff ejieefffeljedvvdeggfffgfekhfetgeejgfevudeuhfegieehiefgfeevnecuffhomhgr ihhnpehstghivghntggvughirhgvtghtrdgtohhmpdgtrhgrtghkrdhshhenucfkphepge ehrdejiedrudelrdehkedpvddtjedrgeehrdekvddrfeeknecuvehluhhsthgvrhfuihii vgeptdenucfrrghrrghmpehinhgvthepgeehrdejiedrudelrdehkedphhgvlhhopehmrg hilhdrphhoshhigigtrghfvgdrohhrghdpmhgrihhlfhhrohhmpeeomhhoohguhiesphho shhigigtrghfvgdrohhrgheqpdhnsggprhgtphhtthhopedupdhrtghpthhtohepoeelfh grnhhsseelfhgrnhhsrdhnvghtqe X-ME-VSScore: 0 X-ME-VSCategory: clean Received-SPF: pass (posixcafe.org: 45.76.19.58 is authorized to use 'moody@posixcafe.org' in 'mfrom' identity (mechanism 'mx' matched)) receiver=tb-mx0.topicbox.com; identity=mailfrom; envelope-from="moody@posixcafe.org"; helo=mail.posixcafe.org; client-ip=45.76.19.58 Received: from mail.posixcafe.org (mail.posixcafe.org [45.76.19.58]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by tb-mx0.topicbox.com (Postfix) with ESMTPS for <9fans@9fans.net>; Sun, 12 May 2024 11:19:57 -0400 (EDT) (envelope-from moody@posixcafe.org) Received: from [192.168.168.200] ( [207.45.82.38]) by mail.posixcafe.org (OpenSMTPD) with ESMTPSA id 4626c7e1 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO) for <9fans@9fans.net>; Sun, 12 May 2024 10:19:46 -0500 (CDT) Message-ID: <4cfdad97-e33e-42d7-8fee-377991a2ad2a@posixcafe.org> Date: Sun, 12 May 2024 10:19:55 -0500 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [9fans] one weird trick to break p9sk1 ? To: 9fans@9fans.net References: Content-Language: en-US From: Jacob Moody In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: 1bcfe286-1073-11ef-967d-e6da008c7b06 Archived-At: =?UTF-8?B?PGh0dHBzOi8vOWZhbnMudG9waWNib3guY29tL2dyb3Vwcy85?= =?UTF-8?B?ZmFucy9UNTYzOTdlZmY2MjY5YWYyNy1NNTUwNGM2YTJlY2Q0ZWUyMmU0ZDk5?= =?UTF-8?B?ZThkPg==?= List-Help: List-Id: "9fans" <9fans.9fans.net> List-Post: List-Software: Topicbox v0 List-Subscribe: Precedence: list Reply-To: 9fans <9fans@9fans.net> List-Unsubscribe: , Topicbox-Delivery-ID: 2:9fans:437d30aa-c441-11e9-8a57-d036212d11b0:522be890-2105-11eb-b15e-8d699134e1fa:M5504c6a2ecd4ee22e4d99e8d:1:o_X0RGvYTdU9CdmKdnDUm01HEdgwVFmXLwE69XFRjaY 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. >=20 > 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. >=20 > I agree that 1) is true, but I don't think it's serious. The shared secre= t 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 requ= est > 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 s= omehow > is able to listen in on the conversation between my p9sk1 clients and ser= vers. You do not need to listen between clients in order to get the DES key to be= gin brute forcing of the password. A malicious client can initiate an authentic= ation attempt without any current information about the user and leave with the e= ncrypted DES key to perform the known plaintext attack. >=20 > 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". >=20 > 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 publi= cation > 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. >=20 > 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. >=20 > 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? >=20 > cpu% hoc > 2^55/(6*60*60) > 1667999861989 > 1/_ > 5.995204332976e-13 >=20 > 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). >=20 > 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 fo= r Des/3des > ... on an RTX 3070 GPU." >=20 > So even with a GPU, the expected time to crack a random 56-bit key would = be > something like: >=20 > cpu% hoc > 2^55/3.87e9 > 9309766.671567 > _/(60*60*24) > 107.7519290691 >=20 > More than three months. The same paper mentions someone else's purpose-bu= ilt > machine called RIVYERA which "uses 128 Xilinx Spartan-6 LX150 FPGAs ...=20 > 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, b= ut not by much. >=20 > When Jacob says "triple DES is not computationally hard to brute force th= ese days", > I assume this is just a slip of the keyboard, since p9sk1 uses only singl= e 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 a= nd simplest > possible extension to p9sk1 to mitigate the brute force threat. The manua= l entry for > des(2) suggests that the Plan 9 authors were already thinking along these= lines: >=20 > 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. >=20 > Let's postulate a p9sk3 which is identical to p9sk1 except that it encryp= ts the > ticket responses using 3DES instead of DES. The effective keyspace of 3DE= S is > considered to be 112 bits because of the theoretical meet-in-the-middle a= ttack. > So brute forcing a 3DES key with commodity hardware (including GPU) would= be > expected to take something like: >=20 > cpu% hoc > 2^111/3.87e9 > 6.708393874076e+23 > _/(60*60*24*365.25) > 2.125761741728e+16 >=20 > 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 c= heap. >=20 > 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. >=20 The issue is both getting the "point and shoot" nature of getting the encry= pted DES key from a running p9sk1 server starting from zero knowledge, as well a= s the current bruteforceble encryption is what makes it a problem. ------------------------------------------ 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M5504c= 6a2ecd4ee22e4d99e8d Delivery options: https://9fans.topicbox.com/groups/9fans/subscription