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-ob1.topicbox.com (tb-ob1.topicbox.com [64.147.108.173]) by inbox.vuxu.org (Postfix) with ESMTP id 1CAAA201A4 for ; Sun, 12 May 2024 15:59:24 +0200 (CEST) Received: from tb-mx0.topicbox.com (tb-mx0.nyi.icgroup.com [10.90.30.73]) by tb-ob1.topicbox.com (Postfix) with ESMTP id CB9703EBD3 for ; Sun, 12 May 2024 09:59:23 -0400 (EDT) (envelope-from bounce.mM6dbaaf4ed5d4e0cfb97f4016.r522be890-2105-11eb-b15e-8d699134e1fa@9fans.bounce.topicbox.com) Received: by tb-mx0.topicbox.com (Postfix, from userid 1132) id C9225185C6ED; Sun, 12 May 2024 09:59:23 -0400 (EDT) ARC-Authentication-Results: i=2; topicbox.com; arc=pass; dkim=none (no signatures found); dmarc=none 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=kergis.com; spf=pass smtp.mailfrom=tlaronde@kergis.com smtp.helo=smtpout4.mo529.mail-out.ovh.net; 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=date:from:to:subject:message-id:references :mime-version:content-type:in-reply-to:list-help:list-id :list-post:list-subscribe:reply-to:content-transfer-encoding :list-unsubscribe; s=sysmsg-1; t=1715522363; bh=ORdg631VvcdDxcSy l9KDUSVOqM6YbfK2AcDfLA7cb7o=; b=K4EJ5SDOhNm2GFshTyh9jbSbP5jMePkj Bx4OraNwLAsd1AjbRhXN9hwVmjwBkM3Yd24cm/HCaAMHLfMU+OJ6bh12HCOVBfUV avIRicJEInvkpw42TIwOr0zklzvekgLY618xdJWH0RpY+7km9rq5roqm+0+/3r3K LaPLfOD+d2s= ARC-Seal: i=2; a=rsa-sha256; cv=pass; d=topicbox.com; s=sysmsg-1; t= 1715522363; b=K7lH+L5nVmU4iqN2a48TKWeJDccDOLmzxwqUzkOJFC2hJBF+CG MnDwP6HW1oadjuM9oMOX4xjC/3LGHpiGyE5UvmDWsWsnsWpId9ZF5iymMydBFMXv ijyqllLl01O2bzLbSAisA0KVr8kuwkwjGcwC4ObdxjfMYjCm+9Gd5JW7Q= Authentication-Results: topicbox.com; arc=pass; dkim=none (no signatures found); dmarc=none 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=kergis.com; spf=pass smtp.mailfrom=tlaronde@kergis.com smtp.helo=smtpout4.mo529.mail-out.ovh.net; 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: garm.ovh; auth=pass (GARM-96R001ba0e8d64-b588-4d45-a2b4-26bdd4bb2467, 5E14C14271D413DEFE03735BC941B79FADB75C08) smtp.auth=tlaronde@kergis.com X-Received-Authentication-Results: tb-mx1.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC did not pass); dkim=none (no signatures found); dmarc=none 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=kergis.com; iprev=pass smtp.remote-ip=217.182.185.173 (smtpout4.mo529.mail-out.ovh.net); spf=pass smtp.mailfrom=tlaronde@kergis.com smtp.helo=smtpout4.mo529.mail-out.ovh.net; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=smtpout4.mo529.mail-out.ovh.net policy.ptr=smtpout4.mo529.mail-out.ovh.net; x-return-mx=pass header.domain=kergis.com policy.is_org=yes (MX Records found: mx2.ovh.net,mx1.ovh.net,mxb.ovh.net); x-return-mx=pass smtp.domain=kergis.com policy.is_org=yes (MX Records found: mx2.ovh.net,mx1.ovh.net,mxb.ovh.net); 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=date:from :to:subject:message-id:references:mime-version:content-type :in-reply-to:list-help:list-id:list-post:list-subscribe:reply-to :content-transfer-encoding:list-unsubscribe; s=dkim-1; t= 1715522363; x=1715608763; bh=dxLzaUGhw/apL+D3d2F1srp1jAAokD95oHz 1vf7c72Y=; b=neLy1MYntm0QEMTTchuIA2wVShvMlcS3rpvnx8w7hE+X46GBZ3x ubh+kLKe9qZM82XKmS9JqWllJVncVjwW3eva6ZAQzaJktNq9czjUoQ9PNLDUsLOi VTxGBxkLHfACppu6x0Q2E7Mc+kxSTYP2rSBm4xcDhRQrXq7ajbmC8xw8= Received: from tb-mx1.topicbox.com (localhost.local [127.0.0.1]) by tb-mx1.topicbox.com (Postfix) with ESMTP id 1E7711901C75 for <9fans@9fans.net>; Sun, 12 May 2024 09:59:13 -0400 (EDT) (envelope-from tlaronde@kergis.com) Received: from tb-mx1.topicbox.com (localhost [127.0.0.1]) by tb-mx1.topicbox.com (Authentication Milter) with ESMTP id 5459D3B4053; Sun, 12 May 2024 09:59:13 -0400 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1715522353; b=iNToaqVRP1/q1ARyN275BvodZ3zlr+3TBr3kf8+VkqcJ5BlMWN fTt9JSbnaIb0ulJVrh3Ax7o3N95Yd3CsWLYk6c2dN3mKqMFAsJTrP3guB3HZdm3N EGSw65S9A8QeVSn4x5ptBAFZmhVrBpNoOLuH3RZYnk3GR4wbwEyRNDspDygq6+B6 Gx2gPBiYwKtNb5Aeal1AaOeQ/gJoV6UFJNuyirHw2iCB1ZvrAo7YM9RWI+H5f9JK myzqBAWCMJvsd7x2YLXB8DNuLu2dR86xSVBQiRREFhcc7ssskJYP33eT+ZNKJwDP UARrl2RxbAs5dIWEUtr27Bt5mJGRHmaRfcfg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=date:from:to:subject:message-id:references :mime-version:content-type:in-reply-to; s=arcseal; t=1715522353; bh=ALasLD24KPYHFiqzyMbKIP6J7eaqPqAs2jsL9t9243Y=; b=nyXifPVE7cDv 3yCnVIqRnD3EM7zTf5xeVWb+ZPeruthpegW6tmvI/6f4C7CfZVRnqriKT3W8NWPF sYSyuGLoPGzdqOp4MmQLts5pisKiTuxhBBGaK+U2G3QD3SJOanBf9CpF6us0nWUK HgvdMyqQBABrMv8r9LKn/nUfVsz/JI3m1TYi3e2Fjp/3OyV/H2YkykSqN6qDB/HI 2FYj4zyRRGqMwdIl/sz8A6ubDXClg+H/xgKXhIB52MWpxZAMHNgvFum60CzlKkwB mc+enTIjVhIErvfQGLJ81THsQ1aiEX/pYDhUYRB40H6czwTU1zTe3UnpjLIUbMhN cgMcPwhuZw== ARC-Authentication-Results: i=1; tb-mx1.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC did not pass); dkim=none (no signatures found); dmarc=none 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=kergis.com; iprev=pass smtp.remote-ip=217.182.185.173 (smtpout4.mo529.mail-out.ovh.net); spf=pass smtp.mailfrom=tlaronde@kergis.com smtp.helo=smtpout4.mo529.mail-out.ovh.net; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=smtpout4.mo529.mail-out.ovh.net policy.ptr=smtpout4.mo529.mail-out.ovh.net; x-return-mx=pass header.domain=kergis.com policy.is_org=yes (MX Records found: mx2.ovh.net,mx1.ovh.net,mxb.ovh.net); x-return-mx=pass smtp.domain=kergis.com policy.is_org=yes (MX Records found: mx2.ovh.net,mx1.ovh.net,mxb.ovh.net); 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: gggruggvucftvghtrhhoucdtuddrgedvledrvdegvddgjeduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuf fkfhggtggujghisehttdertddttddvnecuhfhrohhmpeeothhlrghrohhnuggvsehkvghr ghhishdrtghomheqnecuggftrfgrthhtvghrnhepffevfeejgeejudfhjefftedvjedtge efvedukeeffeegueekfeetieejfffhkefhnecuffhomhgrihhnpehstghivghntggvughi rhgvtghtrdgtohhmpdhkvghrghhishdrtghomhdpnhhunhgtqdgvthdqhhhitgdrfhhrne cukfhppedvudejrddukedvrddukeehrddujeefpdefjedrheelrddugedvrdeliedpvddu fedrgeegrddvgeegrdehleenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepih hnvghtpedvudejrddukedvrddukeehrddujeefpdhhvghlohepshhmthhpohhuthegrdhm ohehvdelrdhmrghilhdqohhuthdrohhvhhdrnhgvthdpmhgrihhlfhhrohhmpeeothhlrg hrohhnuggvsehkvghrghhishdrtghomheqpdhnsggprhgtphhtthhopedupdhrtghpthht ohepoeelfhgrnhhsseelfhgrnhhsrdhnvghtqe X-ME-VSScore: 0 X-ME-VSCategory: clean Received-SPF: pass (kergis.com: Sender is authorized to use 'tlaronde@kergis.com' in 'mfrom' identity (mechanism 'include:mx.ovh.com' matched)) receiver=tb-mx1.topicbox.com; identity=mailfrom; envelope-from="tlaronde@kergis.com"; helo=smtpout4.mo529.mail-out.ovh.net; client-ip=217.182.185.173 Received: from smtpout4.mo529.mail-out.ovh.net (smtpout4.mo529.mail-out.ovh.net [217.182.185.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by tb-mx1.topicbox.com (Postfix) with ESMTPS for <9fans@9fans.net>; Sun, 12 May 2024 09:59:11 -0400 (EDT) (envelope-from tlaronde@kergis.com) Received: from mxplan4.mail.ovh.net (unknown [10.109.139.198]) by mo529.mail-out.ovh.net (Postfix) with ESMTPS id 4VckkQ3PLWzyg9 for <9fans@9fans.net>; Sun, 12 May 2024 13:59:10 +0000 (UTC) Received: from kergis.com (37.59.142.96) by DAG1EX1.mxp4.local (172.16.2.1) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.37; Sun, 12 May 2024 15:59:10 +0200 X-OVh-ClientIp: 213.44.244.59 Received: from cauchy.polynum.local (localhost [127.0.0.1]) by cauchy.polynum.local (8.16.1/8.16.1) with ESMTPS id 44CDx8WK018780 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO) for <9fans@9fans.net>; Sun, 12 May 2024 15:59:08 +0200 (CEST) Received: (from tlaronde@localhost) by cauchy.polynum.local (8.16.1/8.14.9/Submit) id 44CDx8Y6019079 for 9fans@9fans.net; Sun, 12 May 2024 15:59:08 +0200 (CEST) Date: Sun, 12 May 2024 15:59:08 +0200 From: To: 9fans <9fans@9fans.net> Subject: Re: [9fans] one weird trick to break p9sk1 ? Message-ID: References: <2dda1745-c644-4d9b-b436-26aaf3380192@posixcafe.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline In-Reply-To: X-Originating-IP: [37.59.142.96] X-ClientProxiedBy: DAG4EX1.mxp4.local (172.16.2.7) To DAG1EX1.mxp4.local (172.16.2.1) X-Ovh-Tracer-GUID: 20a77b3f-869b-4add-af0c-42d2096b685d X-Ovh-Tracer-Id: 14640639439245216535 X-VR-SPAMSTATE: OK X-VR-SPAMSCORE: 0 X-VR-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgedvledrvdegvddgjedtucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuqfggjfdpvefjgfevmfevgfenuceurghilhhouhhtmecuhedttdenucenucfjughrpeffhffvuffkfhggtggujghisehttdertddttddvnecuhfhrohhmpeeothhlrghrohhnuggvsehkvghrghhishdrtghomheqnecuggftrfgrthhtvghrnhepffevfeejgeejudfhjefftedvjedtgeefvedukeeffeegueekfeetieejfffhkefhnecuffhomhgrihhnpehstghivghntggvughirhgvtghtrdgtohhmpdhkvghrghhishdrtghomhdpnhhunhgtqdgvthdqhhhitgdrfhhrnecukfhppeduvdejrddtrddtrddupdefjedrheelrddugedvrdeliedpvddufedrgeegrddvgeegrdehleenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduvdejrddtrddtrddupdhmrghilhhfrhhomhepthhlrghrohhnuggvsehkvghrghhishdrtghomhdpnhgspghrtghpthhtohepuddprhgtphhtthhopeelfhgrnhhsseelfhgrnhhsrdhnvghtpdfovfetjfhoshhtpehmohehvdelpdhmohguvgepshhmthhpohhuth Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: d2d1580e-1067-11ef-b24c-ba03fc4dc9a2 Archived-At: =?UTF-8?B?PGh0dHBzOi8vOWZhbnMudG9waWNib3guY29tL2dyb3Vwcy85?= =?UTF-8?B?ZmFucy9UNTYzOTdlZmY2MjY5YWYyNy1NNmRiYWFmNGVkNWQ0ZTBjZmI5N2Y0?= =?UTF-8?B?MDE2Pg==?= List-Help: List-Id: "9fans" <9fans.9fans.net> List-Post: List-Software: Topicbox v0 List-Subscribe: Precedence: list Reply-To: 9fans <9fans@9fans.net> Content-Transfer-Encoding: quoted-printable List-Unsubscribe: , Topicbox-Delivery-ID: 2:9fans:437d30aa-c441-11e9-8a57-d036212d11b0:522be890-2105-11eb-b15e-8d699134e1fa:M6dbaaf4ed5d4e0cfb97f4016:1:6b66YONmh63oraHOtimFLxT25_frOF_DWFhNHVQuse4 On Sun, May 12, 2024 at 02:16:47PM +0100, 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: > >=20 > > 1) p9sk1 allows the shared secret to be brute-forced offline. > > 2) The average consumer machine is fast enough to make a large amount o= f attempts in a short time, > > in other words triple DES is not computationally hard to brute force= these days. > >=20 > > 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. >=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: >=20 > > 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. >=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. >=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. >=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. Let's see if Natural Unintelligence (mine) can beat Artifial Intelligence: - knowing that bubbles can "resolve" equations that we can't (Plateau's problem); - knowing that teenagers chew chewing-gums; Isn't it possible that a teenager, making bubbles with chewing-gum, was able to solve analogically a problem that is digitally very difficult to challenge? [I'm absolutely convinced that, if cryptography is allowed in the digital world, this is because some entities have analogical means to solve them...]. Yes: I'm like others. I love Internet because, when I'm tired of working, this is a great way of very busily doing nothing ;-) --=20 Thierry Laronde http://www.kergis.com/ http://kertex.kergis.com/ http://nunc-et-hic.fr/ Key fingerprint =3D 0FF7 E906 FBAF FE95 FD89 250D 52B1 AE95 6006 F40C ------------------------------------------ 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M6dbaa= f4ed5d4e0cfb97f4016 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription