constant half-byte from /proc/sys/kernel/random/uuid

constant half-byte from /proc/sys/kernel/random/uuid

[Petr Ovtchenkov]

Lack of randomness during generating uuid.

Sample:

for i in 1 2 3 4 5 6 7 8 9; do cat /proc/sys/kernel/random/uuid ; done

3faf5c7e-5e1b-4b3c-a318-979653d85404
a929d2d3-e229-42ca-9f33-9c09801f41fb
c2a96cb6-0dba-401c-a9c6-dabe1dec89d6
df341de3-eb97-4327-bb63-46afd8dbfaa8
9d84d61c-0c55-4914-8bd6-7f1601110908
6d82e69b-418e-4189-b5a4-0661b6e24dcf
eb38de66-4e0b-4bd0-827b-e75ba273e85a
5585c367-754f-4bbf-81f6-8a728380860d
c074480b-ad5c-4e10-81d2-82225c449b91


See on 7th high half-byte: it '4' in
all cases---4b, 42, 40, 43, 49, 41,
4b, 4b, 4e. Checked three comps, with
similar results. All Linux-generated UUID (boot_id)
that I see in internet has '4' in this
half-byte.


cat /proc/version
Linux version 2.6.27.15 (yeti@peak) (gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)) #1 SMP Thu Feb 12 17:28:11 MSK 2009

or

Linux version 2.6.27.21 (ptr@localhost) (gcc version 4.2.4) #6 SMP Sat Apr 25 00:29:08 MSD 2009

or

Linux version 2.6.33-ARCH (thomas@evey) (gcc version 4.5.0 (GCC) ) #1 SMP PREEMPT Thu May 13 12:06:25 CEST 2010

cat /proc/cpuinfo
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 2400.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts pni monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr lahf_lm
bogomips        : 4799.97
clflush size    : 64
power management:
...

or

processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 15
model           : 75
model name      : AMD Athlon(tm) 64 X2 Dual Core Processor 4200+
stepping        : 2
cpu MHz         : 2204.555
cache size      : 512 KB
physical id     : 0
siblings        : 2
core id         : 0
cpu cores       : 2
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt rdtscp lm 3dnowext 3dnow pni cx16 lahf_lm cmp_legacy svm extapic cr8_legacy
bogomips        : 4409.11
clflush size    : 64
power management: ts fid vid ttp tm stc

...

or
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 CPU         T7200  @ 2.00GHz
stepping        : 6
cpu MHz         : 1995.264
cache size      : 4096 KB
physical id     : 0
siblings        : 2
core id         : 0
cpu cores       : 2
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge 
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm 
constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl 
vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow
bogomips        : 3992.80
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Re: constant half-byte from /proc/sys/kernel/random/uuid

[Lukasz Gromanowski]

Petr Ovtchenkov pisze:
> Lack of randomness during generating uuid.
> 
> Sample:
> 
> for i in 1 2 3 4 5 6 7 8 9; do cat /proc/sys/kernel/random/uuid ; done
> 
> 3faf5c7e-5e1b-4b3c-a318-979653d85404
> a929d2d3-e229-42ca-9f33-9c09801f41fb
> c2a96cb6-0dba-401c-a9c6-dabe1dec89d6
> df341de3-eb97-4327-bb63-46afd8dbfaa8
> 9d84d61c-0c55-4914-8bd6-7f1601110908
> 6d82e69b-418e-4189-b5a4-0661b6e24dcf
> eb38de66-4e0b-4bd0-827b-e75ba273e85a
> 5585c367-754f-4bbf-81f6-8a728380860d
> c074480b-ad5c-4e10-81d2-82225c449b91
> 
> 
> See on 7th high half-byte: it '4' in
> all cases---4b, 42, 40, 43, 49, 41,
> 4b, 4b, 4e. Checked three comps, with
> similar results. All Linux-generated UUID (boot_id)
> that I see in internet has '4' in this
> half-byte.

Hi,
quote from wikipedia[1]

"Version 4 (random)

Version 4 UUIDs use a scheme relying only on random numbers. This
algorithm sets the version number as well as two reserved bits.
All other bits are set using a random or pseudorandom data source.
Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx
with any hexadecimal digits for x but only one of 8, 9, A, or B for y.
e.g. f47ac10b-58cc-4372-a567-0e02b2c3d479."

[1] http://en.wikipedia.org/wiki/Universally_Unique_Identifier

-- 
best regards,
Lukasz

Re: constant half-byte from /proc/sys/kernel/random/uuid

[Ian Campbell]

On Tue, 2010-06-01 at 16:22 +0400, Petr Ovtchenkov wrote:
> Lack of randomness during generating uuid.
[...]
> See on 7th high half-byte: it '4' in
> all cases---4b, 42, 40, 43, 49, 41,
> 4b, 4b, 4e. Checked three comps, with
> similar results. All Linux-generated UUID (boot_id)
> that I see in internet has '4' in this
> half-byte.

This appears to be deliberate. From drivers/char/random.c:

        void generate_random_uuid(unsigned char uuid_out[16])
        {
                get_random_bytes(uuid_out, 16);
                /* Set UUID version to 4 --- truly random generation */
                uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
                /* Set the UUID variant to DCE */
                uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
        }
        EXPORT_SYMBOL(generate_random_uuid);

Version 4 UUIDs and the format used are described at
http://en.wikipedia.org/wiki/Universally_Unique_Identifier

Ian.

-- 
Ian Campbell
Current Noise: Jesu - Your Path To Divinity

Build a system that even a fool can use and only a fool will want to use it.