[PATCH] mkswap: generate UUID

Rob Landley rob at landley.net
Fri Jun 19 09:48:21 UTC 2009


On Thursday 18 June 2009 21:10:25 Colin Watson wrote:
> On Thu, Jun 18, 2009 at 05:24:04PM -0500, Rob Landley wrote:
> > On Thursday 18 June 2009 14:56:53 Colin Watson wrote:
> > > Is this an identical algorithm to that used in libuuid? It doesn't look
> > > like it, and I'm not happy with increasing the probability that UUIDs
> > > might turn out not to be universally unique. If you apply it this way
> > > I'll certainly have to patch it out in the version I distribute ...

[patronizing ommitted for space]

> > (You can argue that /dev/urandom isn't _truly_ random, so maybe there's
> > only a 95% chance the the sun would run out of fuel first, but I really
> > don't care.)
>
> Let me expand on my previous reply. I know I'm coming to this list as a
> supplicant asking for a patch to be accepted, but on reflection I'm
> actually not really willing to be patronised like this without defending
> myself a bit.

Sure.  (For the record, I patronize everybody.  Including myself.  Which takes 
practice.)

> While the metaphors above are certainly colourful, the code that Denys
> posted does not have randomness even close to 2^128.

The code I posted read from the Linux kernel's random number generator.  The 
parenthetical I've mentioned above eplicitly mentions /dev/urandom.  I agree 
that using a pseudo-random number generator here isn't good enough.

> Please bear in mind that I was replying specifically to Denys' patch,
> not to an abstract concept of a patch that used proper random numbers.

Your stated concern was that it was not "an identical algorithm to that used 
in libuuid".  How is that a criteria for "is this new method good enough" 
instead of "the old method is the only acceptable way"?

> The reason I'm concerned about it is that I *do* understand the scale of
> these things and that patch (which is in master now) isn't in the right
> ballpark at all. I spent several days and nights of my life last year on
> very little sleep dealing with cleanup and mitigation of the notorious
> Debian openssl bug, in which an accidental mispatch caused a shortage of
> randomness such that only 2^15 distinct keys were possible for each key
> type/length combination. I know what powers of two do, and the kinds of
> thing that happen if you don't have enough of them.

Which is why I use the kernel's random numer generator directly, because if 
something goes wrong with that one people will notice, and only the kernel has 
access to hardware entropy sources (you can't create true entropy in software, 
it's theoretically impossible) so library wrappers over the entropy the kernel 
provides are deeply pointless.

I admit I use urandom instead of /dev/random because programs hanging aren't 
really an improvement over falling back to a pseudo-random number generator 
that's been very, very, very thoroughly initialized.  (If the system has no 
hardware entropy inputs to speak of, you're screwed anyway.)

> Now, granted, it doesn't matter so much if swap UUIDs are really
> universally unique when you compare them to something like SSH keys. But
> let's consider the example of a large organisation deploying Linux
> automatically on lots of machines. We can probably expect those machines
> to be of roughly the same specification such that they'll reach similar
> stages of the installer at about the same time, plus or minus a few
> seconds,

The traditional uuid initialization method (where the fields actually mean 
something) depends heavily on your mac addresses being unique (which is _not_ 
the case under most emulators) and your clock granularity not sucking (ditto).

Choose your failure mode.

> and we can certainly expect their deployment to be such that
> the installer takes an identical or nearly identical code path each
> time. I'd be surprised at this point if you had much more than 2^24
> random bits to play with. The probability of real collisions within the
> organisation is no longer negligible.

Ok, so your contrived setup is that an organization somehow powers on hundreds 
of machines at exactly the same instant (which means they've probably blown 
the breakers for room, but let's ignore that for the moment).  They redo 
mkswap every single boot for some reason, first thing when the system's had the 
minimum possible activity, and then _find_ that swap partition by uuid.

I'd like to pause here to say that the SCSI layer's design of throwing every 
single device into a single large pot and giving it a stir, discarding 
transport type, was deeply stupid.  And the hotplug guys taking the SCSI layer 
as a model for performing device enumeration were _utterly_ misguided.  So 
this whole "the uuid must be globally unique or we'll confuse USB devices with 
sata devices because we can't find our hardware with both hands and a map" 
thing is a side effect of the mainframe guys going "feel our pain, desktop 
people, and solve our problems for us!" and the desktop guys going "I bought a 
mac".

But that's a side issue I only bring up because I have a headache.  Back to 
your hypothetical situation:

You ignore the various sources of uniqueness the kernel has (like cpuid) that 
aren't credited as entropy pool bits (since their cryptographically 
predictable to a local attacker) but which are still folded into the pool to 
perturb the output so it doesn't match what you get from other machines.  
You're ignoring the way modern PC chipsets (and some embedded chipsets for 
that matter) have a hardware random number generator built into them, that 
modern clock chipsets give something near nanosecond resolution, that sound 
cards act as sources of essentially instant infinite entropy even without a 
microphone plugged in (grab the low bits, it's funky quantum electrical 
noise), and so on...

The concern here is what exactly, that the uuid of one machine's swap 
partition might match the uuid of another machine's swap partition?  Or that 
the mkswap uuid might match the ext2 partition uuid?  (Note that busybox 
hasn't got a mkfs.ext2 implememntation at the moment, so if the ext2 uuid is 
likely to match something we do then that's not really a deficiency in what 
_we're_ doing, is it?)

> If you then use the same UUID generation algorithm for something more
> important than swap, such as mke2fs,

...then you get the opportunity to complain at that point.

You're not only arguing about a theoretical you've never seen, which even YOU 
probably aren't sure you could reproduce under laboratory conditions given 
weeks to do so and labs full of hardware, and which I suspect even _just_ the 
cpuid thing plus an advancing clock would be enough to prevent, considering 
that the Linux random number generator is based on repeatedly folding together 
its input data via sha1sum so each new bit of entropy perturbs the entire 
pool...

You're arguing that if we add _more_ commands in future, _then_ it might 
become a problem.

Uh-huh.

> then it's actually quite plausible
> that real failures will happen due to things like UUID mounts over
> iSCSI,

Here's a test you can do:

Get a room full of machines.  Boot them with an initramfs that (as its very 
first action when init gets spawned) spits out 128 bits of /dev/urandom output 
via an http post to a server that's logging them all, and which then 
immediately reboots to do it again.

Feel free to carefully choose your hardware so you've got a processor with no 
cpuid, a chipset with no hardware random number generator, no entropy-
producing peripherals, a clock with horrible granularity, etc.

Leave that running until you get a single collision, then get back to me.

It might just be possible that you could do this running under an emulator 
(see "can't produce entropy in software", above), but as I mentioned the 
traditional method of combining a mac address with the clock isn't going to do 
you much good there either.

> or swapping a disk between machines for some reason, or that kind
> of thing. Still a rare failure, but I could well imagine it using up a
> fair chunk of support time. From this point of view, the kinds of
> failures that are rare but do still occasionally happen are often worse
> than the kinds of failures that you see all the time, because you can
> fix the latter fairly quickly and move on with your life.

I'm aware that fortune 500 corporations care about million to one chances as 
soon as they get their millionth customer, yes.  (Usually in the context of 
lawsuits.)

But I'm not convinced this is a real problem.

> I already know that *properly-generated* UUIDs are sufficiently
> universally unique for all remotely sensible purposes.

Your definition of "properly generated" seems to imply, among other things, 
"they didn't do it under qemu's default configuration".

> That's why I've
> already deployed them for filesystem mounting in one distribution with
> millions of users, and am working on deploying them in another ... It's
> your mailing list, but it would make things a lot easier to have the
> courtesy of not being assumed to be entirely naïve.

It's actually Denys's mailing list these days.  I'm just a civilian. :)

> UUID generation is not all that far away from being a cryptographic
> algorithm. Doing cryptography properly is hard work, and people put a
> lot of effort into specifying algorithms that get it right.

Yes, which is why I prefer to let the kernel do it for me.  If the kernel 
isn't producing decent random numbers, many bad things happen.  This isn't 
anywhere near the biggest.

> Doing cryptography badly is very easy.

It's good to see I'm not the only one being patronizing in this conversation.

> Please don't do a bodge job on it for
> the sake of a few hundred bytes that we could easily arrange for most
> people to configure away.

Your argument boils down to "the kernel might be so broken that the output of 
/dev/urandom isn't even _unique_, let alone unguessable.  Busybox should try 
to compensate".

I don't find this argument convincing.

> Mike Frysinger's entirely right that it should
> be configurable - I rather doubt that the smallest embedded targets have
> much use for UUID filesystem identification anyway!
>
>
> The generation function you (Rob) sent in
> http://lists.busybox.net/pipermail/busybox/2009-June/069690.html seems
> much better to me and largely fine, except for two mistakes:
>
>  * RFC2518 appears to be in error when it says that you should set the
>    most significant bit of the first octet of the node ID to 1. RFC4122
>    instead says you should set the *least* significant bit, which
>    matches the description of IEEE 802 MAC addresses in
>    http://en.wikipedia.org/wiki/MAC_address.

I vaguely recall figuring out what it _should_ do experimentally (looking at 
hex dumps) and then documenting it based on what the RFC said.  But I wrote 
that code back around 2007, so I don't really remember the details all that 
clearly.  Feel free to tweak if it makes you feel better. 

>  * Your code uses uuid[11] as if it were the first octet of the node ID.
>    I think this should in fact be uuid[10].

Endianness issue, I expect.  (The code I started with was passing in a 
structure and I was treating it as a char array.  It probably did endianness 
conversions later on.)

Again, feel free to tweak.

> If I were writing it I think I'd follow libuuid's lead and add some
> stirring about with rand() and such as a bit of an insurance policy just
> in case /dev/urandom is broken (you'd still be screwed, of course, but
> at least less screwed than always getting all zeroes or whatever), but
> that may not be necessary in the context of busybox.

That pretty much goes against everything busybox stands for, yes.

But in general, defensive programming to hide failures so bugs don't get fixed 
is a horrible idea.  Especially a failure _that_serious_ which has systemwide 
consequences like "our packet sequence numbers don't work", "passwords have no 
salt", "our ssl keys are crap", and so on.

If /dev/urandom is broken, the system is completely horked in dozens of 
different ways, and trying to make _this_ way hide the bug so maybe you go a 
little longer without noticing how badly hosed your system is... that's not 
really helping.

> Can I recommend at least looking at libuuid and seeing what can be used,
> though? It could be made a lot smaller simply by stripping out all the
> time-based UUID stuff and assuming the existence of /dev/urandom, and as
> I said above this should all be configured off by default.

Here are the last few lines of e2fsprogs/old_e2fsprogs/uuid/gen_uuid.c:

void uuid_generate_random(uuid_t out)
{
        uuid_t  buf;
        struct uuid uu;

        get_random_bytes(buf, sizeof(buf));
        uuid_unpack(buf, &uu);

        uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;
        uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x4000;
        uuid_pack(&uu, out);
}

/*
 * This is the generic front-end to uuid_generate_random and
 * uuid_generate_time.  It uses uuid_generate_random only if
 * /dev/urandom is available, since otherwise we won't have
 * high-quality randomness.
 */
void uuid_generate(uuid_t out)
{
        if (get_random_fd() >= 0)
                uuid_generate_random(out);
        else
                uuid_generate_time(out);
}

The actual get_random_bytes implementation does various voodoo to try to make 
the output of /dev/urandom _more_ random, which is about on par with calling 
memset twice on the same data just to be sure, and there's a _reason_ it was 
removed from busybox.  (My understanding is that the old_e2fsprogs directory 
is there as a reference for when we get around to writing a real mke2fs for 
busybox.)

> Thanks,

Rob
-- 
Latency is more important than throughput. It's that simple. - Linus Torvalds


More information about the busybox mailing list