[6951] in cryptography@c2.net mail archive
key agility and IPsec
daemon@ATHENA.MIT.EDU (Steve Bellovin)
Thu Apr 27 11:34:24 2000
From: Steve Bellovin <smb@research.att.com>
To: cryptography@c2.net
Cc: ipsec@lists.tislabs.com
Reply-To: cryptography@c2.net
Mime-Version: 1.0
Content-Type: multipart/mixed ;
boundary="==_Exmh_1097001440"
Date: Wed, 26 Apr 2000 19:50:10 -0400
Message-Id: <20000426235010.4A04A35DC2@smb.research.att.com>
This is a multipart MIME message.
--==_Exmh_1097001440
Content-Type: text/plain
(Note to ipsec@ readers -- this is a follow-up to a discussion on the
cryptography list a week or so ago. To spare folks who subscribe to both, I've
directed followups to the cryptography list ONLY. Subscription to it is via
majordomo@c2.net.)
----
Following my exchange of notes with Ron Rivest on key agility for
IPsec, I decided to gather some real data. I used a monitoring
station on the plaintext side of one of our IPsec gateways to gather
7,000,000 packets in three sessions, two afternoon and one evening.
Note carefully that this experiment is preliminary and small-scale.
That particular gateway is a Linux box running FreeSWAN; it serves about
180 homes running Linux IPsec appliances (for details on the setup,
see http://www.quintillion.com/moat/lisa-moat.ps or .pdf). Most
of our endpoints have high-quality (i.e., short path) connections
to the gateway. Packet headers were captured via tcpdump; lacking
access to the ciphertext (and hence the SPI), I intuited the SA
from the remote IP address and knowledge of our address assignment
plan. Thus, since most people are assigned /29s, I assumed that
I could mask off the low-order three bits of IP addresses in that
range and get the security association. I split the received
traffic depending on whether the gateway was encrypting or decrypting
the packet.
Users of this gateway typically have either a non-Windows machine
or more than one machine on a home LAN. (People with a single
Windows machine generally use a software client, and are homed on
a different gateway.) I picked up converstations to about 145 home
networks, and about 300 different machines. I made no attempt to
account for rekeying; that should be infrequent enough that it
wouldn't affect key agility requirements.
The network behavior was about as expected. There were more packets
to the home than from it (4,189,877 vs. 2,810,123) and many more
bytes (1,705,033,395 vs. 297,915,963), for an average of 406
bytes/packet downstream and 106 bytes/packet upstream. While I
haven't yet analyzed packet size distributions for upstream vs.
downstream, the different average sizes certainly suggest that a
larger percentage of the upstream packets are made up of tinygrams.
To assess the key agility requirements, I simulated an LRU cache
of infiite depth. The number of cache hits at a given depth should
then indicate how large a cache would be needed to avoid a new key
schedule calculation. (Note: I think that this approach is
reasonable -- does anyone disagree?) I could have, but didn't,
discard cache entries when too much time had elapsed since the last
use, thus indicating a likely rekeying operation.
To achieve an 80% hit rate, a cache size of 5 entries is needed
for the encrypt (to the home) side, while a 8-element cache would
be needed for decryption. To achieve a 95% hit rate, 11 and 17
element caches would be needed.
The cache size differences agree with intuition. The gateway
decrypt side requires a bigger cache than the encrypt side to
achieve the same hit rate; this is probably a function of the
mechanisms I suggested a few days ago: smaller packets which allow
for more interleaving, delayed ACK strategies, and some lack of
"packet trains". IPsec decryption is in some sense more demanding
than encryption; since MAC-checking can be done in parallel with
decryption, multiple packets can be decrypted back-to-back, without
needing to reuse the data path for serial encrypt/MAC generation.
On the other hand, the upstream data rate was considerably less,
allowing more time for key-switching.
I did some preliminary analysis of packet train lengths. Downstream
packets show some evidence of packet clustering, though not as much
as I had expected -- 60% of the trains downstream were of length
1, compared with 70% of upstream trains.
I'm not sure what further analyses I should perform on this data.
I do caution people that these are small-scale measurements from
one site; I would be very interested to see data from other sites
with IPsec gateways, especially big gateways. As I noted, I saw
less than 150 SAs; it is not clear to me what would happen with
1500 or 15,000 SAs. For actual assessment of key agility requirements, a
larger study is needed.
I've attached the output summary files. The first column is the
LRU depth; the second is the number of hits at that depth, and the
third is the cumulative packet percentage for that depth. (The
first line is the number of different SAs, and while it does figure
into the cumulative percentages, its effect is obviously minimal.)
--==_Exmh_1097001440
Content-Type: text/plain ; name="encrypt-all"
Content-Description: encrypt-all
Content-Disposition: attachment; filename="encrypt-all"
0 147 0.00
0 1791239 42.76
1 712719 59.77
2 470323 70.99
3 298255 78.11
4 203250 82.96
5 149886 86.54
6 116415 89.32
7 92641 91.53
8 73355 93.28
9 58140 94.67
10 44887 95.74
11 33712 96.54
12 24349 97.12
13 17899 97.55
14 12586 97.85
15 9314 98.07
16 7020 98.24
17 5638 98.37
18 4471 98.48
19 3560 98.57
20 3011 98.64
21 2641 98.70
22 2317 98.76
23 2037 98.81
24 1768 98.85
25 1492 98.88
26 1441 98.92
27 1416 98.95
28 1269 98.98
29 1207 99.01
30 1119 99.04
31 1046 99.06
32 1059 99.09
33 962 99.11
34 970 99.13
35 945 99.16
36 934 99.18
37 910 99.20
38 897 99.22
39 839 99.24
40 785 99.26
41 853 99.28
42 776 99.30
43 782 99.32
44 774 99.34
45 720 99.35
46 713 99.37
47 753 99.39
48 726 99.41
49 709 99.42
50 695 99.44
51 763 99.46
52 708 99.47
53 676 99.49
54 683 99.51
55 641 99.52
56 685 99.54
57 698 99.55
58 627 99.57
59 650 99.59
60 670 99.60
61 554 99.61
62 617 99.63
63 549 99.64
64 591 99.66
65 509 99.67
66 554 99.68
67 514 99.69
68 498 99.71
69 476 99.72
70 438 99.73
71 486 99.74
72 463 99.75
73 460 99.76
74 446 99.77
75 432 99.78
76 471 99.79
77 384 99.80
78 369 99.81
79 355 99.82
80 320 99.83
81 276 99.83
82 270 99.84
83 289 99.85
84 231 99.85
85 250 99.86
86 271 99.87
87 250 99.87
88 250 99.88
89 252 99.88
90 240 99.89
91 255 99.90
92 250 99.90
93 229 99.91
94 240 99.91
95 168 99.92
96 174 99.92
97 172 99.92
98 155 99.93
99 159 99.93
100 137 99.94
101 150 99.94
102 152 99.94
103 162 99.95
104 172 99.95
105 178 99.95
106 162 99.96
107 160 99.96
108 153 99.97
109 146 99.97
110 133 99.97
111 117 99.98
112 116 99.98
113 125 99.98
114 106 99.98
115 112 99.99
116 82 99.99
117 73 99.99
118 74 99.99
119 49 99.99
120 47 99.99
121 40 100.00
122 37 100.00
123 33 100.00
124 38 100.00
125 27 100.00
126 20 100.00
127 7 100.00
128 14 100.00
129 6 100.00
130 2 100.00
131 2 100.00
132 1 100.00
133 1 100.00
134 1 100.00
135 0 100.00
136 0 100.00
137 1 100.00
138 0 100.00
139 0 100.00
140 0 100.00
141 0 100.00
142 0 100.00
143 0 100.00
144 1 100.00
--==_Exmh_1097001440
Content-Type: text/plain ; name="decrypt-all"
Content-Description: decrypt-all
Content-Disposition: attachment; filename="decrypt-all"
0 142 0.01
0 942192 33.53
1 367564 46.61
2 269794 56.21
3 217387 63.95
4 175852 70.21
5 145346 75.38
6 120891 79.68
7 100418 83.26
8 81884 86.17
9 64991 88.48
10 50992 90.30
11 40071 91.72
12 30991 92.83
13 23835 93.67
14 18649 94.34
15 14680 94.86
16 11926 95.28
17 10169 95.65
18 8753 95.96
19 8172 96.25
20 7317 96.51
21 6738 96.75
22 6129 96.97
23 5637 97.17
24 4988 97.34
25 4558 97.51
26 4208 97.66
27 3865 97.79
28 3574 97.92
29 3250 98.04
30 2767 98.14
31 2575 98.23
32 2372 98.31
33 2279 98.39
34 2100 98.47
35 1943 98.54
36 1750 98.60
37 1657 98.66
38 1477 98.71
39 1381 98.76
40 1274 98.80
41 1196 98.85
42 1116 98.89
43 1106 98.93
44 1100 98.97
45 980 99.00
46 904 99.03
47 890 99.06
48 825 99.09
49 803 99.12
50 765 99.15
51 743 99.18
52 729 99.20
53 680 99.23
54 681 99.25
55 705 99.28
56 617 99.30
57 623 99.32
58 637 99.34
59 602 99.36
60 651 99.39
61 580 99.41
62 660 99.43
63 598 99.45
64 564 99.47
65 554 99.49
66 556 99.51
67 524 99.53
68 525 99.55
69 522 99.57
70 498 99.59
71 530 99.60
72 521 99.62
73 468 99.64
74 482 99.66
75 480 99.67
76 442 99.69
77 444 99.71
78 398 99.72
79 393 99.73
80 369 99.75
81 356 99.76
82 297 99.77
83 301 99.78
84 266 99.79
85 264 99.80
86 272 99.81
87 272 99.82
88 222 99.83
89 262 99.84
90 266 99.85
91 221 99.85
92 254 99.86
93 213 99.87
94 211 99.88
95 208 99.88
96 173 99.89
97 162 99.90
98 160 99.90
99 166 99.91
100 169 99.91
101 147 99.92
102 141 99.92
103 140 99.93
104 161 99.94
105 190 99.94
106 158 99.95
107 141 99.95
108 134 99.96
109 129 99.96
110 128 99.97
111 126 99.97
112 127 99.98
113 101 99.98
114 113 99.98
115 80 99.99
116 65 99.99
117 62 99.99
118 44 99.99
119 52 99.99
120 30 100.00
121 35 100.00
122 30 100.00
123 27 100.00
124 16 100.00
125 11 100.00
126 11 100.00
127 5 100.00
128 2 100.00
129 0 100.00
130 0 100.00
131 1 100.00
132 1 100.00
133 0 100.00
134 0 100.00
135 0 100.00
136 0 100.00
137 0 100.00
138 0 100.00
139 1 100.00
--==_Exmh_1097001440
