-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathdraft-gont-predictable-numeric-ids-01.txt
1792 lines (1175 loc) · 65.5 KB
/
draft-gont-predictable-numeric-ids-01.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Network Working Group F. Gont
Internet-Draft SI6 Networks / UTN-FRH
Intended status: Best Current Practice I. Arce
Expires: January 5, 2017 Fundacion Sadosky
July 4, 2016
Security and Privacy Implications of Numeric Identifiers Employed in
Network Protocols
draft-gont-predictable-numeric-ids-01
Abstract
This document performs an analysis of the security and privacy
implications of different types of "numeric identifiers" used in IETF
protocols, and tries to categorize them based on their
interoperability requirements and the associated failure severity
when such requirements are not met. It describes a number of
algorithms that have been employed in real implementations to meet
such requirements and analyzes their security and privacy properties.
Additionally, it provides advice on possible algorithms that could be
employed to satisfy the interoperability requirements of each
identifier type, while minimizing the security and privacy
implications, thus providing guidance to protocol designers and
protocol implementers. Finally, it provides recommendations for
future protocol specifications regarding the specification of the
aforementioned numeric identifiers.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 5, 2017.
Gont & Arce Expires January 5, 2017 [Page 1]
Internet-Draft Predictable Numeric IDs July 2016
Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
This document may not be modified, and derivative works of it may not
be created, and it may not be published except as an Internet-Draft.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Threat Model . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Issues with the Specification of Identifiers . . . . . . . . 5
5. Timeline of Vulnerability Disclosures Related to Some Sample
Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.1. IPv4/IPv6 Identification . . . . . . . . . . . . . . . . 6
5.2. TCP Initial Sequence Numbers (ISNs) . . . . . . . . . . . 7
6. Protocol Failure Severity . . . . . . . . . . . . . . . . . . 9
7. Categorizing Identifiers . . . . . . . . . . . . . . . . . . 9
8. Common Algorithms for Identifier Generation . . . . . . . . . 11
8.1. Category #1: Uniqueness (soft failure) . . . . . . . . . 11
8.1.1. Simple Randomization Algorithm . . . . . . . . . . . 11
8.1.2. Another Simple Randomization Algorithm . . . . . . . 12
8.2. Category #2: Uniqueness (hard failure) . . . . . . . . . 13
8.3. Category #3: Uniqueness, constant within context (soft-
failure) . . . . . . . . . . . . . . . . . . . . . . . . 13
8.4. Category #4: Uniqueness, monotonically increasing within
context (hard failure) . . . . . . . . . . . . . . . . . 14
8.4.1. Predictable Linear Identifiers Algorithm . . . . . . 14
8.4.2. Per-context Counter Algorithm . . . . . . . . . . . . 16
8.4.3. Simple Hash-Based Algorithm . . . . . . . . . . . . . 18
8.4.4. Double-Hash Algorithm . . . . . . . . . . . . . . . . 20
8.4.5. Random-Increments Algorithm . . . . . . . . . . . . . 21
9. Common Vulnerabilities Associated with Identifiers . . . . . 23
9.1. Category #1: Uniqueness (soft failure) . . . . . . . . . 23
9.2. Category #2: Uniqueness (hard failure) . . . . . . . . . 23
9.3. Category #3: Uniqueness, constant within context (soft
Gont & Arce Expires January 5, 2017 [Page 2]
Internet-Draft Predictable Numeric IDs July 2016
failure) . . . . . . . . . . . . . . . . . . . . . . . . 23
9.4. Category #4: Uniqueness, monotonically increasing within
context (hard failure) . . . . . . . . . . . . . . . . . 24
10. Security and Privacy Requirements for Identifiers . . . . . . 25
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
12. Security Considerations . . . . . . . . . . . . . . . . . . . 26
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
14.1. Normative References . . . . . . . . . . . . . . . . . . 26
14.2. Informative References . . . . . . . . . . . . . . . . . 27
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31
1. Introduction
Network protocols employ a variety of numeric identifiers for
different protocol entities, ranging from DNS Transaction IDs (TxIDs)
to transport protocol numbers (e.g. TCP ports) or IPv6 Interface
Identifiers (IIDs). These identifiers usually have specific
properties that must be satisfied such that they do not result in
negative interoperability implications (e.g. uniqueness during a
specified period of time), and associated failure severities when
such properties are not met, ranging from soft to hard failures.
For more than 30 years, a large number of implementations of the TCP/
IP protocol suite have been subject to a variety of attacks, with
effects ranging from Denial of Service (DoS) or data injection, to
information leakage that could be exploited for pervasive monitoring
[RFC7528]. The root of these issues has been, in many cases, the
poor selection of identifiers in such protocols, usually as a result
of an insufficient or misleading specification. While it is
generally trivial to identify an algorithm that can satisfy the
interoperability requirements for a given identifier, there exists
practical evidence that doing so without negatively affecting the
security and/or privacy properties of the aforementioned protocols is
prone to error.
For example, implementations have been subject to security and/or
privacy issues resulting from:
o Predictable TCP sequence numbers
o Predictable transport protocol numbers
o Predictable IPv4 or IPv6 Fragment Identifiers
o Predictable IPv6 IIDs
o Predictable DNS TxIDs
Gont & Arce Expires January 5, 2017 [Page 3]
Internet-Draft Predictable Numeric IDs July 2016
Recent history indicates that when new protocols are standardized or
new protocol implementations are produced, the security and privacy
properties of the associated identifiers tend to be overlooked and
inappropriate algorithms to generate identifier values are either
suggested in the specification or selected by implementators. As a
result, we believe that advice in this area is warranted.
This document contains a non-exhaustive survey of identifiers
employed in various IETF protocols, and aims to categorize such
identifiers based on their interoperability requirements, and the
associated failure severity when such requirements are not met.
Subsequently, it analyzes several algorithms that have been employed
in real implementation to meet such requirements and analyzes their
security and privacy properties, and provides advice on possible
algorithms that could be employed to satisfy the interoperability
requirements of each category, while minimizing the associated
security and privacy implications. Finally, it provides
recommendations for future protocol specifications regarding the
specification of the aforementioned numeric identifiers.
2. Terminology
Identifier:
A data object in a protocol specification that can be used to
definetely distinguish a protocol object (a datagram, network
interface, transport protocol endpoint, session, etc) from all
other objects of the same type, in a given context. Identifiers
are usually defined as a series of bits and represented using
integer values. We note that different identifiers may have
additional requirements or properties depending on their specific
use in a protocol. We use the term "identifier" as a generic term
to refer to any data object in a protocol specification that
satisfies the identification property stated above.
Failure Severity:
The consequences of a failure to comply with the interoperability
requirements of a given identifier. Severity considers the worst
potential consequence of a failure, determined by the system
damage and/or time lost to repair the failure. In this document
we define two types of failure severity: "soft" and "hard".
Hard Failure:
A hard failure is a non-recoverable condition in which a protocol
does not operate in the prescribed manner or it operates with
excessive degradation of service. For example, an established TCP
connection that is aborted due to an error condition constitutes,
from the point of view of the transport protocol, a hard failure,
Gont & Arce Expires January 5, 2017 [Page 4]
Internet-Draft Predictable Numeric IDs July 2016
since it enters a state from which normal operation cannot be
recovered.
Soft Failure:
A soft failure is a recoverable condition in which a protocol does
not operate in the prescribed manner but normal operation can be
resumed automatically in a short period of time. For example, a
simple packet-loss event that is subsequently recovered with a
retransmission can be considered a soft failure.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
3. Threat Model
Throughout this document, we assume an attacker does not have
physical or logical device to the device(s) being attacked. We
assume the attacker can simply send any traffic to the target
devices, to e.g. sample identifiers employed by such devices.
4. Issues with the Specification of Identifiers
While assessing protocol specifications regarding the use of
identifiers, we found that most of the issues discussed in this
document arise as a result of one of the following:
o Protocol specifications which under-specify the requirements for
their identifiers
o Protocol specifications that over-specify their identifiers
o Protocol implementations that simply fail to comply with the
specified requirements
A number of protocol implementations (too many of them) simply
overlook the security and privacy implications of identifiers.
Examples of them are the specification of TCP port numbers in
[RFC0793], the specification of TCP sequence numbers in [RFC0793], or
the specification of the DNS TxID in [RFC1035].
On the other hand, there are a number of protocol specifications that
over-specify some of their associated protocol identifiers. For
example, [RFC4291] essentially results in link-layer addresses being
embedded in the IPv6 Interface Identifiers (IIDs) when the
interoperability requirement of uniqueness could be achieved in other
ways that do not result in negative security and privacy implications
[RFC7721]. Similarly, [RFC2460] suggests the use of a global counter
Gont & Arce Expires January 5, 2017 [Page 5]
Internet-Draft Predictable Numeric IDs July 2016
for the generation of Fragment Identification values, when the
interoperability properties of uniqueness per {Src IP, Dst IP} could
be achieved with other algorithms that do not result in negative
security and privacy implications.
Finally, there are protocol implementations that simply fail to
comply with existing protocol specifications. For example, some
popular operating systems (notably Microsoft Windows) still fail to
implement randomization of transport protocol ephemeral ports, as
specified in [RFC6056].
5. Timeline of Vulnerability Disclosures Related to Some Sample
Identifiers
This section contains a non-exhaustive timeline of vulnerability
disclosures related to some sample identifiers and other work that
has led to advances in this area. The goal of this timeline is to
illustrate:
o That vulnerabilities related to how the values for some
identifiers are generated and assigned have affected
implementations for an extremely long period of time.
o That such vulnerabilities, even when addressed for a given
protocol version, were later reintroduced in new versions or new
implementations of the same protocol.
o That standardization efforts that discuss and provide advice in
this area can have a positive effect on protocol specifications
and protocol implementations.
5.1. IPv4/IPv6 Identification
December 1998:
[Sanfilippo1998a] finds that predictable IPv4 Identification
values can be leveraged to count the number of packets sent by a
target node. [Sanfilippo1998b] explains how to leverage the same
vulnerability to implement a port-scanning technique known as
dumb/idle scan. A tool that implements this attack is publicly
released.
November 1999:
[Sanfilippo1999] discusses how to leverage predictable IPv4
Identification to uncover the rules of a number of firewalls.
November 1999:
[Bellovin2002] explains how the IPv4 Identification field can be
exploited to count the number of systems behind a NAT.
Gont & Arce Expires January 5, 2017 [Page 6]
Internet-Draft Predictable Numeric IDs July 2016
December 2003:
[Zalewski2003] explains a technique to perform TCP data injection
attack based on predictable IPv4 identification values which
requires less effort than TCP injection attacks performed with
bare TCP packets.
November 2005:
[Silbersack2005] discusses shortcoming in a number of techniques
to mitigate predictable IPv4 Identification values.
October 2007:
[Klein2007] describes a weakness in the pseudo random number
generator (PRNG) in use for the generation of the IP
Identification by a number of operating systems.
June 2011:
[Gont2011] describes how to perform idle scan attacks in IPv6.
November 2011:
Linux mitigates predictable IPv6 Identification values
[RedHat2011] [SUSE2011] [Ubuntu2011].
December 2011:
[I-D.ietf-6man-predictable-fragment-id-08] describes the security
implications of predictable IPv6 Identification values, and
possible mitigations.
May 2012:
[Gont2012] notes that some major IPv6 implementations still employ
predictable IPv6 Identification values.
June 2015:
[I-D.ietf-6man-predictable-fragment-id-08] notes that some popular
host and router implementations still employ predictable IPv6
Identification values.
5.2. TCP Initial Sequence Numbers (ISNs)
September 1981:
[RFC0793], suggests the use of a global 32-bit ISN generator,
whose lower bit is incremented roughly every 4 microseconds.
However, such an ISN generator makes it trivial to predict the ISN
that a TCP will use for new connections, thus allowing a variety
of attacks against TCP.
February 1985:
Gont & Arce Expires January 5, 2017 [Page 7]
Internet-Draft Predictable Numeric IDs July 2016
[Morris1985] was the first to describe how to exploit predictable
TCP ISNs for forging TCP connections that could then be leveraged
for trust relationship exploitation.
April 1989:
[Bellovin1989] discussed the security implications of predictable
ISNs (along with a range of other protocol-based vulnerabilities).
February 1995:
[Shimomura1995] reported a real-world exploitation of the attack
described in 1985 (ten years before) in [Morris1985].
May 1996:
[RFC1948] was the first IETF effort, authored by Steven Bellovin,
to address predictable TCP ISNs. The same concept specified in
this document for TCP ISNs was later proposed for TCP ephemeral
ports [RFC6056], TCP Timestamps, and eventually even IPv6
Interface Identifiers [RFC7217].
March 2001:
[Zalewski2001] provides a detailed analysis of statistical
weaknesses in some ISN generators, and includes a survey of the
algorithms in use by popular TCP implementations.
May 2001:
Vulnerability advisories [CERT2001] [USCERT2001] are released
regarding statistical weaknesses in some ISN generators, affecting
popular TCP/IP implementations.
March 2002:
[Zalewski2002] updates and complements [Zalewski2001]. It
concludes that "while some vendors [...] reacted promptly and
tested their solutions properly, many still either ignored the
issue and never evaluated their implementations, or implemented a
flawed solution that apparently was not tested using a known
approach". [Zalewski2002].
February 2012:
[RFC6528], after 27 years of Morris' original work [Morris1985],
formally updates [RFC0793] to mitigate predictable TCP ISNs.
August 2014:
[I-D.eddy-rfc793bis-04], the upcoming revision of the core TCP
protocol specification, incorporates the algorithm specified in
[RFC6528] as the recommended algorithm for TCP ISN generation.
Gont & Arce Expires January 5, 2017 [Page 8]
Internet-Draft Predictable Numeric IDs July 2016
6. Protocol Failure Severity
Section 2 defines the concept of "Failure Severity" and two types of
failures that we employ throughout this document: soft and hard.
Our analysis of the severity of a failure is performed from the point
of view of the protocol in question. However, the corresponding
severity on the upper application or protocol may not be the same as
that of the protocol in question. For example, a TCP connection that
is aborted may or may not result in a hard failure of the upper
application: if the upper application can establish a new TCP
connection without any impact on the application, a hard failure at
the TCP protocol may have no severity at the application level. On
the other hand, if a hard failure of a TCP connection results in
excessive degradation of service at the application layer, it will
also result in a hard failure at the application.
7. Categorizing Identifiers
This section includes a non-exhaustive survey of identifiers, and
proposes a number of categories that can accommodate these
identifiers based on their interoperability requirements and their
failure modes (soft or hard)
+------------+--------------------------------------+---------------+
| Identifier | Interoperability Requirements | Failure |
| | | Severity |
+------------+--------------------------------------+---------------+
| IPv6 Frag | Uniqueness (for IP address pair) | Soft/Hard (1) |
| ID | | |
+------------+--------------------------------------+---------------+
| IPv6 IID | Uniqueness (and constant within IPv6 | Soft (3) |
| | prefix) (2) | |
+------------+--------------------------------------+---------------+
| TCP SEQ | Monotonically-increasing | Hard (4) |
+------------+--------------------------------------+---------------+
| TCP eph. | Uniqueness (for connection ID) | Hard |
| port | | |
+------------+--------------------------------------+---------------+
| IPv6 Flow | Uniqueness | None (5) |
| L. | | |
+------------+--------------------------------------+---------------+
| DNS TxID | Uniqueness | None (6) |
+------------+--------------------------------------+---------------+
Table 1: Survey of Identifiers
Notes:
Gont & Arce Expires January 5, 2017 [Page 9]
Internet-Draft Predictable Numeric IDs July 2016
(1)
While a single collision of Fragment ID values would simply lead
to a single packet drop (and hence a "soft" failure), repeated
collisions at high data rates might trash the Fragment ID space,
leading to a hard failure [RFC4963].
(2)
While the interoperability requirements are simply that the
Interface ID results in a unique IPv6 address, for operational
reasons it is typically desirable that the resulting IPv6 address
(and hence the corresponding Interface ID) be constant within each
network [I-D.ietf-6man-default-iids] [RFC7217].
(3)
While IPv6 Interface IDs must result in unique IPv6 addresses,
IPv6 Duplicate Address Detection (DAD) [RFC4862] allows for the
detection of duplicate Interface IDs/addresses, and hence such
Interface ID collisions can be recovered.
(4)
In theory there are no interoperability requirements for TCP
sequence numbers, since the TIME-WAIT state and TCP's "quiet time"
take care of old segments from previous incarnations of the
connection. However, a widespread optimization allows for a new
incarnation of a previous connection to be created if the Initial
Sequence Number (ISN) of the incoming SYN is larger than the last
sequence number seen in that direction for the previous
incarnation of the connection. Thus, monotonically-increasing TCP
sequence numbers allow for such optimization to work as expected
[RFC6528].
(5)
The IPv6 Flow Label is typically employed for load sharing
[RFC7098], along with the Source and Destination IPv6 addresses.
Reuse of a Flow Label value for the same set {Source Address,
Destination Address} would typically cause both flows to be
multiplexed into the same link. However, as long as this does not
occur deterministically, it will not result in any negative
implications.
(6)
DNS TxIDs are employed, together with the Source Address,
Destination Address, Source Port, and Destination Port, to match
DNS requests and responses. However, since an implementation
knows which DNS requests were sent for that set of {Source
Address, Destination Address, Source Port, and Destination Port,
DNS TxID}, a collision of TxID would result, if anything, in a
small performance penalty (the response would be discarded when it
Gont & Arce Expires January 5, 2017 [Page 10]
Internet-Draft Predictable Numeric IDs July 2016
is found that it does not answer the query sent in the
corresponding DNS query).
Based on the survey above, we can categorize identifiers as follows:
+-----+---------------------------------------+---------------------+
| Cat | Category | Sample Proto IDs |
| # | | |
+-----+---------------------------------------+---------------------+
| 1 | Uniqueness (soft failure) | IPv6 Flow L., DNS |
| | | TxIDs |
+-----+---------------------------------------+---------------------+
| 2 | Uniqueness (hard failure) | IPv6 Frag ID, TCP |
| | | ephemeral port |
+-----+---------------------------------------+---------------------+
| 3 | Uniqueness, constant within context | IPv6 IIDs |
| | (soft failure) | |
+-----+---------------------------------------+---------------------+
| 4 | Uniqueness, monotonically increasing | TCP ISN |
| | within context (hard failure) | |
+-----+---------------------------------------+---------------------+
Table 2: Identifier Categories
We note that Category #4 could be considered a generalized case of
category #3, in which a monotonically increasing element is added to
a constant (within context) element, such that the resulting
identifiers are monotonically increasing within a specified context.
That is, the same algorithm could be employed for both #3 and #4,
given appropriate parameters.
8. Common Algorithms for Identifier Generation
The following subsections describe common algorithms found for
Protocol ID generation for each of the categories above.
8.1. Category #1: Uniqueness (soft failure)
8.1.1. Simple Randomization Algorithm
Gont & Arce Expires January 5, 2017 [Page 11]
Internet-Draft Predictable Numeric IDs July 2016
/* Ephemeral port selection function */
id_range = max_id - min_id + 1;
next_id = min_id + (random() % id_range);
count = next_id;
do {
if(check_suitable_id(next_id))
return next_id;
if (next_id == max_id) {
next_id = min_id;
} else {
next_id++;
}
count--;
} while (count > 0);
return ERROR;
Note:
random() is a function that returns a pseudo-random unsigned
integer number of appropriate size. Note that the output needs to
be unpredictable, and typical implementations of POSIX random()
function do not necessarily meet this requirement. See [RFC4086]
for randomness requirements for security.
The function check_suitable_id() can check, when possible, whether
this identifier is e.g. already in use. When already used, this
algorithm selects the next available protocol ID.
All the variables (in this and all the algorithms discussed in
this document) are unsigned integers.
8.1.2. Another Simple Randomization Algorithm
The following pseudo-code illustrates another algorithm for selecting
a random identifier in which, in the event the identifier is found to
be not suitable (e.g., already in use), another identifier is
selected randomly:
Gont & Arce Expires January 5, 2017 [Page 12]
Internet-Draft Predictable Numeric IDs July 2016
id_range = max_id - min_id + 1;
next_id = min_id + (random() % id_range);
count = id_range;
do {
if(check_suitable_id(next_id))
return next_id;
next_id = min_id + (random() % id_range);
count--;
} while (count > 0);
return ERROR;
This algorithm might be unable to select an identifier (i.e., return
"ERROR") even if there are suitable identifiers available, when there
are a large number of identifiers "in use".
8.2. Category #2: Uniqueness (hard failure)
One of the most trivial approaches for achieving uniqueness for an
identifier (with a hard failure mode) is to implement a linear
function. As a result, all of the algorithms described in
Section 8.4 are of use for complying the requirements of this
identifier category.
8.3. Category #3: Uniqueness, constant within context (soft-failure)
The goal of this algorithm is to produce identifiers that are
constant for a given context, but that change when the aforementioned
context changes.
Keeping one value for each possible "context" may in many cases be
considered too onerous in terms of memory requirements. As a
workaround, the following algorithm employs a calculated technique
(as opposed to keeping state in memory) to maintain the constant
identifier for each given context.
In the following algorithm, the function F() provides (statelessly) a
constant identifier for each given context.
Gont & Arce Expires January 5, 2017 [Page 13]
Internet-Draft Predictable Numeric IDs July 2016
/* Protocol ID selection function */
id_range = max_id - min_id + 1;
counter = 0;
do {
offset = F(CONTEXT, counter, secret_key);
next_id = min_id + (offset % id_range);
if(check_suitable_id(next_id))
return next_id;
counter++;
} while (counter <= MAX_RETRIES);
return ERROR;
The function F() provides a "per-CONTEXT" constant identifier for a
given context. 'offset' may take any value within the storage type
range since we are restricting the resulting identifier to be in the
range [min_id, max_id] in a similar way as in the algorithm described
in Section 8.1.1. Collisions can be recovered by incrementing the
'counter' variable and recomputing F().
The function F() should be a cryptographic hash function like SHA-256
[FIPS-SHS]. Note: MD5 [RFC1321] is considered unacceptable for F()
[RFC6151]. CONTEXT is the concatenation of all the elements that
define a given context. For example, if this algorithm is expected
to produce identifiers that are unique per network interface card
(NIC) and SLAAC autoconfiguration prefix, the CONTEXT should be the
concatenation of e.g. the interface index and the SLAAC
autoconfiguration prefix (please see [RFC7217] for an implementation
of this algorithm for the generation of IPv6 IIDs).
The secret should be chosen to be as random as possible (see
[RFC4086] for recommendations on choosing secrets).
8.4. Category #4: Uniqueness, monotonically increasing within context
(hard failure)
8.4.1. Predictable Linear Identifiers Algorithm
One of the most trivial ways to achieve uniqueness with a low
identifier reuse frequency is to produce a linear sequence. This
obviously assumes that each identifier will be used for a similar
period of time.
Gont & Arce Expires January 5, 2017 [Page 14]
Internet-Draft Predictable Numeric IDs July 2016
For example, the following algorithm has been employed in a number of
operating systems for selecting IP fragment IDs, TCP ephemeral ports,
etc.
/* Initialization at system boot time. Could be random */
next_id = min_id;
id_inc= 1;
/* Identifier selection function */
count = max_id - min_id + 1;
do {
if (next_id == max_id) {
next_id = min_id;
}
else {
next_id = next_id + id_inc;
}
if (check_suitable_id(next_id))
return next_id;
count--;
} while (count > 0);
return ERROR;
Note:
check_suitable_id() is a function that checks whether the
resulting identifier is acceptable (e.g., whether its in use,
etc.).
For obvious reasons, this algorithm results in predicable sequences.
If a global counter is used (such as "next_id" in the example above),
a node that learns one protocol identifier can also learn or guess
values employed by past and future protocol instances. On the other
hand, when the value of increments is known (such as "1" in this
case), an attacker can sample two values, and learn the number of
identifiers that were generated in-between.
Where identifier reuse would lead to a hard failure, one typical
approach to generate unique identifiers (while minimizing the
security and privacy implications of predictable identifiers) is to
obfuscate the resulting protocol IDs by either:
o Replace the global counter with multiple counters (initialized to
a random value)
Gont & Arce Expires January 5, 2017 [Page 15]
Internet-Draft Predictable Numeric IDs July 2016
o Randomizing the "increments"
Avoiding global counters essentially means that learning one
identifier for a given context (e.g., one TCP ephemeral port for a
given {src IP, Dst IP, Dst Port}) is of no use for learning or
guessing identifiers for a different context (e.g., TCP ephemeral
ports that involve other peers). However, this may imply keeping one
additional variable/counter per context, which may be prohibitive in
some environments. The choice of id_inc has implications on both the
security and privacy properties of the resulting identifiers, but
also on the corresponding interoperability properties. On one hand,
minimizing the increments (as in "id_inc = 1" in our case) generally
minimizes the identifier reuse frequency, albeit at increased
predictability. On the other hand, if the increments are randomized
predictability of the resulting identifiers is reduced, and the
information leakage produced by global constant increments is
mitigated.
8.4.2. Per-context Counter Algorithm
One possible way to achieve similar (or even lower) identifier reuse
frequency while still avoiding predictable sequences would be to
employ a per-context counter, as opposed to a global counter. Such
an algorithm could be described as follows:
Gont & Arce Expires January 5, 2017 [Page 16]
Internet-Draft Predictable Numeric IDs July 2016
/* Initialization at system boot time. Could be random */
id_inc= 1;
/* Identifier selection function */
count = max_id - min_id + 1;
if(lookup_counter(CONTEXT) == ERROR){
create_counter(CONTEXT);
}
next_id= lookup_counter(CONTEXT);
do {
if (next_id == max_id) {
next_id = min_id;
}
else {
next_id = next_id + id_inc;
}
if (check_suitable_id(next_id)){
store_counter(CONTEXT, next_id);
return next_id;
}
count--;
} while (count > 0);
store_counter(CONTEXT, next_id);
return ERROR;
NOTE:
lookup_counter() returns the current counter for a given context,
or an error condition if such a counter does not exist.
create_counter() creates a counter for a given context, and
initializes such counter to a random value.
store_counter() saves (updates) the current counter for a given
context.
check_suitable_id() is a function that checks whether the
resulting identifier is acceptable (e.g., whether its in use,
etc.).
Essentially, whenever a new identifier is to be selected, the
algorithm checks whether there there is a counter for the
Gont & Arce Expires January 5, 2017 [Page 17]
Internet-Draft Predictable Numeric IDs July 2016
corresponding context. If there is, such counter is incremented to
obtain the new identifier, and the new identifier updates the
corresponding counter. If there is no counter for such context, a
new counter is created an initialized to a random value, and used as
the new identifier.
This algorithm produces a per-context counter, which results in one
linear function for each context. Since the origin of each "line" is
a random value, the resulting values are unknown to an off-path
attacker.
This algorithm has the following drawbacks:
o If, as a result of resource management, the counter for a given
context must be removed, the last identifier value used for that
context will be lost. Thus, if subsequently an identifier needs
to be generated for such context, that counter will need to be
recreated and reinitialized to random value, thus possibly leading
to reuse/collistion of identifiers.
o If the identifiers are predictable by the destination system
(e.g., the destination host represents the context), a vulnerable
host might possibly leak to third parties the identifiers used by
other hosts to send traffic to it (i.e., a vulnerable Host B could
leak to Host C the identifier values that Host A is using to send
packets to Host B). Appendix A of [RFC7739] describes one
possible scenario for such leakage in detail.
8.4.3. Simple Hash-Based Algorithm
The goal of this algorithm is to produce monotonically-increasing
sequences, with a randomized initial value, for each given context.
For example, if the identifiers being generated must be unique for
each {src IP, dst IP} set, then each possible combination of {src IP,
dst IP} should have a corresponding "next_id" value.
Keeping one value for each possible "context" may in many cases be
considered too onerous in terms of memory requirements. As a
workaround, the following algorithm employs a calculated technique
(as opposed to keeping state in memory) to maintain the random offset
for each possible context.
In the following algorithm, the function F() provides (statelessly) a
random offset for each given context.