idmap_rid/idmap_hash collisions?

[Nick-237]

Is it possible for the uid/gid numbers that are generated by the
idmap_rid and idmap_hash to collide if there are a large number of
users or groups?  I cannot seem to find any documentation on the
limitations of these plugins.  Before using I want to make absolutely
sure that there won't be any collisions.

In doing some research about Likewise Open, I see it's hashing routine
can have this problem:

"If your Active Directory relative identifiers, or RIDs, are a number
greater than 524,287, the Likewise Open algorithm that generates UIDs
and GIDs can result in UID-GID collisions among users and groups. In
such cases, it is recommended that you use Likewise Enterprise or that
you use the Likewise UID-GID management tool."

http://www.likewise.com/resources/documentation_library/manuals/open/likewise-open-guide.html#AboutLikewiseAgent

I was somehow thinking that Likewise is based on Samba, although I
don't remember where I heard that so it could be total BS.

Does anyone know about the limitations of these idmap backends?
--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Volker Lendecke]

On Tue, Nov 10, 2009 at 06:34:13PM -0800, Nick wrote:
> Is it possible for the uid/gid numbers that are generated by the
> idmap_rid and idmap_hash to collide if there are a large number of
> users or groups?  I cannot seem to find any documentation on the
> limitations of these plugins.  Before using I want to make absolutely
> sure that there won't be any collisions.

With idmap_rid you have to take care of splicing up the rid
space yourself. If you don't do that according to your
domains, you get overlap. idmap_hash indeed will generate
collisions if you have more than 2^19 (524287) object in a
domain.

> I was somehow thinking that Likewise is based on Samba, although I
> don't remember where I heard that so it could be total BS.

Likewise used to be based on Samba. It is not anymore.

Please contact Likewise themselves for questions about their
product.

Volker


--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Gerald Carter-3]

Hey Nick,

Nick wrote:
> Is it possible for the uid/gid numbers that are generated by the
> idmap_rid and idmap_hash to collide if there are a large number of
> users or groups?  I cannot seem to find any documentation on the
> limitations of these plugins.  Before using I want to make absolutely
> sure that there won't be any collisions.

There is a small chance of collision based on the domain sid.
In testing the mean average was about40 trusted domains but I've
see it much lower on rare occasions.  Also, if the highest RID
in your domain is > (as Volker points out) 2^19, the plugin will
suffer from integer overflow.

There's a slide or two outlining the algorithm in this slide deck
from LInuxWorld SF '08

http://archives.likewiseopen.org/~gcarter/presentations/likewise_open_first_class_citizen_lwsf08.pdf

> In doing some research about Likewise Open, I see it's hashing routine
> can have this problem:
>
> "If your Active Directory relative identifiers, or RIDs, are a number
> greater than 524,287, the Likewise Open algorithm that generates UIDs
> and GIDs can result in UID-GID collisions among users and groups. In
> such cases, it is recommended that you use Likewise Enterprise or that
> you use the Likewise UID-GID management tool."
>
> http://www.likewise.com/resources/documentation_library/manuals/open/likewise-open-guide.html#AboutLikewiseAgent
>
> I was somehow thinking that Likewise is based on Samba, although I
> don't remember where I heard that so it could be total BS.

The Likewise Identity 3.x and 4.x was based on winbindd.  That's when
I wrote the original idmap_hash and pushed it upstream.  The Likewise 5.x
code based moved to a new single process threaded authentication service
named lsassd, but still supports the hashing mechanism for unprovisioned
AD domains.

The "enterprise" version and the uid/gid management tool you
reference above just allow you to manually administer uid and gid
assignments in AD (that will be picked up by lsassd).

Does that help clarify?





cheers, jerry



--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Gerald Carter-3]

Nick,

Gerald Carter wrote:

> Hey Nick,
>
> Nick wrote:
>> Is it possible for the uid/gid numbers that are generated by the
>> idmap_rid and idmap_hash to collide if there are a large number of
>> users or groups?  I cannot seem to find any documentation on the
>> limitations of these plugins.  Before using I want to make absolutely
>> sure that there won't be any collisions.
>
> There is a small chance of collision based on the domain sid.
> In testing the mean average was about40 trusted domains but I've
> see it much lower on rare occasions.  Also, if the highest RID
> in your domain is > (as Volker points out) 2^19, the plugin will
> suffer from integer overflow.

Forgot to mention that's it pretty simple to test for domain SID
hashing collisions.  Just lookup "Administrator" in all domains
Each should have a unique uid.  For example:

$ for d in AD DEV ATLANTIS; do \
      getent passwd $d\\administrator | awk -F: '{print $3}';\
   done
181928436
557842932
1658323444

Hope this helps.




cheers, jerry



--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Robert LeBlanc]

On Wed, Nov 11, 2009 at 7:52 AM, Gerald Carter <jerry@...> wrote:

