1/* $OpenBSD: deattack.c,v 1.30 2006/09/16 19:53:37 djm Exp $ */
2/*
3 * Cryptographic attack detector for ssh - source code
4 *
5 * Copyright (c) 1998 CORE SDI S.A., Buenos Aires, Argentina.
6 *
7 * All rights reserved. Redistribution and use in source and binary
8 * forms, with or without modification, are permitted provided that
9 * this copyright notice is retained.
10 *
11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
12 * WARRANTIES ARE DISCLAIMED. IN NO EVENT SHALL CORE SDI S.A. BE
13 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR
14 * CONSEQUENTIAL DAMAGES RESULTING FROM THE USE OR MISUSE OF THIS
15 * SOFTWARE.
16 *
17 * Ariel Futoransky <futo@core-sdi.com>
18 * <http://www.core-sdi.com>
19 */
20
21#include "includes.h"
22
23#include <sys/types.h>
24
25#include <string.h>
26#include <stdio.h>
27#include <stdarg.h>
28
29#include "xmalloc.h"
30#include "deattack.h"
31#include "log.h"
32#include "crc32.h"
33#include "misc.h"
34
35/*
36 * CRC attack detection has a worst-case behaviour that is O(N^3) over
37 * the number of identical blocks in a packet. This behaviour can be
38 * exploited to create a limited denial of service attack.
39 *
40 * However, because we are dealing with encrypted data, identical
41 * blocks should only occur every 2^35 maximally-sized packets or so.
42 * Consequently, we can detect this DoS by looking for identical blocks
43 * in a packet.
44 *
45 * The parameter below determines how many identical blocks we will
46 * accept in a single packet, trading off between attack detection and
47 * likelihood of terminating a legitimate connection. A value of 32
48 * corresponds to an average of 2^40 messages before an attack is
49 * misdetected
50 */
51#define MAX_IDENTICAL	32
52
53/* SSH Constants */
54#define SSH_MAXBLOCKS	(32 * 1024)
55#define SSH_BLOCKSIZE	(8)
56
57/* Hashing constants */
58#define HASH_MINSIZE	(8 * 1024)
59#define HASH_ENTRYSIZE	(2)
60#define HASH_FACTOR(x)	((x)*3/2)
61#define HASH_UNUSEDCHAR	(0xff)
62#define HASH_UNUSED	(0xffff)
63#define HASH_IV		(0xfffe)
64
65#define HASH_MINBLOCKS	(7*SSH_BLOCKSIZE)
66
67
68/* Hash function (Input keys are cipher results) */
69#define HASH(x)		get_u32(x)
70
71#define CMP(a, b)	(memcmp(a, b, SSH_BLOCKSIZE))
72
73static void
74crc_update(u_int32_t *a, u_int32_t b)
75{
76	b ^= *a;
77	*a = ssh_crc32((u_char *)&b, sizeof(b));
78}
79
80/* detect if a block is used in a particular pattern */
81static int
82check_crc(u_char *S, u_char *buf, u_int32_t len)
83{
84	u_int32_t crc;
85	u_char *c;
86
87	crc = 0;
88	for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) {
89		if (!CMP(S, c)) {
90			crc_update(&crc, 1);
91			crc_update(&crc, 0);
92		} else {
93			crc_update(&crc, 0);
94			crc_update(&crc, 0);
95		}
96	}
97	return (crc == 0);
98}
99
100
101/* Detect a crc32 compensation attack on a packet */
102int
103detect_attack(u_char *buf, u_int32_t len)
104{
105	static u_int16_t *h = (u_int16_t *) NULL;
106	static u_int32_t n = HASH_MINSIZE / HASH_ENTRYSIZE;
107	u_int32_t i, j;
108	u_int32_t l, same;
109	u_char *c;
110	u_char *d;
111
112	if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||
113	    len % SSH_BLOCKSIZE != 0) {
114		fatal("detect_attack: bad length %d", len);
115	}
116	for (l = n; l < HASH_FACTOR(len / SSH_BLOCKSIZE); l = l << 2)
117		;
118
119	if (h == NULL) {
120		debug("Installing crc compensation attack detector.");
121		h = (u_int16_t *) xcalloc(l, HASH_ENTRYSIZE);
122		n = l;
123	} else {
124		if (l > n) {
125			h = (u_int16_t *)xrealloc(h, l, HASH_ENTRYSIZE);
126			n = l;
127		}
128	}
129
130	if (len <= HASH_MINBLOCKS) {
131		for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) {
132			for (d = buf; d < c; d += SSH_BLOCKSIZE) {
133				if (!CMP(c, d)) {
134					if ((check_crc(c, buf, len)))
135						return (DEATTACK_DETECTED);
136					else
137						break;
138				}
139			}
140		}
141		return (DEATTACK_OK);
142	}
143	memset(h, HASH_UNUSEDCHAR, n * HASH_ENTRYSIZE);
144
145	for (c = buf, same = j = 0; c < (buf + len); c += SSH_BLOCKSIZE, j++) {
146		for (i = HASH(c) & (n - 1); h[i] != HASH_UNUSED;
147		    i = (i + 1) & (n - 1)) {
148			if (!CMP(c, buf + h[i] * SSH_BLOCKSIZE)) {
149				if (++same > MAX_IDENTICAL)
150					return (DEATTACK_DOS_DETECTED);
151				if (check_crc(c, buf, len))
152					return (DEATTACK_DETECTED);
153				else
154					break;
155			}
156		}
157		h[i] = j;
158	}
159	return (DEATTACK_OK);
160}
161