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=-0.6 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [IPv6:2600:3c01:e000:146::1]) by inbox.vuxu.org (Postfix) with ESMTP id BDACA2B802 for ; Wed, 13 Mar 2024 02:23:14 +0100 (CET) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 3FE4442829; Wed, 13 Mar 2024 11:23:10 +1000 (AEST) Received: from mail-pj1-x1030.google.com (mail-pj1-x1030.google.com [IPv6:2607:f8b0:4864:20::1030]) by minnie.tuhs.org (Postfix) with ESMTPS id 468B242828 for ; Wed, 13 Mar 2024 11:23:05 +1000 (AEST) Received: by mail-pj1-x1030.google.com with SMTP id 98e67ed59e1d1-29bfc3ca816so2134487a91.0 for ; Tue, 12 Mar 2024 18:23:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=swtch.com; s=google; t=1710292984; x=1710897784; darn=tuhs.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=un2sfi2Nd5vTubhQTRXt25AhqDFWWyMUBT1tCvG85PE=; b=FIY7ywKskFCG70MiIS1YAzbc4S4PRHAvizITd8dB+lF8U+dS4R6Ug86OSvm6zGMdzx 5RHhJlPm+dNpXISp3mDYreVjXXSxmJohkRf3CqGGF1fSSGTImw1YtK5OK+e7EDS3S2+3 Zuomx2CTLBXYMlUKINS0bgKirV6ko2F76qfg+7kRCBY9cMPqp7lNO6xWNbJY6zkSFNXI 5QIyEOxSMs47txf0Ysm2L0fK0+FzOoBzF7PP8ZYPwSmvGZzP8rUXjCXOFsw1GfRdfigb o6YXSoBGOGt3hKmYGEYHWR5gMvazXXh2En81lRBvYEx/+npBQxu/SW+zVvuNgUStYpQS xWNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710292984; x=1710897784; h=cc: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=un2sfi2Nd5vTubhQTRXt25AhqDFWWyMUBT1tCvG85PE=; b=Efe0NxyfW6s6uj8MdyzrgKs5LclzGDT6DotDJo+7zuOPuqt03eMXuCSS1zK4y7kGg1 QxehOl7umRpJl8ToTUhaReF/SZQBPJ5ZEywe98wxrxHDF2nWK5U9UobPXjoiIaJRj32b odbwfobsGo3ZLkh92dYMyV2iTwcSGtwpsBT1uUkhYIfI93mQ6kML32/1ZI5mEsGToVn9 nb5s4xv2pktvx1Y8TbH64DSV6sVz69G/KDXzIlqK7rSlGMyqUwB2f08VmjcQbIwUjnKm a2pX99Ja37ROe7GFZvlqvu3CEtRgoBV5RemuqQ8mtGol9jiErrAfM40iaLpB/Bnq5ZH0 Q5NA== X-Forwarded-Encrypted: i=1; AJvYcCVurY2x3ogpzEUxqleCQYxkjv7FpyO1DbN0ieXfVw4RI39bz9LMIR8NdvF7Z9YwybjbKmPeF9hx/Vwf2q1Z X-Gm-Message-State: AOJu0Yy/kzD9i2AdXWJW036JiB+0x7dQqM1OdkEtzbHoR4doPEAa0icc P9O8W+/Q1bhI90EuUt3P1ZSIeiepqqRnsfQC+TzzMKx1aDe687vpJQAS3t+RnnmP1KuEfSAP8Go O/+Btq/An/9KQaN2fyatD8IEJhT3fNr5Si4PuVeKSnONPJdA= X-Google-Smtp-Source: AGHT+IH48fyBaaQ3MGqeKXJ2NMhSpL59n1GWwmNBCFHJmPMZOM2B6ng8dxu4/HSoQ9oC3ZhnWnsYuKjsNZXKuJfcPuA= X-Received: by 2002:a17:90a:c684:b0:29b:277d:2590 with SMTP id n4-20020a17090ac68400b0029b277d2590mr11465708pjt.34.1710292984484; Tue, 12 Mar 2024 18:23:04 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Russ Cox Date: Tue, 12 Mar 2024 21:22:53 -0400 Message-ID: To: Paul Winalski Content-Type: multipart/alternative; boundary="000000000000cd71610613809dc1" Message-ID-Hash: VUV5HG5TENXMYCCTCEIUJNAXXPRN3N3C X-Message-ID-Hash: VUV5HG5TENXMYCCTCEIUJNAXXPRN3N3C X-MailFrom: rsc@swtch.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: Douglas McIlroy , TUHS main list X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: early unix rand List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000cd71610613809dc1 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Tue, Mar 12, 2024 at 12:23=E2=80=AFPM Paul Winalski wrote: > On 3/12/24, Douglas McIlroy wrote: > > > > That was a memorable > > error. Guessing that the passwords were generated by > > a simple encoding of the output of rand, Ken promptly > > broke 100% of the newly "hardened" password file. > > To do that wouldn't you need to know the seed value that was used? Or > did this version of rand() always generate the same sequence of > pseudo-random numbers? Any LCG-based version of rand (including, say, java.lang.Math.random) always generates the same periodic sequence of numbers; the seed only controls where in the sequence you start (you start where the seed appears)= . Worse, any LCG-based rand truncated to k bits is itself just a periodic sequence of the 2^k possible truncations. The trivial k=3D1 case of this is that if you look at the bottom bit of successive rand outputs on any of these generators, it is always alternating between even and odd, no matter what constants you pick. (Almost. If you pick bad constants you could get all even or all odd instead.) I don't know what the simple BSD encoding was, but those two facts combined mean that an example of an encoding that would be easily broken would be to pick a fixed-length sequence of letters drawn from "abcdefghijklmnopqrstuvwxyz123456"[rand()&31]. That would just produce the same 32-character permutation over and over again, so there would only be 32 possible passwords, depending only on where in the sequence you start. Best, Russ --000000000000cd71610613809dc1 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Tue, Mar 12, 2024 at 12:23=E2=80=AFPM = Paul Winalski <paul.winalski@gmail.com> wrote:
On 3/12/24, Douglas M= cIlroy <douglas.mcilroy@dartmouth.edu> wrote:
>
> That was a memorable
> error. Guessing that the passwords were generated by
> a simple encoding of the output of rand, Ken promptly
> broke 100% of the newly "hardened" password file.

To do that wouldn't you need to know the seed value that was used?=C2= =A0 Or
did this version of rand() always generate the same sequence of
pseudo-random numbers?

Any LCG-based versio= n of rand (including, say, java.lang.Math.random)
always generate= s the same periodic sequence of numbers; the seed only=C2=A0
cont= rols where in the sequence you start (you start where the seed appears).

Worse, any LCG-based rand truncated to k bits is its= elf just a periodic=C2=A0
sequence of the 2^k possible truncation= s. The trivial k=3D1 case of this is that if
you look at the bott= om bit of successive rand outputs on any of these
generators, it = is always alternating between even and odd, no matter
what consta= nts you pick. (Almost. If you pick bad constants you could
get al= l even or all odd instead.)

I don't know what = the simple BSD encoding was, but those two facts
combined mean th= at an example of an encoding that would be easily broken
would be= to pick a fixed-length sequence of letters drawn from
"abcd= efghijklmnopqrstuvwxyz123456"[rand()&31].
That would jus= t produce the same 32-character permutation
over and over again, = so there would=C2=A0only be 32 possible passwords,
depending = only on where in the sequence you start.

Best,
Russ
--000000000000cd71610613809dc1--