> Hey Nick,
>
> Nick wrote:
> > Is it possible for the uid/gid numbers that are generated by the
> > idmap_rid and idmap_hash to collide if there are a large number of
> > users or groups?  I cannot seem to find any documentation on the
> > limitations of these plugins.  Before using I want to make absolutely
> > sure that there won't be any collisions.
>
> There is a small chance of collision based on the domain sid.
> In testing the mean average was about40 trusted domains but I've
> see it much lower on rare occasions.  Also, if the highest RID
> in your domain is > (as Volker points out) 2^19, the plugin will
> suffer from integer overflow.
>
> There's a slide or two outlining the algorithm in this slide deck
> from LInuxWorld SF '08
>
> <http://archives.likewiseopen.org/%7Egcarter/presentations/likewise_open_first_class_citizen_lwsf08.pdf>

How does this compare with idmap hash? I can't seem to find the doc that I
found sometime ago regarding it's details. My understanding is that it uses
31 bit uid/gid that is generated from a hash of the domain on certain bits
and a hash of the SID on certain bits. I don't recall how many bit were
allocated to each. Does it suffer from the same collision problem as rid?
Our AD will have a couple of hundred thousand objects in the not too near
future.

Thanks,

Robert LeBlanc
Life Sciences & Undergraduate Education Computer Support
Brigham Young University
--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Volker Lendecke]

On Wed, Nov 11, 2009 at 09:30:03AM -0600, Robert LeBlanc wrote:
> How does this compare with idmap hash? I can't seem to find the doc that I
> found sometime ago regarding it's details. My understanding is that it uses
> 31 bit uid/gid that is generated from a hash of the domain on certain bits
> and a hash of the SID on certain bits. I don't recall how many bit were
> allocated to each. Does it suffer from the same collision problem as rid?
> Our AD will have a couple of hundred thousand objects in the not too near
> future.

If I read the code right, it's 12 bits for the domain, this
is a hash of the domain sid prefix. 19 bits from the RID.

Volker


--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Gerald Carter-3]

Robert LeBlanc wrote:

>> There's a slide or two outlining the algorithm in this slide deck
>> from LInuxWorld SF '08
>>
>> <http://archives.likewiseopen.org/%7Egcarter/presentations/likewise_open_first_class_citizen_lwsf08.pdf>
>
> How does this compare with idmap hash?

It's the same thing algorithm.  I wrote the original Samba & Likewise
SID hashing code.

> Does it suffer from the same collision problem as rid?

idmap_rid doesn't have a collision problem that I'm aware of
as long as you set it up properly.  Did I misunderstand something?

> Our AD will have a couple of hundred thousand objects in
> the not too near future.

Depending on account turnover and number of trusted domains,
I think you should be fine with idmap_hash.  But if you only
have a single domain, then idmap_rid is equivalent I think.





cheers, jerry



--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Robert LeBlanc]

On Wed, Nov 11, 2009 at 9:52 AM, Gerald Carter <jerry@...> wrote:

> Robert LeBlanc wrote:
>
>  > Does it suffer from the same collision problem as rid?
>
> idmap_rid doesn't have a collision problem that I'm aware of
> as long as you set it up properly.  Did I misunderstand something?
>
> > Our AD will have a couple of hundred thousand objects in
> > the not too near future.
>
> Depending on account turnover and number of trusted domains,
> I think you should be fine with idmap_hash.  But if you only
> have a single domain, then idmap_rid is equivalent I think.
>
>

I think I may have not woken up completely this morning. I thought the
original question was regarding idamp_rid and basically interger rollover.
After rereading the first post, it sounds like they want to use RID and Hash
at the same time. I don't know why one want to do that, but ok. I much
prefer hash because I don't have to specify a range and hope it is large
enough. I also don't have to worry about all my machines having the same
lower end starting number so that they are the same on all machines. We have
some trusts, but they are only intended to be temporay as we transitition to
a central AD.

So if I understand right, hash does not hash the SID, it does the same as
rid and takes the last section directly from the SID and uses that withou
modification (rid adds that number to the lower range number).

Thanks,

Robert LeBlanc
Life Sciences & Undergraduate Education Computer Support
Brigham Young University
--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Gerald Carter-3]

Robert LeBlanc wrote:

> So if I understand right, hash does not hash the SID, it does the
> same as rid and takes the last section directly from the SID
> and uses that withou modification (rid adds that number to the
> lower range number).

idmap_hash *does* the SID.




cheers, jerry




--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba

[Robert LeBlanc]

On Wed, Nov 11, 2009 at 10:18 AM, Gerald Carter <jerry@...> wrote:

> Robert LeBlanc wrote:
>
> > So if I understand right, hash does not hash the SID, it does the
> > same as rid and takes the last section directly from the SID
> > and uses that withou modification (rid adds that number to the
> > lower range number).
>
> idmap_hash *does* the SID.
>
>

That is what I initially thought.

Thanks,

Robert LeBlanc
Life Sciences & Undergraduate Education Computer Support
Brigham Young University
--
To unsubscribe from this list go to the following URL and read the
instructions:  https://lists.samba.org/mailman/options/samba