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.8 required=5.0 tests=DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,DKIM_VALID,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, 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 6A690240D5 for ; Sun, 12 May 2024 16:25:54 +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 3D35A3327C for ; Sun, 12 May 2024 10:25:54 -0400 (EDT) (envelope-from bounce.mM2b019138d47049a2ec5d3ecb.r522be890-2105-11eb-b15e-8d699134e1fa@9fans.bounce.topicbox.com) Received: by tb-mx1.topicbox.com (Postfix, from userid 1132) id 3794B1902C06; Sun, 12 May 2024 10:25:54 -0400 (EDT) ARC-Authentication-Results: i=2; topicbox.com; arc=pass; dkim=pass (2048-bit rsa key sha256) header.d=gmail.com header.i=@gmail.com header.b=l/8kDcV0 header.a=rsa-sha256 header.s=20230601 x-bits=2048; dmarc=pass policy.published-domain-policy=none policy.published-subdomain-policy=quarantine policy.applied-disposition=none policy.evaluated-disposition=none (p=none,sp=quarantine,d=none,d.eval=none) policy.policy-from=p header.from=gmail.com; spf=pass smtp.mailfrom=23hiro@gmail.com smtp.helo=mail-pj1-f43.google.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=mime-version:references:in-reply-to:from:date :message-id:subject:to:content-type:content-transfer-encoding :list-help:list-id:list-post:list-subscribe:reply-to :list-unsubscribe; s=sysmsg-1; t=1715523954; bh=pkti0o5cawEycaTV CQemMR8H17h9z0w+W1OpgCWMX3c=; b=nrcsyoMb0SgxZGqZFPj8XN/lS3oTGXVA bZ1VePS8Jl3GbpM+p5o2zRD7loDe2CvofLX+njEDNYc723E1KK9M9R+/V/9bt1au R+LVKHG5fDzlPPzbJodUzAT/Qxj3iMtpAA69A/shuWBCcheRIe9inG2SvD6MD3Yt akuo2IQ2m/E= ARC-Seal: i=2; a=rsa-sha256; cv=pass; d=topicbox.com; s=sysmsg-1; t= 1715523954; b=kiIPvDjoHRJ7WX8JXpyUJFdWoPexdjfX6xHwfOB1p/+iKzYpmh 4lYEf5FU36603MY9Zn8beQWVYuAwZhqdWwDlO0W/IAdLU6/miP8VpFsb4QxWNKQe K83+OZH7vEYIqCrloMLQFGlT3rRQRcaEiSTgiqqw3bQsQ9Kze9tckT908= Authentication-Results: topicbox.com; arc=pass; dkim=pass (2048-bit rsa key sha256) header.d=gmail.com header.i=@gmail.com header.b=l/8kDcV0 header.a=rsa-sha256 header.s=20230601 x-bits=2048; dmarc=pass policy.published-domain-policy=none policy.published-subdomain-policy=quarantine policy.applied-disposition=none policy.evaluated-disposition=none (p=none,sp=quarantine,d=none,d.eval=none) policy.policy-from=p header.from=gmail.com; spf=pass smtp.mailfrom=23hiro@gmail.com smtp.helo=mail-pj1-f43.google.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 Policy is not at enforcement); dkim=pass (2048-bit rsa key sha256) header.d=gmail.com header.i=@gmail.com header.b=l/8kDcV0 header.a=rsa-sha256 header.s=20230601 x-bits=2048; dmarc=pass policy.published-domain-policy=none policy.published-subdomain-policy=quarantine policy.applied-disposition=none policy.evaluated-disposition=none (p=none,sp=quarantine,d=none,d.eval=none) policy.policy-from=p header.from=gmail.com; iprev=pass smtp.remote-ip=209.85.216.43 (mail-pj1-f43.google.com); spf=pass smtp.mailfrom=23hiro@gmail.com smtp.helo=mail-pj1-f43.google.com; x-aligned-from=pass (Address match); x-google-dkim=pass (2048-bit rsa key) header.d=1e100.net header.i=@1e100.net header.b=cgDVgfj7; x-me-sender=none; x-ptr=pass smtp.helo=mail-pj1-f43.google.com policy.ptr=mail-pj1-f43.google.com; x-return-mx=pass header.domain=gmail.com policy.is_org=yes (MX Records found: gmail-smtp-in.l.google.com,alt2.gmail-smtp-in.l.google.com,alt3.gmail-smtp-in.l.google.com,alt1.gmail-smtp-in.l.google.com,alt4.gmail-smtp-in.l.google.com); x-return-mx=pass smtp.domain=gmail.com policy.is_org=yes (MX Records found: gmail-smtp-in.l.google.com,alt2.gmail-smtp-in.l.google.com,alt3.gmail-smtp-in.l.google.com,alt1.gmail-smtp-in.l.google.com,alt4.gmail-smtp-in.l.google.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= mime-version:references:in-reply-to:from:date:message-id:subject :to:content-type:content-transfer-encoding:list-help:list-id :list-post:list-subscribe:reply-to:list-unsubscribe; s=dkim-1; t=1715523954; x=1715610354; bh=I1Cs5TTR2jmmEB2ZrvJho5nwdJFyHC9o 4tSOzZev3aM=; b=EjBQFZmEjzgnJKunbs42Lgh3hwum3XE98dg3zbdxvtffJeC/ ivid2L1MKwHUjL3HNN5v+ebPRIRQY6S8cuA1pS/9TR9v4CzlTNtleJqZEk5Y4M6C Vsap1FEkx4x2H85UoafVmEGXvk07FaoF2eiNxbXsPDMYAEf3EhdG9/jnj0A= Received: from tb-mx1.topicbox.com (localhost.local [127.0.0.1]) by tb-mx1.topicbox.com (Postfix) with ESMTP id AF7C519027DE for <9fans@9fans.net>; Sun, 12 May 2024 10:25:39 -0400 (EDT) (envelope-from 23hiro@gmail.com) Received: from tb-mx1.topicbox.com (localhost [127.0.0.1]) by tb-mx1.topicbox.com (Authentication Milter) with ESMTP id 47457990FF1; Sun, 12 May 2024 10:25:39 -0400 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1715523939; b=yHnMhKcDJT56MZ9hrdDnxjmrzEV1rl0U1YqiJnn6q+FHpWJ4a9 3NStyG57PLeUaZ6O8LgiiiHnYcqI+HEedZvXPaBTspEVNvZEpDGVoB2Mp0zaW01r RPl7/6dmGdIxGsBmoWWbZVmlVVM+iV5i0D2nWnBaBH1uKKADJ6xlma5RJnnh08Us p8QabKsV4+TW+uFIIhUxB51yGOobMMM3PLWPk9LwUyHlUjcS2PJfkzIFIH5lTwJs M/RhYc+IB2F7oVMnnrW10+BnwVL900ZI72gxi/VpzthMeJq/MV92zdgPHEygRmZp /Vpcp8YbAEaV130wKFafHHtz92Wt+zKwiFYg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=mime-version:references:in-reply-to:from:date :message-id:subject:to:content-type:content-transfer-encoding; s=arcseal; t=1715523939; bh=EeYKbxf9AUNeZcUvBHtiN3vW27/fZuKpPyr fxJ0dUCI=; b=u+RFwj/DSxp+N8OhbMvmGufeuFi64i+1KFOfG6n8XEJNmyxAOJM vZh4uSZ9GBhDhAIU5rgYG4WvUDub3A9v5vSYPQ+t6XkPr/xDbOt4q4KXHD/Q+bzK l4W4od5X16O3pLo1feZHuTUMqijaFkxGY/q3Q35qvPnsVNkGVMp0IG0Zk7BzuxZO D1mrnXQNWTV8mQV5jSMUx7epGzZvd1QEjlcz+cNjg3CFxEyMFpa5nm5JNr3JWN// fbH52ayN/8OFd2QqeSMAlaFGUKhlDKmH90f3xcik4XOi7WGZvxdn9PBHtJPlsBp4 eStbEntHr7zwP+aFTgZHcnwifL3FqziSg9Q== ARC-Authentication-Results: i=1; tb-mx1.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC Policy is not at enforcement); dkim=pass (2048-bit rsa key sha256) header.d=gmail.com header.i=@gmail.com header.b=l/8kDcV0 header.a=rsa-sha256 header.s=20230601 x-bits=2048; dmarc=pass policy.published-domain-policy=none policy.published-subdomain-policy=quarantine policy.applied-disposition=none policy.evaluated-disposition=none (p=none,sp=quarantine,d=none,d.eval=none) policy.policy-from=p header.from=gmail.com; iprev=pass smtp.remote-ip=209.85.216.43 (mail-pj1-f43.google.com); spf=pass smtp.mailfrom=23hiro@gmail.com smtp.helo=mail-pj1-f43.google.com; x-aligned-from=pass (Address match); x-google-dkim=pass (2048-bit rsa key) header.d=1e100.net header.i=@1e100.net header.b=cgDVgfj7; x-me-sender=none; x-ptr=pass smtp.helo=mail-pj1-f43.google.com policy.ptr=mail-pj1-f43.google.com; x-return-mx=pass header.domain=gmail.com policy.is_org=yes (MX Records found: gmail-smtp-in.l.google.com,alt2.gmail-smtp-in.l.google.com,alt3.gmail-smtp-in.l.google.com,alt1.gmail-smtp-in.l.google.com,alt4.gmail-smtp-in.l.google.com); x-return-mx=pass smtp.domain=gmail.com policy.is_org=yes (MX Records found: gmail-smtp-in.l.google.com,alt2.gmail-smtp-in.l.google.com,alt3.gmail-smtp-in.l.google.com,alt1.gmail-smtp-in.l.google.com,alt4.gmail-smtp-in.l.google.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: gggruggvucftvghtrhhoucdtuddrgedvledrvdegvddgjeeiucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpeggfhgjhf ffkffuvfgtgfesthhqredttddtjeenucfhrhhomhephhhirhhouceovdefhhhirhhosehg mhgrihhlrdgtohhmqeenucggtffrrghtthgvrhhnpeefhfejudfhhfeuteegjefhudejke effeejleettddugeejveduvdeujeetkeetfeenucffohhmrghinhepshgtihgvnhgtvggu ihhrvggtthdrtghomhdpthhophhitggsohigrdgtohhmnecukfhppedvtdelrdekhedrvd duiedrgeefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepvddt ledrkeehrddvudeirdegfedphhgvlhhopehmrghilhdqphhjuddqfhegfedrghhoohhglh gvrdgtohhmpdhmrghilhhfrhhomhepoedvfehhihhrohesghhmrghilhdrtghomheqpdhn sggprhgtphhtthhopedupdhrtghpthhtohepoeelfhgrnhhsseelfhgrnhhsrdhnvghtqe X-ME-VSScore: 0 X-ME-VSCategory: clean Received-SPF: pass (gmail.com ... _spf.google.com: Sender is authorized to use '23hiro@gmail.com' in 'mfrom' identity (mechanism 'include:_netblocks.google.com' matched)) receiver=tb-mx1.topicbox.com; identity=mailfrom; envelope-from="23hiro@gmail.com"; helo=mail-pj1-f43.google.com; client-ip=209.85.216.43 Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) (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 10:25:38 -0400 (EDT) (envelope-from 23hiro@gmail.com) Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-2af71daeec1so943157a91.0 for <9fans@9fans.net>; Sun, 12 May 2024 07:25:38 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715523938; x=1716128738; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=EeYKbxf9AUNeZcUvBHtiN3vW27/fZuKpPyrfxJ0dUCI=; b=cgDVgfj7dGEgrviPZl39WQYJFJ0kobt6L/Y6JXrN1cPgZIC5ng0qfhMamBSAMn5ZSH /xcBUk8flA4/tGTMfOfwgU50PHMwk3o3S7lccQKKbbz5KiWhmaDB9O+rz7uhrGWpkgs/ 4vpa+4V0DAqRMCH7aZ9xLqG3eWITMxNVx4YZDNzhtbKgYiRFmfC6zovh7sd6grThwydF uXPR0wsf5rIg5XXsSsClafDCHWga/mwlD1WRs2/Hg89mddsZNj00SOlhwkpAUZipfLSi Ub8VPsl/kVYtdCprUJtpRXBhlrnQ+iSYwBQdevOiaBovYN3uH+K+etJLVivkbsYL7jg+ OjHA== X-Gm-Message-State: AOJu0YzbPDbfS3ywGp8JQMc6yaSAEY0cx0PGO5ji2n9XQb7cWMIxFUoO pMeEKZwQrC9aDeNI6UfX/AkIm5tl5G3xYtkgkwNY6gMnh3Poq+N0C/OE1CHym/RnIs1ueEmD8Ab SaUdd9aMs37AumM6iNufydWYGYWqtzg== X-Google-Smtp-Source: AGHT+IElhQKclyvlF7iatA0ceVBd0uvHSvUfdTubNebmC+v7jVlPvceY4u0Ek71Sv8Cz3fhwrIqAAQUrH091cfIshLA= X-Received: by 2002:a17:90b:2389:b0:2b1:99fd:4eea with SMTP id 98e67ed59e1d1-2b6ccd7d042mr7340832a91.2.1715523937820; Sun, 12 May 2024 07:25:37 -0700 (PDT) MIME-Version: 1.0 References: <2dda1745-c644-4d9b-b436-26aaf3380192@posixcafe.org> In-Reply-To: From: hiro <23hiro@gmail.com> Date: Sun, 12 May 2024 16:25:26 +0200 Message-ID: Subject: Re: [9fans] one weird trick to break p9sk1 ? To: 9fans <9fans@9fans.net> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: 850cfeee-106b-11ef-a103-9b8d620a7653 Archived-At: =?UTF-8?B?PGh0dHBzOi8vOWZhbnMudG9waWNib3guY29tL2dyb3Vwcy85?= =?UTF-8?B?ZmFucy9UNTYzOTdlZmY2MjY5YWYyNy1NMmIwMTkxMzhkNDcwNDlhMmVjNWQz?= =?UTF-8?B?ZWNiPg==?= 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:M2b019138d47049a2ec5d3ecb:1:fFwfByDFoyMCnRSZnMSOzosKo5qEwmNBA_bVsn0IhCE 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=E2=80=AFPM Richard Miller <9fans@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. > > 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 o= f 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 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. > > 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 publi= cation > 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. >=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 ... > 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. >=20 ------------------------------------------ 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T56397eff6269af27-M2b019= 138d47049a2ec5d3ecb Delivery options: https://9fans.topicbox.com/groups/9fans/subscription