1295367Sdes/* $OpenBSD: deattack.c,v 1.32 2015/01/20 23:14:00 deraadt Exp $ */ 257429Smarkm/* 357429Smarkm * Cryptographic attack detector for ssh - source code 457429Smarkm * 557429Smarkm * Copyright (c) 1998 CORE SDI S.A., Buenos Aires, Argentina. 657429Smarkm * 757429Smarkm * All rights reserved. Redistribution and use in source and binary 857429Smarkm * forms, with or without modification, are permitted provided that 957429Smarkm * this copyright notice is retained. 1057429Smarkm * 1157429Smarkm * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 1257429Smarkm * WARRANTIES ARE DISCLAIMED. IN NO EVENT SHALL CORE SDI S.A. BE 1357429Smarkm * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR 1457429Smarkm * CONSEQUENTIAL DAMAGES RESULTING FROM THE USE OR MISUSE OF THIS 1557429Smarkm * SOFTWARE. 1657429Smarkm * 1757429Smarkm * Ariel Futoransky <futo@core-sdi.com> 1857429Smarkm * <http://www.core-sdi.com> 1957429Smarkm */ 2057429Smarkm 2157429Smarkm#include "includes.h" 2292555Sdes 23162852Sdes#include <string.h> 24162852Sdes#include <stdio.h> 25295367Sdes#include <stdlib.h> 26162852Sdes 2757429Smarkm#include "deattack.h" 2857429Smarkm#include "crc32.h" 29295367Sdes#include "sshbuf.h" 30162852Sdes#include "misc.h" 3157429Smarkm 32162852Sdes/* 33162852Sdes * CRC attack detection has a worst-case behaviour that is O(N^3) over 34162852Sdes * the number of identical blocks in a packet. This behaviour can be 35162852Sdes * exploited to create a limited denial of service attack. 36162852Sdes * 37162852Sdes * However, because we are dealing with encrypted data, identical 38162852Sdes * blocks should only occur every 2^35 maximally-sized packets or so. 39162852Sdes * Consequently, we can detect this DoS by looking for identical blocks 40162852Sdes * in a packet. 41162852Sdes * 42162852Sdes * The parameter below determines how many identical blocks we will 43162852Sdes * accept in a single packet, trading off between attack detection and 44162852Sdes * likelihood of terminating a legitimate connection. A value of 32 45162852Sdes * corresponds to an average of 2^40 messages before an attack is 46162852Sdes * misdetected 47162852Sdes */ 48162852Sdes#define MAX_IDENTICAL 32 49162852Sdes 5057429Smarkm/* SSH Constants */ 5157429Smarkm#define SSH_MAXBLOCKS (32 * 1024) 5257429Smarkm#define SSH_BLOCKSIZE (8) 5357429Smarkm 5457429Smarkm/* Hashing constants */ 5557429Smarkm#define HASH_MINSIZE (8 * 1024) 5657429Smarkm#define HASH_ENTRYSIZE (2) 5757429Smarkm#define HASH_FACTOR(x) ((x)*3/2) 5857429Smarkm#define HASH_UNUSEDCHAR (0xff) 5957429Smarkm#define HASH_UNUSED (0xffff) 6092555Sdes#define HASH_IV (0xfffe) 6157429Smarkm 6257429Smarkm#define HASH_MINBLOCKS (7*SSH_BLOCKSIZE) 6357429Smarkm 6457429Smarkm 6557429Smarkm/* Hash function (Input keys are cipher results) */ 66295367Sdes#define HASH(x) PEEK_U32(x) 6757429Smarkm 6876259Sgreen#define CMP(a, b) (memcmp(a, b, SSH_BLOCKSIZE)) 6957429Smarkm 7092555Sdesstatic void 7157429Smarkmcrc_update(u_int32_t *a, u_int32_t b) 7257429Smarkm{ 7357429Smarkm b ^= *a; 74162852Sdes *a = ssh_crc32((u_char *)&b, sizeof(b)); 7557429Smarkm} 7657429Smarkm 7757429Smarkm/* detect if a block is used in a particular pattern */ 7892555Sdesstatic int 79295367Sdescheck_crc(const u_char *S, const u_char *buf, u_int32_t len) 8057429Smarkm{ 8157429Smarkm u_int32_t crc; 82295367Sdes const u_char *c; 8357429Smarkm 8457429Smarkm crc = 0; 8557429Smarkm for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) { 8657429Smarkm if (!CMP(S, c)) { 8757429Smarkm crc_update(&crc, 1); 8857429Smarkm crc_update(&crc, 0); 8957429Smarkm } else { 9057429Smarkm crc_update(&crc, 0); 9157429Smarkm crc_update(&crc, 0); 9257429Smarkm } 9357429Smarkm } 94295367Sdes return crc == 0; 9557429Smarkm} 9657429Smarkm 97295367Sdesvoid 98295367Sdesdeattack_init(struct deattack_ctx *dctx) 99295367Sdes{ 100295367Sdes bzero(dctx, sizeof(*dctx)); 101295367Sdes dctx->n = HASH_MINSIZE / HASH_ENTRYSIZE; 102295367Sdes} 10357429Smarkm 10457429Smarkm/* Detect a crc32 compensation attack on a packet */ 10557429Smarkmint 106295367Sdesdetect_attack(struct deattack_ctx *dctx, const u_char *buf, u_int32_t len) 10757429Smarkm{ 108295367Sdes u_int32_t i, j, l, same; 109295367Sdes u_int16_t *tmp; 110295367Sdes const u_char *c, *d; 11157429Smarkm 11257429Smarkm if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) || 113295367Sdes len % SSH_BLOCKSIZE != 0) 114295367Sdes return DEATTACK_ERROR; 115295367Sdes for (l = dctx->n; l < HASH_FACTOR(len / SSH_BLOCKSIZE); l = l << 2) 11657429Smarkm ; 11757429Smarkm 118295367Sdes if (dctx->h == NULL) { 119295367Sdes if ((dctx->h = calloc(l, HASH_ENTRYSIZE)) == NULL) 120295367Sdes return DEATTACK_ERROR; 121295367Sdes dctx->n = l; 12257429Smarkm } else { 123295367Sdes if (l > dctx->n) { 124295367Sdes if ((tmp = reallocarray(dctx->h, l, HASH_ENTRYSIZE)) 125295367Sdes == NULL) { 126295367Sdes free(dctx->h); 127295367Sdes dctx->h = NULL; 128295367Sdes return DEATTACK_ERROR; 129295367Sdes } 130295367Sdes dctx->h = tmp; 131295367Sdes dctx->n = l; 13257429Smarkm } 13357429Smarkm } 13457429Smarkm 13557429Smarkm if (len <= HASH_MINBLOCKS) { 13657429Smarkm for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) { 13757429Smarkm for (d = buf; d < c; d += SSH_BLOCKSIZE) { 13857429Smarkm if (!CMP(c, d)) { 139162852Sdes if ((check_crc(c, buf, len))) 140295367Sdes return DEATTACK_DETECTED; 14157429Smarkm else 14257429Smarkm break; 14357429Smarkm } 14457429Smarkm } 14557429Smarkm } 146295367Sdes return DEATTACK_OK; 14757429Smarkm } 148295367Sdes memset(dctx->h, HASH_UNUSEDCHAR, dctx->n * HASH_ENTRYSIZE); 14957429Smarkm 150162852Sdes for (c = buf, same = j = 0; c < (buf + len); c += SSH_BLOCKSIZE, j++) { 151295367Sdes for (i = HASH(c) & (dctx->n - 1); dctx->h[i] != HASH_UNUSED; 152295367Sdes i = (i + 1) & (dctx->n - 1)) { 153295367Sdes if (!CMP(c, buf + dctx->h[i] * SSH_BLOCKSIZE)) { 154162852Sdes if (++same > MAX_IDENTICAL) 155295367Sdes return DEATTACK_DOS_DETECTED; 156162852Sdes if (check_crc(c, buf, len)) 157295367Sdes return DEATTACK_DETECTED; 15857429Smarkm else 15957429Smarkm break; 16057429Smarkm } 16157429Smarkm } 162295367Sdes dctx->h[i] = j; 16357429Smarkm } 164295367Sdes return DEATTACK_OK; 16557429Smarkm} 166