1 /*
2  * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License").
5  * You may not use this file except in compliance with the License.
6  * A copy of the License is located at
7  *
8  *  http://aws.amazon.com/apache2.0
9  *
10  * or in the "license" file accompanying this file. This file is distributed
11  * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
12  * express or implied. See the License for the specific language governing
13  * permissions and limitations under the License.
14  */
15 
16 #include "s2n_test.h"
17 
18 #include <inttypes.h>
19 #include <string.h>
20 #include <stdio.h>
21 #include <math.h>
22 
23 #include <s2n.h>
24 
25 #include "testlib/s2n_testlib.h"
26 
27 #include "tls/s2n_cipher_suites.h"
28 #include "stuffer/s2n_stuffer.h"
29 #include "crypto/s2n_cipher.h"
30 #include "utils/s2n_random.h"
31 #include "utils/s2n_safety.h"
32 #include "crypto/s2n_hmac.h"
33 #include "tls/s2n_record.h"
34 #include "tls/s2n_prf.h"
35 
36 /*
37  * disable everything in this file if the compiler target isn't Intel x86 or x86_64. There's inline asm
38  * that can't really be replaced with an analog for other architectures.
39  */
40 #if defined(__x86_64__) || defined(__i386__)
41 /* qsort() u64s numerically */
u64cmp(const void * left,const void * right)42 static int u64cmp (const void * left, const void * right)
43 {
44    if (*(const uint64_t *)left > *(const uint64_t *)right) return 1;
45    if (*(const uint64_t *)left < *(const uint64_t *)right) return -1;
46    return 0;
47 }
48 
49 /* Generate summary statistics from a list of u64s */
summarize(uint64_t * list,int n,uint64_t * count,uint64_t * avg,uint64_t * median,uint64_t * stddev,uint64_t * variance)50 static void summarize(uint64_t *list, int n, uint64_t *count, uint64_t *avg, uint64_t *median, uint64_t *stddev, uint64_t *variance)
51 {
52     qsort(list, n, sizeof(uint64_t), u64cmp);
53 
54     uint64_t p25 = list[ n / 4 ];
55     uint64_t p50 = list[ n / 2 ];
56     uint64_t p75 = list[ n - (n / 4)];
57     uint64_t iqr = p75 - p25;
58 
59     /* Use the standard interquartile range rule for outlier detection */
60     int64_t low = p25 - (iqr * 1.5);
61     if (iqr > p25) {
62         low = 0;
63     }
64 
65     *avg = low;
66 
67     int64_t hi = p75 + (iqr * 1.5);
68     /* Ignore overflow as we have plenty of room at the top */
69 
70     *count = 0;
71     uint64_t sum = 0;
72     uint64_t sum_squares = 0;
73     uint64_t min = 0xFFFFFFFF;
74     uint64_t max = 0;
75 
76     for (int i = 0; i < n; i++) {
77         int64_t value = list[ i ];
78 
79         if (value < low || value > hi) {
80             continue;
81         }
82 
83         (*count)++;
84 
85         sum += value;
86         sum_squares += value * value;
87 
88         if (value < min) {
89             min = value;
90         }
91         if (value > max) {
92             max = value;
93         }
94     }
95 
96     *variance = sum_squares - (sum * sum);
97     *median = p50;
98 
99     if (*count == 0) {
100         *avg = 0;
101     }
102     else {
103         *avg = sum / *count;
104     }
105 
106     if (*count <= 1) {
107         *stddev = 0;
108     }
109     else {
110         *stddev = sqrt((*count * *variance) / (*count * (*count - 1)));
111     }
112 }
113 
rdtsc()114 inline static uint64_t rdtsc(){
115     unsigned int bot, top;
116     __asm__ __volatile__ ("rdtsc" : "=a" (bot), "=d" (top));
117     return ((uint64_t) top << 32) | bot;
118 }
119 #endif /* defined(__x86_64__) || defined(__i386__) */
120 
main(int argc,char ** argv)121 int main(int argc, char **argv)
122 {
123     BEGIN_TEST();
124     EXPECT_SUCCESS(s2n_disable_tls13());
125 /*
126  * disable everything in this test if the compiler target isn't Intel x86 or x86_64. There's inline asm
127  * that can't really be replaced with an analog for other architectures.
128  */
129 #if defined(__x86_64__) || defined(__i386__)
130     struct s2n_connection *conn;
131     uint8_t mac_key[] = "sample mac key";
132     uint8_t fragment[S2N_SMALL_FRAGMENT_LENGTH];
133     uint8_t random_data[S2N_SMALL_FRAGMENT_LENGTH];
134     struct s2n_hmac_state check_mac, record_mac;
135     struct s2n_blob r = {.data = random_data, .size = sizeof(random_data)};
136 
137 
138     /* Valgrind affects execution timing, making this test unreliable */
139     if (getenv("S2N_VALGRIND") != NULL) {
140         END_TEST();
141     }
142 
143     EXPECT_SUCCESS(s2n_hmac_new(&check_mac));
144     EXPECT_SUCCESS(s2n_hmac_new(&record_mac));
145 
146     EXPECT_NOT_NULL(conn = s2n_connection_new(S2N_SERVER));
147     EXPECT_OK(s2n_get_public_random_data(&r));
148 
149     /* Emulate TLS1.2 */
150     conn->actual_protocol_version = S2N_TLS12;
151 
152     /* Try every 16 bytes to simulate block alignments */
153     for (int i = 288; i < S2N_SMALL_FRAGMENT_LENGTH; i += 16) {
154 
155         EXPECT_SUCCESS(s2n_hmac_init(&record_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
156 
157         EXPECT_MEMCPY_SUCCESS(fragment, random_data, i - 20 - 1);
158         EXPECT_SUCCESS(s2n_hmac_update(&record_mac, fragment, i - 20 - 1));
159         EXPECT_SUCCESS(s2n_hmac_digest(&record_mac, fragment + (i - 20 - 1), 20));
160 
161         /* Start out with zero byte padding */
162         fragment[i - 1] = 0;
163 
164         struct s2n_blob decrypted = {0};
165         s2n_blob_init(&decrypted, fragment, i);
166 
167         uint64_t timings[10001];
168         for (int t = 0; t < 10001; t++) {
169             EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
170 
171             uint64_t before = rdtsc();
172             EXPECT_SUCCESS(s2n_verify_cbc(conn, &check_mac, &decrypted));
173             uint64_t after = rdtsc();
174 
175             timings[ t ] = (after - before);
176         }
177 
178         uint64_t good_median, good_avg, good_stddev, good_variance, good_count;
179         summarize(timings, 10001, &good_count, &good_avg, &good_median, &good_stddev, &good_variance);
180 
181         for (int t = 0; t < 10001; t++) {
182             EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
183 
184             uint64_t before = rdtsc();
185             EXPECT_SUCCESS(s2n_verify_cbc(conn, &check_mac, &decrypted));
186             uint64_t after = rdtsc();
187 
188             timings[ t ] = (after - before);
189         }
190 
191         summarize(timings, 10001, &good_count, &good_avg, &good_median, &good_stddev, &good_variance);
192 
193         /* Set up a record so that the MAC fails */
194         EXPECT_SUCCESS(s2n_hmac_init(&record_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
195 
196         /* Set up 254 bytes of padding */
197         for (int j = 1; j < 256; j++) {
198             fragment[i - j] = 254;
199         }
200 
201         EXPECT_MEMCPY_SUCCESS(fragment, random_data, i - 20 - 255);
202         EXPECT_SUCCESS(s2n_hmac_update(&record_mac, fragment, i - 20 - 255));
203         EXPECT_SUCCESS(s2n_hmac_digest(&record_mac, fragment + (i - 20 - 255), 20));
204 
205         /* Verify that the record would pass: the MAC and padding are ok */
206         EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
207         EXPECT_SUCCESS(s2n_verify_cbc(conn, &check_mac, &decrypted));
208 
209         /* Corrupt a HMAC byte */
210         fragment[i - 256]++;
211 
212         for (int t = 0; t < 10001; t++) {
213             EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
214 
215             uint64_t before = rdtsc();
216             EXPECT_FAILURE(s2n_verify_cbc(conn, &check_mac, &decrypted));
217             uint64_t after = rdtsc();
218 
219             timings[ t ] = (after - before);
220         }
221 
222         uint64_t mac_median, mac_avg, mac_stddev, mac_variance, mac_count;
223         summarize(timings, 10001, &mac_count, &mac_avg, &mac_median, &mac_stddev, &mac_variance);
224 
225         /* Use a simple 3 sigma test for the median distance from the good */
226         int64_t lo = good_median - (3 * good_stddev);
227         int64_t hi = good_median + (3 * good_stddev);
228 
229         if ((int64_t) mac_median < lo || (int64_t) mac_median > hi) {
230             printf("\n\nRecord size: %d\nGood Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n"
231                    "Bad Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n\n",
232                     i, good_median, good_avg, good_stddev, mac_median, mac_avg, mac_stddev);
233             FAIL();
234         }
235 
236         /* Set up the record so that the HMAC passes, and the padding fails */
237         EXPECT_SUCCESS(s2n_hmac_init(&record_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
238 
239         /* Set up 15 bytes of padding */
240         for (int j = 1; j < 17; j++) {
241             fragment[i - j] = 15;
242         }
243 
244         EXPECT_MEMCPY_SUCCESS(fragment, random_data, i - 20 - 16);
245         EXPECT_SUCCESS(s2n_hmac_update(&record_mac, fragment, i - 20 - 16));
246         EXPECT_SUCCESS(s2n_hmac_digest(&record_mac, fragment + (i - 20 - 16), 20));
247 
248         /* Verify that the record would pass: the MAC and padding are ok */
249         EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
250         EXPECT_SUCCESS(s2n_verify_cbc(conn, &check_mac, &decrypted));
251 
252         /* Now corrupt a padding byte */
253         fragment[i - 10]++;
254 
255         for (int t = 0; t < 10001; t++) {
256             EXPECT_SUCCESS(s2n_hmac_init(&check_mac, S2N_HMAC_SHA1, mac_key, sizeof(mac_key)));
257 
258             uint64_t before = rdtsc();
259             EXPECT_FAILURE(s2n_verify_cbc(conn, &check_mac, &decrypted));
260             uint64_t after = rdtsc();
261 
262             timings[ t ] = (after - before);
263         }
264 
265         uint64_t pad_median, pad_avg, pad_stddev, pad_variance, pad_count;
266         summarize(timings, 10001, &pad_count, &pad_avg, &pad_median, &pad_stddev, &pad_variance);
267 
268         /* Use a simple 3 sigma test for the median from the good */
269         lo = good_median - (3 * good_stddev);
270         hi = good_median + (3 * good_stddev);
271 
272         if ((int64_t) pad_median < lo || (int64_t) pad_median > hi) {
273             printf("\n\nRecord size: %d\nGood Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n"
274                    "Bad Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n\n",
275                     i, good_median, good_avg, good_stddev, pad_median, pad_avg, pad_stddev);
276             FAIL();
277         }
278 
279         /* Use a more sensitive 0.5 sigma test for the MAC error from the padding error. This is the
280          * the difference that attackers can exploit.
281          */
282         lo = mac_median - (mac_stddev / 2);
283         hi = mac_median + (mac_stddev / 2);
284 
285         if ((int64_t) pad_median < lo || (int64_t) pad_median > hi) {
286             printf("\n\nRecord size: %d\nMAC Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n"
287                    "PAD Median: %" PRIu64 " (Avg: %" PRIu64 " Stddev: %" PRIu64 ")\n\n",
288                     i, mac_median, mac_avg, mac_stddev, pad_median, pad_avg, pad_stddev);
289             FAIL();
290         }
291     }
292 
293     EXPECT_SUCCESS(s2n_hmac_free(&check_mac));
294     EXPECT_SUCCESS(s2n_hmac_free(&record_mac));
295     EXPECT_SUCCESS(s2n_connection_free(conn));
296 
297 #endif /* defined(__x86_64__) || defined(__i386__) */
298     END_TEST();
299 }
300