Bob,
This is something like the birthday paradox. What's the probability of a collision of n values chosen from m bits of possibilities? It's
P = 1 - ((2^m - 1)/2^m)^C(n,2)
And if n is 10000 and m is 16 bits the probability of collision is 0.9995, essentially 1. There will definitely be duplicate IDs if you give 10000 devices IDs out of a space of only 2^16. If you bump it up to 32 bits the probability drops
to 0.0115. Still not good. For MAC randomization, consider 50,000 associated stations (like a Taylor Swift concert) and 46 bits of randomization, the probability that 2 STAs will randomly* choose the same MAC is 0.00001176 which is decent.
regards,
Dan.
* of course that assumes the STA has a good random number generator and uses it properly, so caveat emptor.
--
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
I am pretty busy this morning. I will look closely at it this afternoon.
Meanwhile the formula I use is:
=1-EXP(-(B39^2)/(2*C39))
Where C contains the possible population and B the deployed population.
On 8/2/23 23:10, HARRY BIMS wrote:
Bob,
Can you check my attached spreadsheet and show me where I’ve made a mistake? It appears that for the 5th randomly generated ID from a population of 10,000, the collision probability is 0.1%, not 0.01%. And the
45th randomly generated ID has a collision probability of 9.44%, not 1%.
Also, for the population size of 2^32, the 0.01% collision probability occurs after the 928th random selection, and the 1% collision probability occurs after the 9292th random selection.
Also, for the 1 out of 100 deployed addresses scenario, it appears that the 0.01% collision probability with a deployed address occurs after the 4396th random selection. This is due to the fact that duplicate random
IDs that are outside of the deployed addresses are not counted as a collision. Even after the 16,384th random selection, the collision probability for the 1 out of 100 deployed addresses is less than 0.04%.
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
Using the probability formula I provided earlier:
In a potential population of 10000, The 5th randomly generated ID has a .01% risk of a collision. The 45th has a 1% risk. In part, big deal, the AP just tries again.
Now if I use a 4-byte ID, 2^32, at ~1000 is the .01% probability of collision and ~9000 is 1%. Pretty good, I might think as would an AP have more than 1000 STAs? Well you all know better than me.
Thus a 4-byte minimum seems OK based on probability of collisions. It becomes a different matter if the attacker needs to get 1 out of 100 deployed. I would have to run the math for that.
And given this is encrypted with SIV? Just use some polynomial increasing value and encrypt. What is the problem, as you say.
hmmm, I did say I would withdraw, but the math is fun. And I can use a little fun right now.
Bob
On 8/2/23 18:08, Luther Smith wrote:
I am sure that I have this wrong, but I am going to just put it out there and let others correct me.
My understanding is that the device Id (lower d) is created by the AP/network. If that is the case, then there should not be any collisions unless the AP/network is not keeping track – (bad AP/network).
That the Device ID (big D) I thought was sent encrypted OTA. If so, then it will be changing in similar fashion as RCM. If not, then whenever the device is sending the Device ID it can be “tracked”. (the reason
RCM was started).
As to “spoofing” a device, likened to what could have happened before RCM, what is the true impact? The major use case is where the MAC address was used to ID the device an allow access (either in association or
to the network ie partental controls). This goes back to the comment about the Device ID OTA – does it get changed and only the AP/Network knows what it is at that time.
I fall back to Dan’s statement about the TGbh, to have a method of identifying a device that does not make use of the MAC address. So, if the AP/Network assigns a device an ID, the AP/Network can identify the device.
If the AP/Network changes the device Id, then the AP/Network knows the new one. The only issue I see is if, and only if, a spoofing device get access and the AP/Network updates the device’s ID (which is sent back to the spoofing device), then when the real
device returns the AP/Network will not know that device as the device Id the real device is using has been deprecated with a new device Id and given to the spoofing device. This is where I go back to – is the Device ID in an encrypted exchange?
Thank you for listening/reading my thoughts and beliefs,
Director Wireless Access Technologies/ Distinguished Technologist
303-661-3305 voice
303-661-9199 fax
There were two issues on the call
1a. Having an inordinately short device ID could lead to identifier collisions
The network owns the device ID space. It knows how many device IDs it will be handing out. And it knows what information it needs to put in device IDs in order to do whatever it intends on doing. No one is going
to use a 1 octet device ID if there will be multiple 1000s of clients and if the network wants to use a UUID or something to track devices it's not going to select a single octet Device ID. This seems like an issue in search of a problem.
1b. A short device ID could be “guessed” or brute forced by an attacker. I am with Dan on the idea that we should NOT be providing feedback to the client whether the identifier was accepted or not. The secondary
question here is that does knowledge of the plaintext and encrypted forms of the ID reveal anything about the encryption key?
I encourage you to look into "known plaintext attacks" and whether modern ciphers (including AES-SIV) are susceptible to them and why or why not.
2. As Kurt mentioned on the call, a large Device ID has an impact on devices with small memory footprints. They may not be able to keep track of large IDs across several ESS. They don’t have a way to communicate
what the upper limit on the device ID that they can support and would potentially have to drop identifiers when a large one comes in.
Constrained devices are a concern but I don't think a Device ID is the straw that broke that camel's back. We're talking about an IE, as we cram more and more stuff into beacons and probe responses that these constrained
devices are supposed to be able to just parse? Problem? Color me skeptical. STAs don't need to "support" the Device ID anyway, they just need to echo it back in a different frame. To them it's an opaque blob.
Do we think that we have handled both concerns?
I don't think either concern is anything we need to worry about actually.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
The synthetic initialization vector (SIV) is also the integrity check value. It's a 2-pass cipher mode. To generate you do a keyed CMAC on the plaintext and use the resulting
digest as the IV to CTR mode. To process, it's the inverse, decrypt the ciphertext with the IV and see if the result produces the IV when CMAC'd. Since garbage will always successfully decrypt with CTR mode (to more garbage but how do you know?), the "plaintext"
needs to be thrown away, not exported to the caller, if the IV does not check out. See RFC 5297 for beautiful ASCII art diagrams ☺
So yes, the overhead is 17 bytes at a minimum and a tad more to make sure that the same Device ID (upper case!) isn't given out twice, plus any kind of traffic analysis
obfuscation a user wants to do.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
But, doesn’t AES-SIV also add the length of the SIV to the resulting total? (Sorry for neophyte questions… I would really like to make sure we are all accounting for the annex correctly in our discussion about
the Device ID field size, though.)
As for, “then why are we telling the attacker his attack is successful or not?” Well, the usual: the problem of conflicting/competing requirements, I guess is the best answer…
I think we are running into the terminology problem, again. When I say “Device ID” (upper case ‘D’), I mean what is carried in that field of the IE/KDE and sent OTA.
Yep, I agree, the device ID can be short, and Annex AD will still protect it. But, the resulting Device ID (sent OTA) will be relatively large (that is, more than a handful of octets), right? And, hence if we
propose something like 6 octets as the minimum length of the Device ID, then anything that uses the Annex will be compliant. But, I’m stating this as a double-check that I’m right…?
The Annex adds 17 octets of overhead (16 octets of integrity check and 1 octet to indicate padding) and has an optional padding and a user-specified tweak so it's difficult to say how big it would be. A single octet
device ID (lower case!) with no padding and an 8 octet tweak would result in a 26 octet Device ID (upper case!). Of course if collision of blobs (i.e. giving the same Device ID (upper case!) to STAs for a static, unchanging device ID (lower case!)) over the
course of all of a STA's associations over the AP's uptime is not so much of a concern the tweak can be smaller.
But if the Annex is not used then, yes, there is a possibility of an attacker running through all umpteen possibilities of device IDs (lower case!) until one "works". So again, I will ask, if that is a concern then
why are we telling the attacker his attack is successful or not? "Nope, try again… nope, try again… yes, it worked!" The cognitive dissonance is a bit much for me.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Just a quick response on the first point. If the length of the communicated Device ID (which is what we’re discussing, the length in the actual IE/KDE as it is carried OTA) could be very short (for example, 1 octet),
then it would be much easier to brute force try all 256 possibilities until you get a “Recognized” response from the network. Even 6 octets would be a big improvement.
If the user of the 11bh amendment cared then it would not use a "very short" identifier. While I am amenable to the argument that the customer doesn't really know what he's doing I would also caution us from thinking
that we do. If we have "security considerations" regarding the use of our standard then we should explicitly mention them and if we have consensus that short device IDs are problematic then we should have a nice informative note on that subject. Personally
I don't think they are but that's just me.
And, again, if we are concerned about this brute force attack then why are we telling the attacker whether or not his guess was good or not?
I don’t think the Annex AD method can/would produce such a short Device ID to be sent OTA, anyway, so I think that is beyond this discussion. That is, we are only talking about when the annex is not being used
(for whatever implementation choice reasons).
The Annex can and would protect such a short device ID because of the security properties of AES-SIV. The size of the plaintext does not affect the non-forgeability property. It is computationally infeasible for
an adversary to construct a blob that would pass the integrity verification part of AES-SIV whether the plaintext is 1 octet or 250 octets. That's the whole point.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
A couple of counter arguments (I think, if I’m understanding the points made):
- I am concerned that with no minimum length requirement for
a Device ID, we will get comments that there is a “security hole” in that an attacker could easily brute force try a lot/every possible short Device ID string until one works. We’ve had discussions in the past that we don’t want to introduce a mechanism that
allows trivial spoofing of a “known” device, by either a rogue STA or AP. As long as we have agreement that we don’t care about this problem, and/or it is out of our scope to worry about perhaps (in which case maybe we at least want a NOTE?), then I can see
arguments for allowing (or at least not disallowing) very short Device IDs.
Keeping in mind why 11bh got formed. This device ID is replacing a plaintext MAC address that was used by networks for identification purposes. I fail to see how a short device ID would open some "security hole"
that didn't exist with a spoofable identifier that was passed in the clear! We didn't get formed because the outcry was "the identifier we were using could be spoofed and we demand more security", it was "the identifier we were using is useless now and we
just need something, anything".
I wonder what "until one works" means anyway. Don't we have some status bit saying, "didn't recognize that but here's a new one for you"? So if fear of this "security hole" was real then we should not be expressing
a status bit to tell the attacker that it "works" or not—"you can end your brute force attack now mr attacker, I recognize that value."
Also, maybe this is another reason to use the (optional for now) technique in the Annex. It is computationally infeasible for an adversary to forge a blob even if it knew the size and make-up of the device ID. In
addition. It adds padding to the device ID to make traffic analysis more difficult and adds a tweak to the computation to ensure that blobs will not be repeated. If we are concerned about the security of using device IDs then maybe we should promote the informative
annex into normative text. (And I will take the outcry to not do that as evidence that this security concern is not serious).
I think a minimum length of the device ID (128 bits?) is more the illusion of security. AES-SIV has provable security and we can point to that instead of handwave about how hard it would be to brute force device
IDs and what it means to say "until one works".
- Ben’s takeaway (just below) seems to have been that the
Device ID comes from a “higher layer protocol”. That has not been my assumption. I could imagine that this is possible, but I can also imagine that it is generate (in an implementation-dependent manner) within the 802 layer. Do we need to get agreement/add
clarification on this (again, maybe just a NOTE)?
I guess it depends on the purpose. But regardless of whether it comes from a higher layer protocol or not, the construction of the device ID is outside the scope of 11bh and therefore the resulting length of the
constructed device ID is as well. Let's not constrain the use of this amendment with unnecessary limits on its use.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
Thanks Dan, that explanation is very helpful.
An alternative to rejecting the comment would be "revised" and clarify the field definition consistent with Dan's explanation. As is it says that it contains something that is undefined
(refers only to an informative annex) which a voter might suggest makes the spec not technically complete.
The Device ID field is an octet string and is defined by the higher layer protocol. See also Annex AD.1.
(borrowing language from 802.11-2020 for similar situations where the content is defined at the network layer).
FWIW it would seem from the discussion that clarification will help. It helped me!
I missed the TGbh call this morning but I understand there was a discussion about min/max device ID lengths. It is my opinion that the contents of a device ID and its
subsequent length are entirely outside the scope of the standard. The only requirement is it has to fit in an IE and if you do the Annex encryption stuff you will need to take into account the overhead it imposes (17 octets plus tweak plus padding if used)
and make sure your device IDs will still fit after being encrypted. There is no need to specify a min. STAs don't care what their device ID is (remember, these use cases are entirely to help the network side of the conversation) and the network owns the device
ID space so it can do anything it wants.
I would support rejection of the comments that ask for min/max limits on device IDs.
"the object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." – Marcus Aurelius
I just wanted to point out a couple examples from the baseline (REVme, that is), for fields which are not always present, and/or have variable length or some restrictions on their length (when they are present).
Supported Operating Classes element:
Note the “(optional)” inside the field’s box, and the “variable” below the box. Also, note that the text then describes when the field is present or not, and minimal information about what it carries when it is
present:
Time Advertisement element:
Again “(optional)” inside the box, and this time a fixed choice of length below the box (0 or a fixed length). And, again, minimal description in the text about when the field is present, and what it means when
it is present:
Of interest here, is the use of “4 x m” for the length of the last field. So, there are examples of a simple “formula” type of length, even with an optional field – which can presumably be 0 if m is 0.
This is one with the possibility of “not present” (0 length), or a specific range of lengths allowed when it is present. And, here the text describes when it is present, and points elsewhere (although still in
clause 9 ?! 😊) for its structure and definition when it is present:
Personally, I think that last example might be the most relevant one for us to mirror, if we decide the Device ID length can be a range (when present), or ours could be like Time Advertisement element if we decide
the Device ID is fixed length (when present).
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
--
Robert Moskowitz
Owner
HTT Consulting
C: 248-219-2059
F: 248-968-2824
E: rgm@xxxxxxxxxxxxxxxxxxxx
There's no limit to what can be accomplished if it doesn't matter who gets the credit
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
--
Robert Moskowitz
Owner
HTT Consulting
C: 248-219-2059
F: 248-968-2824
E: rgm@xxxxxxxxxxxxxxxxxxxx
There's no limit to what can be accomplished if it doesn't matter who gets the credit
To unsubscribe from the STDS-802-11-TGBH list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
To unsubscribe from the STDS-802-11-TGBH list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGBH&A=1
|