crypto/openssh/deattack.c

   1 /* $OpenBSD: deattack.c,v 1.32 2015/01/20 23:14:00 deraadt 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 <string.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26
  27 #include "deattack.h"
  28 #include "crc32.h"
  29 #include "sshbuf.h"
  30 #include "misc.h"
  31
  32 /*
  33  * CRC attack detection has a worst-case behaviour that is O(N^3) over
  34  * the number of identical blocks in a packet. This behaviour can be
  35  * exploited to create a limited denial of service attack.
  36  *
  37  * However, because we are dealing with encrypted data, identical
  38  * blocks should only occur every 2^35 maximally-sized packets or so.
  39  * Consequently, we can detect this DoS by looking for identical blocks
  40  * in a packet.
  41  *
  42  * The parameter below determines how many identical blocks we will
  43  * accept in a single packet, trading off between attack detection and
  44  * likelihood of terminating a legitimate connection. A value of 32
  45  * corresponds to an average of 2^40 messages before an attack is
  46  * misdetected
  47  */
  48 #define MAX_IDENTICAL   32
  49
  50 /* SSH Constants */
  51 #define SSH_MAXBLOCKS   (32 * 1024)
  52 #define SSH_BLOCKSIZE   (8)
  53
  54 /* Hashing constants */
  55 #define HASH_MINSIZE    (8 * 1024)
  56 #define HASH_ENTRYSIZE  (2)
  57 #define HASH_FACTOR(x)  ((x)*3/2)
  58 #define HASH_UNUSEDCHAR (0xff)
  59 #define HASH_UNUSED     (0xffff)
  60 #define HASH_IV         (0xfffe)
  61
  62 #define HASH_MINBLOCKS  (7*SSH_BLOCKSIZE)
  63
  64
  65 /* Hash function (Input keys are cipher results) */
  66 #define HASH(x)         PEEK_U32(x)
  67
  68 #define CMP(a, b)       (memcmp(a, b, SSH_BLOCKSIZE))
  69
  70 static void
  71 crc_update(u_int32_t *a, u_int32_t b)
  72 {
  73         b ^= *a;
  74         *a = ssh_crc32((u_char *)&b, sizeof(b));
  75 }
  76
  77 /* detect if a block is used in a particular pattern */
  78 static int
  79 check_crc(const u_char *S, const u_char *buf, u_int32_t len)
  80 {
  81         u_int32_t crc;
  82         const u_char *c;
  83
  84         crc = 0;
  85         for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) {
  86                 if (!CMP(S, c)) {
  87                         crc_update(&crc, 1);
  88                         crc_update(&crc, 0);
  89                 } else {
  90                         crc_update(&crc, 0);
  91                         crc_update(&crc, 0);
  92                 }
  93         }
  94         return crc == 0;
  95 }
  96
  97 void
  98 deattack_init(struct deattack_ctx *dctx)
  99 {
 100         bzero(dctx, sizeof(*dctx));
 101         dctx->n = HASH_MINSIZE / HASH_ENTRYSIZE;
 102 }
 103
 104 /* Detect a crc32 compensation attack on a packet */
 105 int
 106 detect_attack(struct deattack_ctx *dctx, const u_char *buf, u_int32_t len)
 107 {
 108         u_int32_t i, j, l, same;
 109         u_int16_t *tmp;
 110         const u_char *c, *d;
 111
 112         if (len > (SSH_MAXBLOCKS * SSH_BLOCKSIZE) ||
 113             len % SSH_BLOCKSIZE != 0)
 114                 return DEATTACK_ERROR;
 115         for (l = dctx->n; l < HASH_FACTOR(len / SSH_BLOCKSIZE); l = l << 2)
 116                 ;
 117
 118         if (dctx->h == NULL) {
 119                 if ((dctx->h = calloc(l, HASH_ENTRYSIZE)) == NULL)
 120                         return DEATTACK_ERROR;
 121                 dctx->n = l;
 122         } else {
 123                 if (l > dctx->n) {
 124                         if ((tmp = reallocarray(dctx->h, l, HASH_ENTRYSIZE))
 125                             == NULL) {
 126                                 free(dctx->h);
 127                                 dctx->h = NULL;
 128                                 return DEATTACK_ERROR;
 129                         }
 130                         dctx->h = tmp;
 131                         dctx->n = l;
 132                 }
 133         }
 134
 135         if (len <= HASH_MINBLOCKS) {
 136                 for (c = buf; c < buf + len; c += SSH_BLOCKSIZE) {
 137                         for (d = buf; d < c; d += SSH_BLOCKSIZE) {
 138                                 if (!CMP(c, d)) {
 139                                         if ((check_crc(c, buf, len)))
 140                                                 return DEATTACK_DETECTED;
 141                                         else
 142                                                 break;
 143                                 }
 144                         }
 145                 }
 146                 return DEATTACK_OK;
 147         }
 148         memset(dctx->h, HASH_UNUSEDCHAR, dctx->n * HASH_ENTRYSIZE);
 149
 150         for (c = buf, same = j = 0; c < (buf + len); c += SSH_BLOCKSIZE, j++) {
 151                 for (i = HASH(c) & (dctx->n - 1); dctx->h[i] != HASH_UNUSED;
 152                     i = (i + 1) & (dctx->n - 1)) {
 153                         if (!CMP(c, buf + dctx->h[i] * SSH_BLOCKSIZE)) {
 154                                 if (++same > MAX_IDENTICAL)
 155                                         return DEATTACK_DOS_DETECTED;
 156                                 if (check_crc(c, buf, len))
 157                                         return DEATTACK_DETECTED;
 158                                 else
 159                                         break;
 160                         }
 161                 }
 162                 dctx->h[i] = j;
 163         }
 164         return DEATTACK_OK;
 165 }