[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: RE: [security-services] Possible 1.1 (and 1.0) errata
I think this result is almost right, but question an aspect of the analysis. The "almost right" part first: the "less than" components should be "less than or equal to", assuming that the intent is to allow 128-bit and 160-bit values respectively rather than requiring something slightly larger; the probability that one 160-bit random value matches the next should be exactly 2^-160, not less. The first trial fixes the value against which the second independent sample will be compared, and there are 2^160 possible values. WRT the analysis, it's easier (given enough operations and their accumulated history) to find a result collision between some pair of hash inputs than to find a match against a specific fixed output. This corresponds to the result that 2^80 operations can be expected to yield *some* collision for a 160-bit hash function, but doesn't mean that the probability that two initial trials, taken in isolation, will match with a probability as "high" as 2^-80. --jl -----Original Message----- From: Jahan Moreh [mailto:jmoreh@sigaba.com] Sent: Tuesday, August 05, 2003 1:41 PM To: Scott Cantor; SAML Subject: RE: [security-services] Possible 1.1 (and 1.0) errata Scott - This is the text in 1.1 core that references uniqueness (I am using draft 10, lines 360-362): The mechanism by which a SAML system entity ensures that the identifier is unique is left to the implementation. In the case that a pseudorandom technique is employed, the probability of two randomly chosen identifiers being identical MUST be less than 2^-128 and SHOULD be less than 2^-160. This requirement MAY be met by encoding a randomly chosen value between 128 and 160 bits in length. I actually think this text is correct! The key words here are: "randomly chosen". I believe the case you identify below is the probability of collision when one value is already chosen (i.e., a birthday attack). In that case, indeed the probability is approximately 2^-n/2, where "n" is the number of bits. So, if this is not the text you are referencing, or, if I am mistaken in my analysis, please let me know so that I can update the errata accordingly. Thanks, Jahan ---------------- Jahan Moreh Chief Security Architect 310.286.3070 > -----Original Message----- > From: Scott Cantor [mailto:cantor.2@osu.edu] > Sent: Thursday, July 31, 2003 10:21 AM > To: SAML > Subject: [security-services] Possible 1.1 (and 1.0) errata > > > It's been pointed out during review of the latest Liberty > documents that the > part in SAML about identifier uniqueness is overstated based on > the intent. > If the point is to use a SHA1 hash, then the actual collision > probability in > the spec language should be <= 2^-80 instead of < 2^-160 > > Liberty had the same language and it was copied from SAML, so I > figured I'd > mention it. > > -- Scott > > > You may leave a Technical Committee at any time by visiting > http://www.oasis-open.org/apps/org/workgroup/security-services/mem bers/leave_workgroup.php You may leave a Technical Committee at any time by visiting http://www.oasis-open.org/apps/org/workgroup/security-services/members/leave _workgroup.php
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]