<div dir="ltr"><div dir="ltr">On Tue, Mar 12, 2024 at 12:23 PM Paul Winalski <<a href="mailto:paul.winalski@gmail.com" target="_blank">paul.winalski@gmail.com</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 3/12/24, Douglas McIlroy <<a href="mailto:douglas.mcilroy@dartmouth.edu" target="_blank">douglas.mcilroy@dartmouth.edu</a>> wrote:<br>
><br>
> That was a memorable<br>
> error. Guessing that the passwords were generated by<br>
> a simple encoding of the output of rand, Ken promptly<br>
> broke 100% of the newly "hardened" password file.<br>
<br>
To do that wouldn't you need to know the seed value that was used?  Or<br>
did this version of rand() always generate the same sequence of<br>
pseudo-random numbers?</blockquote><div><br></div><div>Any LCG-based version of rand (including, say, java.lang.Math.random)</div><div>always generates the same periodic sequence of numbers; the seed only </div><div>controls where in the sequence you start (you start where the seed appears).</div><div><br></div><div>Worse, any LCG-based rand truncated to k bits is itself just a periodic </div><div>sequence of the 2^k possible truncations. The trivial k=1 case of this is that if</div><div>you look at the bottom bit of successive rand outputs on any of these</div><div>generators, it is always alternating between even and odd, no matter</div><div>what constants you pick. (Almost. If you pick bad constants you could</div><div>get all even or all odd instead.)</div><div><br></div><div>I don't know what the simple BSD encoding was, but those two facts</div><div>combined mean that an example of an encoding that would be easily broken</div><div>would be to pick a fixed-length sequence of letters drawn from</div><div>"abcdefghijklmnopqrstuvwxyz123456"[rand()&31].</div><div>That would just produce the same 32-character permutation</div><div>over and over again, so there would only be 32 possible passwords,<br></div><div>depending only on where in the sequence you start.</div><div><br></div><div>Best,</div><div>Russ</div></div></div>