Re: UID and GID generation
>
> For all such situations a workaround exists. Still I've been wondering
> for years why appearently nobody else considers this a problem. So I
> patched adduser to determine the user (also: group) ID from a static
> "acount name"<->"ID" mapping. It's in the BTS somewhere eight years
> ago, and I use an updated version still today. Migration of existing
> installations was painful but worth it, YMMV.
Good that I'm not the only one who is not satisfied with the current
implementation. I didn't know that for system services the same algorithm is
used. I thought that the IDs for system services are fixed. Static ID mapping
is a nice idea which would be helpful for system services. Sad that the patch
didn't find it's way into the official release. Nevertheless your idea does not
solve the problem of different user IDs.
I fear that my idea will also be ignored, because someone can always find a
reason not to change a proven algorithm.
>
> Given Murphy and birthday paradoxon, this will bite you much sooner
> than you'd expect.
Yes, collisions must be exptected. Thus the algorithm has to deal with it.
To get an idea about the chance of collisions I've used a file of 281249 common
user names I've found on the net and checked the number of collisions with
different algorithms. The valid value range is from 1000 to 2^32-1, because I
would not use the hash algorithm for system services. Here are the results.
Collisions for 281249 usernames:
15 xxh32
7 md5 (Only first 4 bytes of hash value used)
73980 adler32
7 crc32
9 fnv1_32
9 fnv1a_32
14 murmur1_32
14 murmur1_aligned_32
8 murmur2_32
8 murmur2a_32
8 murmur2_aligned_32
8 murmur2_neutral_32
8 murmur3_32
9 spooky_32
72 super_fast_hash
5 gencrc
It seems that gencrc is the best, but it has to be considered that the used
list is not meant the be complete in any way. The conclusion IMHO is that it
is good enough for a family and small communities where you only have a few
users.
Here is the code for gencrc:
gencrctab = [
0x46d1e192, 0x66edf9aa, 0x927fc9e5, 0xa53baacc, 0x29b47658, 0x5a411a01,
0x0e66d5bd, 0x0dd5b1db, 0xcb38340e, 0x04d4ebb6, 0x98bc4f54, 0x36f20f2c,
0x4a3047ed, 0x1ec1e0eb, 0x568c0c1f, 0x6a731432, 0x81367fc6, 0xe3e25237,
0xe7f64884, 0x0fa59f64, 0x4f3109de, 0xf02d61f5, 0x5daec03b, 0x7f740e83,
0x056ff2d8, 0x2026cc0a, 0x7ac2112d, 0x82c55605, 0xb0911ef2, 0xa7b88e4c,
0x89dca282, 0x4b254d27, 0x7694a6d3, 0xd229eadd, 0x8e8f3738, 0x5bee7a55,
0x012eb6ab, 0x08dd28c8, 0xb5abc274, 0xbc7931f0, 0xf2396ed5, 0xe4e43d97,
0x943f4b7f, 0x85d0293d, 0xaed83a88, 0xc8f932fc, 0xc5496f20, 0xe9228173,
0x9b465b7d, 0xfda26680, 0x1ddeab35, 0x0c4f25cb, 0x86e32faf, 0xe59fa13a,
0xe192e2c4, 0xf147da1a, 0x67620a8d, 0x5c9a24c5, 0xfe6afde2, 0xacad0250,
0xd359730b, 0xf35203b3, 0x96a4b44d, 0xfbcacea6, 0x41a165ec, 0xd71e53ac,
0x835f39bf, 0x6b6bde7e, 0xd07085ba, 0x79064e07, 0xee5b20c3, 0x3b90bd65,
0x5827aef4, 0x4d12d31c, 0x9143496e, 0x6c485976, 0xd9552733, 0x220f6895,
0xe69def19, 0xeb89cd70, 0xc9bb9644, 0x93ec7e0d, 0x2ace3842, 0x2b6158da,
0x039e9178, 0xbb5367d7, 0x55682285, 0x4315d891, 0x19fd8906, 0x7d8d4448,
0xb4168a03, 0x40b56a53, 0xaa3e69e0, 0xa25182fe, 0xad34d16c, 0x720c4171,
0x9dc3b961, 0x321db563, 0x8b801b9e, 0xf5971893, 0x14cc1251, 0x8f4ae962,
0xf65aff1e, 0x13bd9dee, 0x5e7c78c7, 0xddb61731, 0x73832c15, 0xefebdd5b,
0x1f959aca, 0xe801fb22, 0xa89826ce, 0x30b7165d, 0x458a4077, 0x24fec52a,
0x849b065f, 0x3c6930cd, 0xa199a81d, 0xdb768f30, 0x2e45c64a, 0xff2f0d94,
0x4ea97917, 0x6f572acf, 0x653a195c, 0x17a88c5a, 0x27e11fb5, 0x3f09c4c1,
0x2f87e71b, 0xea1493e4, 0xd4b3a55e, 0xbe6090be, 0xaf6cd9d9, 0xda58ca00,
0x612b7034, 0x31711dad, 0x6d7db041, 0x8ca786b7, 0x09e8bf7a, 0xc3c4d7ea,
0xa3cd77a8, 0x7700f608, 0xdf3de559, 0x71c9353f, 0x9fd236fb, 0x1675d43e,
0x390d9e9a, 0x21ba4c6b, 0xbd1371e8, 0x90338440, 0xd5f163d2, 0xb140fef9,
0x52f50b57, 0x3710cf67, 0x4c11a79c, 0xc6d6624e, 0x3dc7afa9, 0x34a69969,
0x70544a26, 0xf7d9ec98, 0x7c027496, 0x1bfb3ba3, 0xb3b1dc8f, 0x9a241039,
0xf993f5a4, 0x15786b99, 0x26e704f7, 0x51503c04, 0x028bb3b8, 0xede5600c,
0x9cb22b29, 0xb6ff339b, 0x7e771c43, 0xc71c05f1, 0x604ca924, 0x695eed60,
0x688ed0bc, 0x3e0b232f, 0xf8a39c11, 0xbae6e67c, 0xb8cf75e1, 0x970321a7,
0x5328922b, 0xdef3df2e, 0x8d0443b0, 0x2885e3ae, 0x6435eed1, 0xcc375e81,
0xa98495f6, 0xe0bff114, 0xb2da3e4f, 0xc01b5adf, 0x507e0721, 0x6267a36a,
0x181a6df8, 0x7baff0c0, 0xfa6d6c13, 0x427250b2, 0xe2f742d6, 0xcd5cc723,
0x2d218be7, 0xb91fbbb1, 0x9eb946d0, 0x1c180810, 0xfc81d602, 0x0b9c3f52,
0xc2ea456f, 0x1165b2c9, 0xabf4ad75, 0x0a56fc8c, 0x12e0f818, 0xcadbcba1,
0x2586be56, 0x952c9b46, 0x07c6a43c, 0x78967df3, 0x477b2e49, 0x2c5d7b6d,
0x8a637272, 0x59acbcb4, 0x74a0e447, 0xc1f8800f, 0x35c015dc, 0x230794c2,
0x4405f328, 0xec2adba5, 0xd832b845, 0x6e4ed287, 0x48e9f7a2, 0xa44be89f,
0x38cbb725, 0xbf6ef4e6, 0xdc0e83fa, 0x54238d12, 0xf4f0c1e3, 0xa60857fd,
0xc43c64b9, 0x00c851ef, 0x33d75f36, 0x5fd39866, 0xd1efa08a, 0xa0640089,
0x877a978b, 0x99175d86, 0x57dfacbb, 0xceb02de9, 0xcf4d5c09, 0x3a8813d4,
0xb7448816, 0x63fa5568, 0x06be014b, 0xd642fa7b, 0x10aa7c90, 0x8082c88e,
0x1afcba79, 0x7519549d, 0x490a87ff, 0x8820c3a0 ]
def gencrc(s):
h = 0
for c in s:
h = (h >> 8) ^ gencrctab[(h & 0xff) ^ ord(c)];
return h
uid = gencrc(username)
while 0 <= uid < 1000:
username += "X"
uid = gencrc(username)
>
> I wouldn't use the b word here. The implementation is simple but
> introduces problems once you have more than one machine.
You are right. Declaring a proven algorithm as a bug is too exaggerated, but
from the view of a user with no knowledge about UIDs and GIDs and how the
mapping works the behavior as I've described in my first post seems like a bug.
I'm wondering how Windows behaves in such situations. Does Windows save
usernames for access rights? Does anybody know?
Regards,
Martin
Reply to: