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 8FC862155F for ; Sun, 12 May 2024 15:17:02 +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 D46AE3E14A for ; Sun, 12 May 2024 09:17:01 -0400 (EDT) (envelope-from bounce.mMc7caa71e6900a435bbe4a9b6.r522be890-2105-11eb-b15e-8d699134e1fa@9fans.bounce.topicbox.com) Received: by tb-mx0.topicbox.com (Postfix, from userid 1132) id D31811859DE9; Sun, 12 May 2024 09:17:01 -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=hamnavoe.com; spf=pass smtp.mailfrom=miller@hamnavoe.com smtp.helo=mx2.mythic-beasts.com; 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:to:from:date:in-reply-to:mime-version :content-type:content-transfer-encoding:list-help:list-id :list-post:list-subscribe:reply-to:subject:list-unsubscribe; s= sysmsg-1; t=1715519821; bh=dCqqgGCGcFZAtMbDSU0ziZhQz8r/+X9ZitMdn 83Cv7c=; b=ApOFuQEPN658hiEvNz+2s33ZQhWVt0WeMnfnXFRYAivFptoLFdOUr ic766yhuAn3TSDceocfIOMRyVNFYd/eDCNEmVlee9BGXHcJ7MfGaBTdhCeDFWCaL 3AM2z1aAXBT8Clq7pWl19sYYi0YoCdb7e1OtOLxe+KQTy1ptC+1s3s= ARC-Seal: i=2; a=rsa-sha256; cv=pass; d=topicbox.com; s=sysmsg-1; t= 1715519821; b=assnnBSxn/zSxDHLQaNrYLP1NVgDi2epfS+3OTTKzRGwQR3p8Q 3jeExtWjpVew2qXJff7TyT/t3GI8+5Scw2jjFB94PlBDFXanNH2WOrhthXsZZli7 ZjGU4Le3DPG1vAm7F1Av4qLT/oiHTxf37jqPPcWrxODp2EyN6osS2hFg4= 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=hamnavoe.com; spf=pass smtp.mailfrom=miller@hamnavoe.com smtp.helo=mx2.mythic-beasts.com; 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-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=hamnavoe.com; iprev=pass smtp.remote-ip=46.235.227.24 (mx2.mythic-beasts.com); spf=pass smtp.mailfrom=miller@hamnavoe.com smtp.helo=mx2.mythic-beasts.com; x-aligned-from=domain_pass (Domain match); x-me-sender=none; x-ptr=pass smtp.helo=mx2.mythic-beasts.com policy.ptr=mx2.mythic-beasts.com; x-return-mx=pass header.domain=hamnavoe.com policy.is_org=yes (MX Records found: mx2.mythic-beasts.com,mx1.mythic-beasts.com); x-return-mx=pass smtp.domain=hamnavoe.com policy.is_org=yes (MX Records found: mx2.mythic-beasts.com,mx1.mythic-beasts.com); 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 :to:from:date:in-reply-to:mime-version:content-type :content-transfer-encoding:list-help:list-id:list-post :list-subscribe:reply-to:subject:list-unsubscribe; s=dkim-1; t= 1715519821; x=1715606221; bh=Xuwq1wd8WLcbclvLRuqrxw0jBcgg/U39pf7 xtnZ74yQ=; b=ltTcu97VikIEuxYMJ52VYtTHP1374gbIT8oKUNbAl3gyzDqpy4G q3FMFeGqTR1OS2NNhqxHfdR3slnBVpypvnXIkzzn8Q4DRTX7GBk+grRNQoNAiIUx hzJk+ifFcoSP2OuTFzxGno1w7mr4t6NCP+10lIUmEVXEgYo5wNqUOcb4= Received: from tb-mx1.topicbox.com (localhost.local [127.0.0.1]) by tb-mx1.topicbox.com (Postfix) with ESMTP id 919621900CDC for <9fans@9fans.net>; Sun, 12 May 2024 09:16:50 -0400 (EDT) (envelope-from miller@hamnavoe.com) Received: from tb-mx1.topicbox.com (localhost [127.0.0.1]) by tb-mx1.topicbox.com (Authentication Milter) with ESMTP id 0ECE17BF5BC; Sun, 12 May 2024 09:16:50 -0400 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1715519810; b=Z+97g3UN8IFTUg9s+jocPfw7XGLRL8G7tIQhhMw6k1hL8V9brO cFII3nQHmI33A8Yx02MPNCCcNilo5Dv4HAbQCvLwklSmOEyJI+iPcHmYh/GsDoD8 Q4Ohevt6ac6Sty7oiHvmxy5h07qj03mBzKctTkcPHXeKb+07jnfSSBpZRcgRrlFy bWRlHkfT++ysNF6Y0iYeX+3nwxxGkU0jk+Cn8W4KkpEk5e6V56pqmYHOpN4gYGcR X2gT5OLzdlbz3wUYIyltHVLVT5Zr2dSAFCe7U+WxUZE/hTXy5YPGm/Xsbcr+draO cTse6EmSKTu9LynW3++Zf1GfEJzMxl8ALQxg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=message-id:to:subject:from:date:in-reply-to :mime-version:content-type:content-transfer-encoding; s=arcseal; t=1715519810; bh=ZUvQadHoOpZ/iKACaWkbpmeJAyNv2nzeI+Bc1JoRPw8=; b= ajA0GQDsydyl1CmeY99R0r0vTCRH3B2wJWthUScmMLMVIU4aAmhU7PtI1E7eoNGq K2x0QFI7tpZpaHx7CuLVTFIgWUK1bMRTS0JnYLohOBjnNneQkBEp11oqWfzxxao9 GizQou/Qnu8lNsOkqsGFufI9I4doKhGO+Pq2Lf0ApIQDy7JXhNOSApckCaBYVJeF KzLIH/ItDuUhLz2gDvUW5k0odxbKRst048vggdmQhg7ipxlaj3awp2FJE1oa6prO AOAiUSz73NSZYbUM74GPq07wrFBJNwuCeOuKfKlR5H1x4wkOyk/VPYKHFhSQa0bu 5BMH72RMzGjMaWOy3Tn2iQ== 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=hamnavoe.com; iprev=pass smtp.remote-ip=46.235.227.24 (mx2.mythic-beasts.com); spf=pass smtp.mailfrom=miller@hamnavoe.com smtp.helo=mx2.mythic-beasts.com; x-aligned-from=domain_pass (Domain match); x-me-sender=none; x-ptr=pass smtp.helo=mx2.mythic-beasts.com policy.ptr=mx2.mythic-beasts.com; x-return-mx=pass header.domain=hamnavoe.com policy.is_org=yes (MX Records found: mx2.mythic-beasts.com,mx1.mythic-beasts.com); x-return-mx=pass smtp.domain=hamnavoe.com policy.is_org=yes (MX Records found: mx2.mythic-beasts.com,mx1.mythic-beasts.com); 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: gggruggvucftvghtrhhoucdtuddrgedvledrvdegvddgiedvucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpefkvffuhf ffjgggtgfgsehtjehjtddttddvnecuhfhrohhmpeftihgthhgrrhguucfoihhllhgvrhcu oeelfhgrnhhssehhrghmnhgrvhhovgdrtghomheqnecuggftrfgrthhtvghrnhepjeeike ethfduhfejueejjeelhedvvefffffguddtkedvvdeiheeffedtheevtefgnecuffhomhgr ihhnpehstghivghntggvughirhgvtghtrdgtohhmnecukfhppeegiedrvdefhedrvddvje drvdegnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgeeirddv feehrddvvdejrddvgedphhgvlhhopehmgidvrdhmhihthhhitgdqsggvrghsthhsrdgtoh hmpdhmrghilhhfrhhomhepoehmihhllhgvrheshhgrmhhnrghvohgvrdgtohhmqedpnhgs pghrtghpthhtohepuddprhgtphhtthhopeeolehfrghnsheslehfrghnshdrnhgvtheq X-ME-VSScore: 0 X-ME-VSCategory: clean Received-SPF: pass (hamnavoe.com: Sender is authorized to use 'miller@hamnavoe.com' in 'mfrom' identity (mechanism 'include:_spf.mythic-beasts.com' matched)) receiver=tb-mx1.topicbox.com; identity=mailfrom; envelope-from="miller@hamnavoe.com"; helo=mx2.mythic-beasts.com; client-ip=46.235.227.24 Received: from mx2.mythic-beasts.com (mx2.mythic-beasts.com [46.235.227.24]) (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:16:49 -0400 (EDT) (envelope-from miller@hamnavoe.com) Received: by mailhub-hex-d.mythic-beasts.com with esmtpsa (TLS1.2) tls TLS_RSA_WITH_AES_256_CBC_SHA (Exim 4.94.2) (envelope-from ) id 1s694K-00GjdU-J0 for 9fans@9fans.net; Sun, 12 May 2024 14:16:48 +0100 Message-ID: To: 9fans@9fans.net From: Richard Miller <9fans@hamnavoe.com> Date: Sun, 12 May 2024 14:16:47 +0100 In-Reply-To: <2dda1745-c644-4d9b-b436-26aaf3380192@posixcafe.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-BlackCat-Spam-Score: 12 Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: e758ab84-1061-11ef-a9dd-a5f3cf502973 Archived-At: =?UTF-8?B?PGh0dHBzOi8vOWZhbnMudG9waWNib3guY29tL2dyb3Vwcy85?= =?UTF-8?B?ZmFucy9UNTYzOTdlZmY2MjY5YWYyNy1NYzdjYWE3MWU2OTAwYTQzNWJiZTRh?= =?UTF-8?B?OWI2Pg==?= List-Help: List-Id: "9fans" <9fans.9fans.net> List-Post: List-Software: Topicbox v0 List-Subscribe: Precedence: list Reply-To: 9fans <9fans@9fans.net> Subject: [9fans] one weird trick to break p9sk1 ? List-Unsubscribe: , Topicbox-Delivery-ID: 2:9fans:437d30aa-c441-11e9-8a57-d036212d11b0:522be890-2105-11eb-b15e-8d699134e1fa:Mc7caa71e6900a435bbe4a9b6:1:8YG_q1y3GaMRMUDVWZ8B7ARXloWUy751MeYF9p7WBGs 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. 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 of = attempts in a short time, > in other words triple DES is not computationally hard to brute force t= hese days. >=20 > 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 ke= ys of the client and server. Provided, of course, that the random teenager som= ehow is able to listen in on the conversation between my p9sk1 clients and serve= rs. 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 publica= tion of the details. Ori's recent claim in 9fans seemed more specific: > 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. 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 ...=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. When Jacob says "triple DES is not computationally hard to brute force thes= e 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 l= ines: 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 att= ack. 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-Mc7caa= 71e6900a435bbe4a9b6 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription