src/rxkad/bg-fcrypt.c

   1 /*
   2  * Copyright (c) 1995 - 2000 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33 #include <afsconfig.h>
  34 #include <afs/param.h>
  35 #include <afs/stds.h>
  36
  37 #define DEBUG 0
  38 #ifdef KERNEL
  39 #ifndef UKERNEL
  40 #include "h/types.h"
  41 #if !defined(AFS_LINUX20_ENV) && !defined(AFS_OBSD_ENV)
  42 #include "netinet/in.h"
  43 #endif
  44 #else /* UKERNEL */
  45 #include "afs/sysincludes.h"
  46 #endif /* UKERNEL */
  47 #ifdef AFS_LINUX22_ENV
  48 #include <asm/byteorder.h>
  49 #endif
  50
  51 #else /* KERNEL */
  52 #include <roken.h>
  53 #include <afs/opr.h>
  54
  55 #include <rx/rx.h>
  56 #include <rx/rx_packet.h>
  57 #endif /* KERNEL */
  58
  59 #include "fcrypt.h"
  60 #include "rxkad.h"
  61 #include "fcrypt.h"
  62 #include "private_data.h"
  63 #include "stats.h"
  64
  65 /*
  66  * Unrolling of the inner loops helps the most on pentium chips
  67  * (ca 18%). On risc machines only expect a modest improvement (ca 5%).
  68  * The cost for this is rougly 4k bytes.
  69  */
  70 #define UNROLL_LOOPS 1
  71 /*
  72  * Inline assembler gives a boost only to fc_keysched.
  73  * On the pentium expect ca 28%.
  74  */
  75 /*#define GNU_ASM 1 (now autoconfed) */
  76
  77 #if !defined(inline) && !defined(__GNUC__)
  78 #define inline
  79 #endif
  80
  81 /*
  82  * There is usually no memcpy in kernels but gcc will inline all
  83  * calls to memcpy in this code anyway.
  84  */
  85 #if defined(KERNEL) && !defined(__GNUC__)
  86 #define memcpy(to, from, n) bcopy((from), (to), (n))
  87 #endif
  88
  89 /* Rotate 32 bit word left */
  90 #define ROT32L(x, n) ((((afs_uint32) x) << (n)) | (((afs_uint32) x) >> (32-(n))))
  91 #define octetswap32(x) (((ROT32L(x, 16) & 0x00ff00ff)<<8) | ((ROT32L(x, 16)>>8) & 0x00ff00ff))
  92
  93 #if WORDS_BIGENDIAN
  94 #define NTOH(x) (x)
  95 #else
  96 #define NTOH(x) octetswap32(x)
  97 #endif
  98
  99 /*
 100  * Try to use a good function for ntohl-ing.
 101  *
 102  * The choice is done by autoconf setting EFF_NTOHL to one of:
 103  * CPU          function
 104  * i386         ntohl
 105  * i[4-9]86     bswap
 106  * alpha        bswap32
 107  * all else     ntohl
 108  */
 109
 110 #define EFF_NTOHL(x) ntohl(x)
 111
 112 #if 0
 113 #if defined(__GNUC__) && (defined(i386) || defined(__i386__))
 114 static inline afs_uint32
 115 bswap(afs_uint32 x)
 116 {
 117   asm("bswap %0": "=r"(x):"0"(x));
 118     return x;
 119 }
 120 #endif
 121 #endif
 122
 123 /*
 124  * Sboxes for Feistel network derived from
 125  * /afs/transarc.com/public/afsps/afs.rel31b.export-src/rxkad/sboxes.h
 126  */
 127
 128 #undef Z
 129 #define Z(x) NTOH(x << 3)
 130 static const afs_uint32 sbox0[256] = {
 131     Z(0xea), Z(0x7f), Z(0xb2), Z(0x64), Z(0x9d), Z(0xb0), Z(0xd9), Z(0x11),
 132     Z(0xcd), Z(0x86), Z(0x86),
 133     Z(0x91), Z(0x0a), Z(0xb2), Z(0x93), Z(0x06), Z(0x0e), Z(0x06), Z(0xd2),
 134     Z(0x65), Z(0x73), Z(0xc5),
 135     Z(0x28), Z(0x60), Z(0xf2), Z(0x20), Z(0xb5), Z(0x38), Z(0x7e), Z(0xda),
 136     Z(0x9f), Z(0xe3), Z(0xd2),
 137     Z(0xcf), Z(0xc4), Z(0x3c), Z(0x61), Z(0xff), Z(0x4a), Z(0x4a), Z(0x35),
 138     Z(0xac), Z(0xaa), Z(0x5f),
 139     Z(0x2b), Z(0xbb), Z(0xbc), Z(0x53), Z(0x4e), Z(0x9d), Z(0x78), Z(0xa3),
 140     Z(0xdc), Z(0x09), Z(0x32),
 141     Z(0x10), Z(0xc6), Z(0x6f), Z(0x66), Z(0xd6), Z(0xab), Z(0xa9), Z(0xaf),
 142     Z(0xfd), Z(0x3b), Z(0x95),
 143     Z(0xe8), Z(0x34), Z(0x9a), Z(0x81), Z(0x72), Z(0x80), Z(0x9c), Z(0xf3),
 144     Z(0xec), Z(0xda), Z(0x9f),
 145     Z(0x26), Z(0x76), Z(0x15), Z(0x3e), Z(0x55), Z(0x4d), Z(0xde), Z(0x84),
 146     Z(0xee), Z(0xad), Z(0xc7),
 147     Z(0xf1), Z(0x6b), Z(0x3d), Z(0xd3), Z(0x04), Z(0x49), Z(0xaa), Z(0x24),
 148     Z(0x0b), Z(0x8a), Z(0x83),
 149     Z(0xba), Z(0xfa), Z(0x85), Z(0xa0), Z(0xa8), Z(0xb1), Z(0xd4), Z(0x01),
 150     Z(0xd8), Z(0x70), Z(0x64),
 151     Z(0xf0), Z(0x51), Z(0xd2), Z(0xc3), Z(0xa7), Z(0x75), Z(0x8c), Z(0xa5),
 152     Z(0x64), Z(0xef), Z(0x10),
 153     Z(0x4e), Z(0xb7), Z(0xc6), Z(0x61), Z(0x03), Z(0xeb), Z(0x44), Z(0x3d),
 154     Z(0xe5), Z(0xb3), Z(0x5b),
 155     Z(0xae), Z(0xd5), Z(0xad), Z(0x1d), Z(0xfa), Z(0x5a), Z(0x1e), Z(0x33),
 156     Z(0xab), Z(0x93), Z(0xa2),
 157     Z(0xb7), Z(0xe7), Z(0xa8), Z(0x45), Z(0xa4), Z(0xcd), Z(0x29), Z(0x63),
 158     Z(0x44), Z(0xb6), Z(0x69),
 159     Z(0x7e), Z(0x2e), Z(0x62), Z(0x03), Z(0xc8), Z(0xe0), Z(0x17), Z(0xbb),
 160     Z(0xc7), Z(0xf3), Z(0x3f),
 161     Z(0x36), Z(0xba), Z(0x71), Z(0x8e), Z(0x97), Z(0x65), Z(0x60), Z(0x69),
 162     Z(0xb6), Z(0xf6), Z(0xe6),
 163     Z(0x6e), Z(0xe0), Z(0x81), Z(0x59), Z(0xe8), Z(0xaf), Z(0xdd), Z(0x95),
 164     Z(0x22), Z(0x99), Z(0xfd),
 165     Z(0x63), Z(0x19), Z(0x74), Z(0x61), Z(0xb1), Z(0xb6), Z(0x5b), Z(0xae),
 166     Z(0x54), Z(0xb3), Z(0x70),
 167     Z(0xff), Z(0xc6), Z(0x3b), Z(0x3e), Z(0xc1), Z(0xd7), Z(0xe1), Z(0x0e),
 168     Z(0x76), Z(0xe5), Z(0x36),
 169     Z(0x4f), Z(0x59), Z(0xc7), Z(0x08), Z(0x6e), Z(0x82), Z(0xa6), Z(0x93),
 170     Z(0xc4), Z(0xaa), Z(0x26),
 171     Z(0x49), Z(0xe0), Z(0x21), Z(0x64), Z(0x07), Z(0x9f), Z(0x64), Z(0x81),
 172     Z(0x9c), Z(0xbf), Z(0xf9),
 173     Z(0xd1), Z(0x43), Z(0xf8), Z(0xb6), Z(0xb9), Z(0xf1), Z(0x24), Z(0x75),
 174     Z(0x03), Z(0xe4), Z(0xb0),
 175     Z(0x99), Z(0x46), Z(0x3d), Z(0xf5), Z(0xd1), Z(0x39), Z(0x72), Z(0x12),
 176     Z(0xf6), Z(0xba), Z(0x0c),
 177     Z(0x0d), Z(0x42), Z(0x2e)
 178 };
 179
 180 #undef Z
 181 #define Z(x) NTOH((x << 27) | (x >> 5))
 182 static const afs_uint32 sbox1[256] = {
 183     Z(0x77), Z(0x14), Z(0xa6), Z(0xfe), Z(0xb2), Z(0x5e), Z(0x8c), Z(0x3e),
 184     Z(0x67), Z(0x6c), Z(0xa1),
 185     Z(0x0d), Z(0xc2), Z(0xa2), Z(0xc1), Z(0x85), Z(0x6c), Z(0x7b), Z(0x67),
 186     Z(0xc6), Z(0x23), Z(0xe3),
 187     Z(0xf2), Z(0x89), Z(0x50), Z(0x9c), Z(0x03), Z(0xb7), Z(0x73), Z(0xe6),
 188     Z(0xe1), Z(0x39), Z(0x31),
 189     Z(0x2c), Z(0x27), Z(0x9f), Z(0xa5), Z(0x69), Z(0x44), Z(0xd6), Z(0x23),
 190     Z(0x83), Z(0x98), Z(0x7d),
 191     Z(0x3c), Z(0xb4), Z(0x2d), Z(0x99), Z(0x1c), Z(0x1f), Z(0x8c), Z(0x20),
 192     Z(0x03), Z(0x7c), Z(0x5f),
 193     Z(0xad), Z(0xf4), Z(0xfa), Z(0x95), Z(0xca), Z(0x76), Z(0x44), Z(0xcd),
 194     Z(0xb6), Z(0xb8), Z(0xa1),
 195     Z(0xa1), Z(0xbe), Z(0x9e), Z(0x54), Z(0x8f), Z(0x0b), Z(0x16), Z(0x74),
 196     Z(0x31), Z(0x8a), Z(0x23),
 197     Z(0x17), Z(0x04), Z(0xfa), Z(0x79), Z(0x84), Z(0xb1), Z(0xf5), Z(0x13),
 198     Z(0xab), Z(0xb5), Z(0x2e),
 199     Z(0xaa), Z(0x0c), Z(0x60), Z(0x6b), Z(0x5b), Z(0xc4), Z(0x4b), Z(0xbc),
 200     Z(0xe2), Z(0xaf), Z(0x45),
 201     Z(0x73), Z(0xfa), Z(0xc9), Z(0x49), Z(0xcd), Z(0x00), Z(0x92), Z(0x7d),
 202     Z(0x97), Z(0x7a), Z(0x18),
 203     Z(0x60), Z(0x3d), Z(0xcf), Z(0x5b), Z(0xde), Z(0xc6), Z(0xe2), Z(0xe6),
 204     Z(0xbb), Z(0x8b), Z(0x06),
 205     Z(0xda), Z(0x08), Z(0x15), Z(0x1b), Z(0x88), Z(0x6a), Z(0x17), Z(0x89),
 206     Z(0xd0), Z(0xa9), Z(0xc1),
 207     Z(0xc9), Z(0x70), Z(0x6b), Z(0xe5), Z(0x43), Z(0xf4), Z(0x68), Z(0xc8),
 208     Z(0xd3), Z(0x84), Z(0x28),
 209     Z(0x0a), Z(0x52), Z(0x66), Z(0xa3), Z(0xca), Z(0xf2), Z(0xe3), Z(0x7f),
 210     Z(0x7a), Z(0x31), Z(0xf7),
 211     Z(0x88), Z(0x94), Z(0x5e), Z(0x9c), Z(0x63), Z(0xd5), Z(0x24), Z(0x66),
 212     Z(0xfc), Z(0xb3), Z(0x57),
 213     Z(0x25), Z(0xbe), Z(0x89), Z(0x44), Z(0xc4), Z(0xe0), Z(0x8f), Z(0x23),
 214     Z(0x3c), Z(0x12), Z(0x52),
 215     Z(0xf5), Z(0x1e), Z(0xf4), Z(0xcb), Z(0x18), Z(0x33), Z(0x1f), Z(0xf8),
 216     Z(0x69), Z(0x10), Z(0x9d),
 217     Z(0xd3), Z(0xf7), Z(0x28), Z(0xf8), Z(0x30), Z(0x05), Z(0x5e), Z(0x32),
 218     Z(0xc0), Z(0xd5), Z(0x19),
 219     Z(0xbd), Z(0x45), Z(0x8b), Z(0x5b), Z(0xfd), Z(0xbc), Z(0xe2), Z(0x5c),
 220     Z(0xa9), Z(0x96), Z(0xef),
 221     Z(0x70), Z(0xcf), Z(0xc2), Z(0x2a), Z(0xb3), Z(0x61), Z(0xad), Z(0x80),
 222     Z(0x48), Z(0x81), Z(0xb7),
 223     Z(0x1d), Z(0x43), Z(0xd9), Z(0xd7), Z(0x45), Z(0xf0), Z(0xd8), Z(0x8a),
 224     Z(0x59), Z(0x7c), Z(0x57),
 225     Z(0xc1), Z(0x79), Z(0xc7), Z(0x34), Z(0xd6), Z(0x43), Z(0xdf), Z(0xe4),
 226     Z(0x78), Z(0x16), Z(0x06),
 227     Z(0xda), Z(0x92), Z(0x76), Z(0x51), Z(0xe1), Z(0xd4), Z(0x70), Z(0x03),
 228     Z(0xe0), Z(0x2f), Z(0x96),
 229     Z(0x91), Z(0x82), Z(0x80)
 230 };
 231
 232 #undef Z
 233 #define Z(x) NTOH(x << 11)
 234 static const afs_uint32 sbox2[256] = {
 235     Z(0xf0), Z(0x37), Z(0x24), Z(0x53), Z(0x2a), Z(0x03), Z(0x83), Z(0x86),
 236     Z(0xd1), Z(0xec), Z(0x50),
 237     Z(0xf0), Z(0x42), Z(0x78), Z(0x2f), Z(0x6d), Z(0xbf), Z(0x80), Z(0x87),
 238     Z(0x27), Z(0x95), Z(0xe2),
 239     Z(0xc5), Z(0x5d), Z(0xf9), Z(0x6f), Z(0xdb), Z(0xb4), Z(0x65), Z(0x6e),
 240     Z(0xe7), Z(0x24), Z(0xc8),
 241     Z(0x1a), Z(0xbb), Z(0x49), Z(0xb5), Z(0x0a), Z(0x7d), Z(0xb9), Z(0xe8),
 242     Z(0xdc), Z(0xb7), Z(0xd9),
 243     Z(0x45), Z(0x20), Z(0x1b), Z(0xce), Z(0x59), Z(0x9d), Z(0x6b), Z(0xbd),
 244     Z(0x0e), Z(0x8f), Z(0xa3),
 245     Z(0xa9), Z(0xbc), Z(0x74), Z(0xa6), Z(0xf6), Z(0x7f), Z(0x5f), Z(0xb1),
 246     Z(0x68), Z(0x84), Z(0xbc),
 247     Z(0xa9), Z(0xfd), Z(0x55), Z(0x50), Z(0xe9), Z(0xb6), Z(0x13), Z(0x5e),
 248     Z(0x07), Z(0xb8), Z(0x95),
 249     Z(0x02), Z(0xc0), Z(0xd0), Z(0x6a), Z(0x1a), Z(0x85), Z(0xbd), Z(0xb6),
 250     Z(0xfd), Z(0xfe), Z(0x17),
 251     Z(0x3f), Z(0x09), Z(0xa3), Z(0x8d), Z(0xfb), Z(0xed), Z(0xda), Z(0x1d),
 252     Z(0x6d), Z(0x1c), Z(0x6c),
 253     Z(0x01), Z(0x5a), Z(0xe5), Z(0x71), Z(0x3e), Z(0x8b), Z(0x6b), Z(0xbe),
 254     Z(0x29), Z(0xeb), Z(0x12),
 255     Z(0x19), Z(0x34), Z(0xcd), Z(0xb3), Z(0xbd), Z(0x35), Z(0xea), Z(0x4b),
 256     Z(0xd5), Z(0xae), Z(0x2a),
 257     Z(0x79), Z(0x5a), Z(0xa5), Z(0x32), Z(0x12), Z(0x7b), Z(0xdc), Z(0x2c),
 258     Z(0xd0), Z(0x22), Z(0x4b),
 259     Z(0xb1), Z(0x85), Z(0x59), Z(0x80), Z(0xc0), Z(0x30), Z(0x9f), Z(0x73),
 260     Z(0xd3), Z(0x14), Z(0x48),
 261     Z(0x40), Z(0x07), Z(0x2d), Z(0x8f), Z(0x80), Z(0x0f), Z(0xce), Z(0x0b),
 262     Z(0x5e), Z(0xb7), Z(0x5e),
 263     Z(0xac), Z(0x24), Z(0x94), Z(0x4a), Z(0x18), Z(0x15), Z(0x05), Z(0xe8),
 264     Z(0x02), Z(0x77), Z(0xa9),
 265     Z(0xc7), Z(0x40), Z(0x45), Z(0x89), Z(0xd1), Z(0xea), Z(0xde), Z(0x0c),
 266     Z(0x79), Z(0x2a), Z(0x99),
 267     Z(0x6c), Z(0x3e), Z(0x95), Z(0xdd), Z(0x8c), Z(0x7d), Z(0xad), Z(0x6f),
 268     Z(0xdc), Z(0xff), Z(0xfd),
 269     Z(0x62), Z(0x47), Z(0xb3), Z(0x21), Z(0x8a), Z(0xec), Z(0x8e), Z(0x19),
 270     Z(0x18), Z(0xb4), Z(0x6e),
 271     Z(0x3d), Z(0xfd), Z(0x74), Z(0x54), Z(0x1e), Z(0x04), Z(0x85), Z(0xd8),
 272     Z(0xbc), Z(0x1f), Z(0x56),
 273     Z(0xe7), Z(0x3a), Z(0x56), Z(0x67), Z(0xd6), Z(0xc8), Z(0xa5), Z(0xf3),
 274     Z(0x8e), Z(0xde), Z(0xae),
 275     Z(0x37), Z(0x49), Z(0xb7), Z(0xfa), Z(0xc8), Z(0xf4), Z(0x1f), Z(0xe0),
 276     Z(0x2a), Z(0x9b), Z(0x15),
 277     Z(0xd1), Z(0x34), Z(0x0e), Z(0xb5), Z(0xe0), Z(0x44), Z(0x78), Z(0x84),
 278     Z(0x59), Z(0x56), Z(0x68),
 279     Z(0x77), Z(0xa5), Z(0x14), Z(0x06), Z(0xf5), Z(0x2f), Z(0x8c), Z(0x8a),
 280     Z(0x73), Z(0x80), Z(0x76),
 281     Z(0xb4), Z(0x10), Z(0x86)
 282 };
 283
 284 #undef Z
 285 #define Z(x) NTOH(x << 19)
 286 static const afs_uint32 sbox3[256] = {
 287     Z(0xa9), Z(0x2a), Z(0x48), Z(0x51), Z(0x84), Z(0x7e), Z(0x49), Z(0xe2),
 288     Z(0xb5), Z(0xb7), Z(0x42),
 289     Z(0x33), Z(0x7d), Z(0x5d), Z(0xa6), Z(0x12), Z(0x44), Z(0x48), Z(0x6d),
 290     Z(0x28), Z(0xaa), Z(0x20),
 291     Z(0x6d), Z(0x57), Z(0xd6), Z(0x6b), Z(0x5d), Z(0x72), Z(0xf0), Z(0x92),
 292     Z(0x5a), Z(0x1b), Z(0x53),
 293     Z(0x80), Z(0x24), Z(0x70), Z(0x9a), Z(0xcc), Z(0xa7), Z(0x66), Z(0xa1),
 294     Z(0x01), Z(0xa5), Z(0x41),
 295     Z(0x97), Z(0x41), Z(0x31), Z(0x82), Z(0xf1), Z(0x14), Z(0xcf), Z(0x53),
 296     Z(0x0d), Z(0xa0), Z(0x10),
 297     Z(0xcc), Z(0x2a), Z(0x7d), Z(0xd2), Z(0xbf), Z(0x4b), Z(0x1a), Z(0xdb),
 298     Z(0x16), Z(0x47), Z(0xf6),
 299     Z(0x51), Z(0x36), Z(0xed), Z(0xf3), Z(0xb9), Z(0x1a), Z(0xa7), Z(0xdf),
 300     Z(0x29), Z(0x43), Z(0x01),
 301     Z(0x54), Z(0x70), Z(0xa4), Z(0xbf), Z(0xd4), Z(0x0b), Z(0x53), Z(0x44),
 302     Z(0x60), Z(0x9e), Z(0x23),
 303     Z(0xa1), Z(0x18), Z(0x68), Z(0x4f), Z(0xf0), Z(0x2f), Z(0x82), Z(0xc2),
 304     Z(0x2a), Z(0x41), Z(0xb2),
 305     Z(0x42), Z(0x0c), Z(0xed), Z(0x0c), Z(0x1d), Z(0x13), Z(0x3a), Z(0x3c),
 306     Z(0x6e), Z(0x35), Z(0xdc),
 307     Z(0x60), Z(0x65), Z(0x85), Z(0xe9), Z(0x64), Z(0x02), Z(0x9a), Z(0x3f),
 308     Z(0x9f), Z(0x87), Z(0x96),
 309     Z(0xdf), Z(0xbe), Z(0xf2), Z(0xcb), Z(0xe5), Z(0x6c), Z(0xd4), Z(0x5a),
 310     Z(0x83), Z(0xbf), Z(0x92),
 311     Z(0x1b), Z(0x94), Z(0x00), Z(0x42), Z(0xcf), Z(0x4b), Z(0x00), Z(0x75),
 312     Z(0xba), Z(0x8f), Z(0x76),
 313     Z(0x5f), Z(0x5d), Z(0x3a), Z(0x4d), Z(0x09), Z(0x12), Z(0x08), Z(0x38),
 314     Z(0x95), Z(0x17), Z(0xe4),
 315     Z(0x01), Z(0x1d), Z(0x4c), Z(0xa9), Z(0xcc), Z(0x85), Z(0x82), Z(0x4c),
 316     Z(0x9d), Z(0x2f), Z(0x3b),
 317     Z(0x66), Z(0xa1), Z(0x34), Z(0x10), Z(0xcd), Z(0x59), Z(0x89), Z(0xa5),
 318     Z(0x31), Z(0xcf), Z(0x05),
 319     Z(0xc8), Z(0x84), Z(0xfa), Z(0xc7), Z(0xba), Z(0x4e), Z(0x8b), Z(0x1a),
 320     Z(0x19), Z(0xf1), Z(0xa1),
 321     Z(0x3b), Z(0x18), Z(0x12), Z(0x17), Z(0xb0), Z(0x98), Z(0x8d), Z(0x0b),
 322     Z(0x23), Z(0xc3), Z(0x3a),
 323     Z(0x2d), Z(0x20), Z(0xdf), Z(0x13), Z(0xa0), Z(0xa8), Z(0x4c), Z(0x0d),
 324     Z(0x6c), Z(0x2f), Z(0x47),
 325     Z(0x13), Z(0x13), Z(0x52), Z(0x1f), Z(0x2d), Z(0xf5), Z(0x79), Z(0x3d),
 326     Z(0xa2), Z(0x54), Z(0xbd),
 327     Z(0x69), Z(0xc8), Z(0x6b), Z(0xf3), Z(0x05), Z(0x28), Z(0xf1), Z(0x16),
 328     Z(0x46), Z(0x40), Z(0xb0),
 329     Z(0x11), Z(0xd3), Z(0xb7), Z(0x95), Z(0x49), Z(0xcf), Z(0xc3), Z(0x1d),
 330     Z(0x8f), Z(0xd8), Z(0xe1),
 331     Z(0x73), Z(0xdb), Z(0xad), Z(0xc8), Z(0xc9), Z(0xa9), Z(0xa1), Z(0xc2),
 332     Z(0xc5), Z(0xe3), Z(0xba),
 333     Z(0xfc), Z(0x0e), Z(0x25)
 334 };
 335
 336 /*
 337  * This is a 16 round Feistel network with permutation F_ENCRYPT
 338  */
 339
 340 #define F_ENCRYPT(R, L, sched) { \
 341  union lc4 { afs_uint32 l; unsigned char c[4]; } un; \
 342  un.l = sched ^ R; \
 343  L ^= sbox0[un.c[0]] ^ sbox1[un.c[1]] ^ sbox2[un.c[2]] ^ sbox3[un.c[3]]; }
 344
 345 #ifndef WORDS_BIGENDIAN
 346 /* BEWARE: this code is endian dependent.
 347  * This should really be inline assembler on the x86.
 348  */
 349 #undef F_ENCRYPT
 350 #define FF(y, shiftN) (((y) >> shiftN) & 0xFF)
 351 #define F_ENCRYPT(R, L, sched) { \
 352  afs_uint32 un; \
 353  un = sched ^ R; \
 354  L ^= sbox0[FF(un, 0)] ^ sbox1[FF(un, 8)] ^ sbox2[FF(un, 16)] ^ sbox3[FF(un, 24)];}
 355 #endif
 356
 357 static inline void
 358 fc_ecb_enc(afs_uint32 l, afs_uint32 r, afs_uint32 out[2],
 359            const afs_int32 sched[MAXROUNDS])
 360 {
 361 #if !defined(UNROLL_LOOPS)
 362     {
 363         int i;
 364         for (i = 0; i < (MAXROUNDS / 4); i++) {
 365             F_ENCRYPT(r, l, *sched++);
 366             F_ENCRYPT(l, r, *sched++);
 367             F_ENCRYPT(r, l, *sched++);
 368             F_ENCRYPT(l, r, *sched++);
 369         }
 370     }
 371 #else
 372     F_ENCRYPT(r, l, *sched++);
 373     F_ENCRYPT(l, r, *sched++);
 374     F_ENCRYPT(r, l, *sched++);
 375     F_ENCRYPT(l, r, *sched++);
 376     F_ENCRYPT(r, l, *sched++);
 377     F_ENCRYPT(l, r, *sched++);
 378     F_ENCRYPT(r, l, *sched++);
 379     F_ENCRYPT(l, r, *sched++);
 380     F_ENCRYPT(r, l, *sched++);
 381     F_ENCRYPT(l, r, *sched++);
 382     F_ENCRYPT(r, l, *sched++);
 383     F_ENCRYPT(l, r, *sched++);
 384     F_ENCRYPT(r, l, *sched++);
 385     F_ENCRYPT(l, r, *sched++);
 386     F_ENCRYPT(r, l, *sched++);
 387     F_ENCRYPT(l, r, *sched++);
 388 #endif /* UNROLL_LOOPS */
 389
 390     out[0] = l;
 391     out[1] = r;
 392 }
 393
 394 static inline void
 395 fc_ecb_dec(afs_uint32 l, afs_uint32 r, afs_uint32 out[2],
 396            const afs_int32 sched[MAXROUNDS])
 397 {
 398     sched = &sched[MAXROUNDS - 1];
 399
 400 #if !defined(UNROLL_LOOPS)
 401     {
 402         int i;
 403         for (i = 0; i < (MAXROUNDS / 4); i++) {
 404             F_ENCRYPT(l, r, *sched--);
 405             F_ENCRYPT(r, l, *sched--);
 406             F_ENCRYPT(l, r, *sched--);
 407             F_ENCRYPT(r, l, *sched--);
 408         }
 409     }
 410 #else
 411     F_ENCRYPT(l, r, *sched--);
 412     F_ENCRYPT(r, l, *sched--);
 413     F_ENCRYPT(l, r, *sched--);
 414     F_ENCRYPT(r, l, *sched--);
 415     F_ENCRYPT(l, r, *sched--);
 416     F_ENCRYPT(r, l, *sched--);
 417     F_ENCRYPT(l, r, *sched--);
 418     F_ENCRYPT(r, l, *sched--);
 419     F_ENCRYPT(l, r, *sched--);
 420     F_ENCRYPT(r, l, *sched--);
 421     F_ENCRYPT(l, r, *sched--);
 422     F_ENCRYPT(r, l, *sched--);
 423     F_ENCRYPT(l, r, *sched--);
 424     F_ENCRYPT(r, l, *sched--);
 425     F_ENCRYPT(l, r, *sched--);
 426     F_ENCRYPT(r, l, *sched--);
 427 #endif /* UNROLL_LOOPS */
 428
 429     out[0] = l;
 430     out[1] = r;
 431 }
 432
 433 static inline void
 434 fc_cbc_enc(const afs_uint32 * in, afs_uint32 * out, afs_int32 length,
 435            const afs_int32 sched[MAXROUNDS], afs_uint32 * iv)
 436 {
 437     afs_int32 xor0 = iv[0], xor1 = iv[1];
 438
 439     for (; length > 0; length -= 8) {
 440         afs_uint32 b8[2];
 441         /* If length < 8 we read to much, usally ok */
 442         xor0 ^= in[0];
 443         xor1 ^= in[1];
 444         fc_ecb_enc(xor0, xor1, b8, sched);
 445         xor0 = in[0] ^ b8[0];
 446         xor1 = in[1] ^ b8[1];
 447
 448         /* Out is always a multiple of 8 */
 449         memcpy(out, b8, 8);
 450         out += 2;
 451         in += 2;
 452     }
 453     iv[0] = xor0;
 454     iv[1] = xor1;
 455 }
 456
 457 static inline void
 458 fc_cbc_dec(const afs_uint32 * in, afs_uint32 * out, afs_int32 length,
 459            const afs_int32 sched[MAXROUNDS], afs_uint32 * iv)
 460 {
 461     afs_int32 xor0 = iv[0], xor1 = iv[1];
 462
 463     for (; length > 0; length -= 8) {
 464         afs_uint32 b8[2];
 465         /* In is always a multiple of 8 */
 466         fc_ecb_dec(in[0], in[1], b8, sched);
 467         b8[0] ^= xor0;
 468         b8[1] ^= xor1;
 469         xor0 = in[0] ^ b8[0];
 470         xor1 = in[1] ^ b8[1];
 471
 472 #if 0
 473         if (length >= 8)
 474             memcpy(out, b8, 8);
 475         else
 476             memcpy(out, b8, length);    /* Don't write to much when length < 8 */
 477 #else
 478         /* If length < 8 we write to much, this is not always ok */
 479         memcpy(out, b8, 8);
 480 #endif
 481         out += 2;
 482         in += 2;
 483     }
 484     iv[0] = xor0;
 485     iv[1] = xor1;
 486 }
 487
 488 afs_int32
 489 fc_ecb_encrypt(afs_uint32 * in, afs_uint32 * out, fc_KeySchedule sched,
 490                int encrypt)
 491 {
 492     INC_RXKAD_STATS(fc_encrypts[encrypt]);
 493     if (encrypt)
 494         fc_ecb_enc(in[0], in[1], out, sched);
 495     else
 496         fc_ecb_dec(in[0], in[1], out, sched);
 497     return 0;
 498 }
 499
 500 afs_int32
 501 fc_cbc_encrypt(afs_uint32 * in, afs_uint32 * out, afs_int32 length,
 502                fc_KeySchedule sched, afs_uint32 * iv, int encrypt)
 503 {
 504     if (encrypt)
 505         fc_cbc_enc(in, out, length, sched, iv);
 506     else
 507         fc_cbc_dec(in, out, length, sched, iv);
 508     return 0;
 509 }
 510
 511 /* Rotate two 32 bit numbers as a 56 bit number */
 512 #define ROT56R(hi, lo, n) { \
 513   afs_uint32 t = lo & ((1<<n)-1); \
 514   lo = (lo >> n) | ((hi & ((1<<n)-1)) << (32-n)); \
 515   hi = (hi >> n) | (t << (24-n)); }
 516
 517 /* Rotate one 64 bit number as a 56 bit number */
 518 #define ROT56R64(k, n) { \
 519   k = (k >> n) | ((k & ((1<<n) - 1)) << (56-n)); }
 520
 521 /*
 522  * Generate a key schedule from key, the least significant bit in each
 523  * key byte is parity and shall be ignored. This leaves 56 significant
 524  * bits in the key to scatter over the 16 key schedules. For each
 525  * schedule extract the low order 32 bits and use as schedule, then
 526  * rotate right by 11 bits.
 527  *
 528  * Note that this fc_keysched() generates a schedule in natural byte
 529  * order, the Transarc function does not. Therefore it's *not*
 530  * possible to mix fc_keysched, fc_ecb_encrypt and fc_cbc_encrypt
 531  * from different implementations. Keep them in the same module!
 532  */
 533 int
 534 fc_keysched(void *key_, fc_KeySchedule sched)
 535 {
 536     const unsigned char *key = key_;
 537
 538     /* Do we have 56 bit longs or even longer longs? */
 539     afs_uint64 k;               /* k holds all 56 non parity bits */
 540
 541     /* Compress out parity bits */
 542     k = (*key++) >> 1;
 543     k <<= 7;
 544     k |= (*key++) >> 1;
 545     k <<= 7;
 546     k |= (*key++) >> 1;
 547     k <<= 7;
 548     k |= (*key++) >> 1;
 549     k <<= 7;
 550     k |= (*key++) >> 1;
 551     k <<= 7;
 552     k |= (*key++) >> 1;
 553     k <<= 7;
 554     k |= (*key++) >> 1;
 555     k <<= 7;
 556     k |= (*key) >> 1;
 557
 558     /* Use lower 32 bits for schedule, rotate by 11 each round (16 times) */
 559     *sched++ = EFF_NTOHL((afs_uint32) k);
 560     ROT56R64(k, 11);
 561     *sched++ = EFF_NTOHL((afs_uint32) k);
 562     ROT56R64(k, 11);
 563     *sched++ = EFF_NTOHL((afs_uint32) k);
 564     ROT56R64(k, 11);
 565     *sched++ = EFF_NTOHL((afs_uint32) k);
 566     ROT56R64(k, 11);
 567
 568     *sched++ = EFF_NTOHL((afs_uint32) k);
 569     ROT56R64(k, 11);
 570     *sched++ = EFF_NTOHL((afs_uint32) k);
 571     ROT56R64(k, 11);
 572     *sched++ = EFF_NTOHL((afs_uint32) k);
 573     ROT56R64(k, 11);
 574     *sched++ = EFF_NTOHL((afs_uint32) k);
 575     ROT56R64(k, 11);
 576
 577     *sched++ = EFF_NTOHL((afs_uint32) k);
 578     ROT56R64(k, 11);
 579     *sched++ = EFF_NTOHL((afs_uint32) k);
 580     ROT56R64(k, 11);
 581     *sched++ = EFF_NTOHL((afs_uint32) k);
 582     ROT56R64(k, 11);
 583     *sched++ = EFF_NTOHL((afs_uint32) k);
 584     ROT56R64(k, 11);
 585
 586     *sched++ = EFF_NTOHL((afs_uint32) k);
 587     ROT56R64(k, 11);
 588     *sched++ = EFF_NTOHL((afs_uint32) k);
 589     ROT56R64(k, 11);
 590     *sched++ = EFF_NTOHL((afs_uint32) k);
 591     ROT56R64(k, 11);
 592     *sched++ = EFF_NTOHL((afs_uint32) k);
 593
 594     INC_RXKAD_STATS(fc_key_scheds);
 595     return 0;
 596 }
 597
 598 /*
 599  * Encryption/decryption of Rx packets is pretty straight forward. Run
 600  * fc_cbc_encrypt over the packet fragments until len bytes have been
 601  * processed. Skip the Rx packet header but not the security header.
 602  */
 603 afs_int32
 604 rxkad_EncryptPacket(const struct rx_connection * rx_connection_not_used,
 605                     const fc_KeySchedule * sched, const afs_uint32 * iv,
 606                     int len, struct rx_packet * packet)
 607 {
 608     afs_uint32 ivec[2];
 609     struct iovec *frag;
 610     struct rx_securityClass *obj;
 611     struct rxkad_cprivate *tp;  /* s & c have type at same offset */
 612
 613     obj = rx_SecurityObjectOf(rx_connection_not_used);
 614     tp = (struct rxkad_cprivate *)obj->privateData;
 615     ADD_RXKAD_STATS(bytesEncrypted[rxkad_TypeIndex(tp->type)],len);
 616     {
 617         /* What is this good for?
 618          * It turns out that the security header for auth_enc is of
 619          * size 8 bytes and the last 4 bytes are defined to be 0!
 620          */
 621         afs_uint32 *t = (afs_uint32 *) packet->wirevec[1].iov_base;
 622         t[1] = 0;
 623     }
 624
 625     memcpy(ivec, iv, sizeof(ivec));     /* Must use copy of iv */
 626     for (frag = &packet->wirevec[1]; len; frag++) {
 627         int ilen = frag->iov_len;
 628         afs_uint32 *ibas = (afs_uint32 *) frag->iov_base;
 629         if (ilen == 0)
 630             return RXKADDATALEN;        /* Length mismatch */
 631         if (len < ilen)
 632             ilen = len; /* Don't process to much data */
 633         fc_cbc_enc(ibas, ibas, ilen, sched, ivec);
 634         len -= ilen;
 635     }
 636     return 0;
 637 }
 638
 639 afs_int32
 640 rxkad_DecryptPacket(const struct rx_connection * rx_connection_not_used,
 641                     const fc_KeySchedule * sched, const afs_uint32 * iv,
 642                     int len, struct rx_packet * packet)
 643 {
 644     afs_uint32 ivec[2];
 645     struct iovec *frag;
 646     struct rx_securityClass *obj;
 647     struct rxkad_cprivate *tp;  /* s & c have type at same offset */
 648
 649     obj = rx_SecurityObjectOf(rx_connection_not_used);
 650     tp = (struct rxkad_cprivate *)obj->privateData;
 651     ADD_RXKAD_STATS(bytesDecrypted[rxkad_TypeIndex(tp->type)],len);
 652     memcpy(ivec, iv, sizeof(ivec));     /* Must use copy of iv */
 653     for (frag = &packet->wirevec[1]; len > 0; frag++) {
 654         int ilen = frag->iov_len;
 655         afs_uint32 *ibas = (afs_uint32 *) frag->iov_base;
 656         if (ilen == 0)
 657             return RXKADDATALEN;        /* Length mismatch */
 658         if (len < ilen)
 659             ilen = len; /* Don't process to much data */
 660         fc_cbc_dec(ibas, ibas, ilen, sched, ivec);
 661         len -= ilen;
 662     }
 663     return 0;
 664 }
 665
 666 #if defined(TEST) || defined(TEST_KERNEL)
 667 /*
 668  * It is possible to link with the client kernel libafs.a to verify
 669  * the test case. Use TEST_KERNEL to get the mangled names.
 670  */
 671
 672 const char the_quick[] = "The quick brown fox jumps over the lazy dogs.\0\0";
 673
 674 const unsigned char key1[8] =
 675     { 0xf0, 0xe1, 0xd2, 0xc3, 0xb4, 0xa5, 0x96, 0x87 };
 676 const char ciph1[] = {
 677     0x00, 0xf0, 0xe, 0x11, 0x75, 0xe6, 0x23, 0x82, 0xee, 0xac, 0x98, 0x62,
 678     0x44, 0x51, 0xe4, 0x84, 0xc3, 0x59, 0xd8, 0xaa, 0x64, 0x60, 0xae, 0xf7,
 679     0xd2, 0xd9, 0x13, 0x79, 0x72, 0xa3, 0x45, 0x03, 0x23, 0xb5, 0x62, 0xd7,
 680     0xc, 0xf5, 0x27, 0xd1, 0xf8, 0x91, 0x3c, 0xac, 0x44, 0x22, 0x92, 0xef
 681 };
 682
 683 const unsigned char key2[8] =
 684     { 0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10 };
 685 const char ciph2[] = {
 686     0xca, 0x90, 0xf5, 0x9d, 0xcb, 0xd4, 0xd2, 0x3c, 0x01, 0x88, 0x7f, 0x3e,
 687     0x31, 0x6e, 0x62, 0x9d, 0xd8, 0xe0, 0x57, 0xa3, 0x06, 0x3a, 0x42, 0x58,
 688     0x2a, 0x28, 0xfe, 0x72, 0x52, 0x2f, 0xdd, 0xe0, 0x19, 0x89, 0x09, 0x1c,
 689     0x2a, 0x8e, 0x8c, 0x94, 0xfc, 0xc7, 0x68, 0xe4, 0x88, 0xaa, 0xde, 0x0f
 690 };
 691
 692 #ifdef TEST_KERNEL
 693 #define fc_keysched    _afs_QTKrFdpoFL
 694 #define fc_ecb_encrypt _afs_sDLThwNLok
 695 #define fc_cbc_encrypt _afs_fkyCWTvfRS
 696 #define rxkad_DecryptPacket _afs_SRWEeqTXrS
 697 #define rxkad_EncryptPacket _afs_bpwQbdoghO
 698 #endif
 699
 700 int
 701 rx_SlowPutInt32()
 702 {
 703     abort();
 704 }
 705
 706 int
 707 main()
 708 {
 709     afs_int32 sched[MAXROUNDS];
 710     char ciph[100], clear[100], tmp[100];
 711     afs_uint32 data[2];
 712     afs_uint32 iv[2];
 713     struct rx_packet packet;
 714
 715     if (sizeof(afs_int32) != 4)
 716         fprintf(stderr, "error: sizeof(afs_int32) != 4\n");
 717     if (sizeof(afs_uint32) != 4)
 718         fprintf(stderr, "error: sizeof(afs_uint32) != 4\n");
 719
 720     /*
 721      * Use key1 and key2 as iv */
 722     fc_keysched(key1, sched);
 723     memcpy(iv, key2, sizeof(iv));
 724     fc_cbc_encrypt(the_quick, ciph, sizeof(the_quick), sched, iv, ENCRYPT);
 725     if (memcmp(ciph1, ciph, sizeof(ciph1)) != 0)
 726         fprintf(stderr, "encrypt FAILED\n");
 727     memcpy(iv, key2, sizeof(iv));
 728     fc_cbc_encrypt(ciph, clear, sizeof(the_quick), sched, iv, DECRYPT);
 729     if (strcmp(the_quick, clear) != 0)
 730         fprintf(stderr, "crypt decrypt FAILED\n");
 731
 732     /*
 733      * Use key2 and key1 as iv
 734      */
 735     fc_keysched(key2, sched);
 736     memcpy(iv, key1, sizeof(iv));
 737     fc_cbc_encrypt(the_quick, ciph, sizeof(the_quick), sched, iv, ENCRYPT);
 738     if (memcmp(ciph2, ciph, sizeof(ciph2)) != 0)
 739         fprintf(stderr, "encrypt FAILED\n");
 740     memcpy(iv, key1, sizeof(iv));
 741     fc_cbc_encrypt(ciph, clear, sizeof(the_quick), sched, iv, DECRYPT);
 742     if (strcmp(the_quick, clear) != 0)
 743         fprintf(stderr, "crypt decrypt FAILED\n");
 744
 745     /*
 746      * Test Encrypt- and Decrypt-Packet, use key1 and key2 as iv
 747      */
 748     fc_keysched(key1, sched);
 749     memcpy(iv, key2, sizeof(iv));
 750     strcpy(clear, the_quick);
 751     packet.wirevec[1].iov_base = clear;
 752     packet.wirevec[1].iov_len = sizeof(the_quick);
 753     packet.wirevec[2].iov_len = 0;
 754
 755     /* For unknown reasons bytes 4-7 are zeroed in rxkad_EncryptPacket */
 756     rxkad_EncryptPacket(tmp, sched, iv, sizeof(the_quick), &packet);
 757     rxkad_DecryptPacket(tmp, sched, iv, sizeof(the_quick), &packet);
 758     clear[4] ^= 'q';
 759     clear[5] ^= 'u';
 760     clear[6] ^= 'i';
 761     clear[7] ^= 'c';
 762     if (strcmp(the_quick, clear) != 0)
 763         fprintf(stderr, "rxkad_EncryptPacket/rxkad_DecryptPacket FAILED\n");
 764
 765     {
 766         struct timeval start, stop;
 767         int i;
 768
 769         fc_keysched(key1, sched);
 770         gettimeofday(&start, NULL);
 771         for (i = 0; i < 1000000; i++)
 772             fc_keysched(key1, sched);
 773         gettimeofday(&stop, NULL);
 774         printf("fc_keysched    = %2.2f us\n",
 775                (stop.tv_sec - start.tv_sec +
 776                 (stop.tv_usec - start.tv_usec) / 1e6) * 1);
 777
 778         fc_ecb_encrypt(data, data, sched, ENCRYPT);
 779         gettimeofday(&start, NULL);
 780         for (i = 0; i < 1000000; i++)
 781             fc_ecb_encrypt(data, data, sched, ENCRYPT);
 782         gettimeofday(&stop, 0);
 783         printf("fc_ecb_encrypt = %2.2f us\n",
 784                (stop.tv_sec - start.tv_sec +
 785                 (stop.tv_usec - start.tv_usec) / 1e6) * 1);
 786
 787         fc_cbc_encrypt(the_quick, ciph, sizeof(the_quick), sched, iv,
 788                        ENCRYPT);
 789         gettimeofday(&start, NULL);
 790         for (i = 0; i < 100000; i++)
 791             fc_cbc_encrypt(the_quick, ciph, sizeof(the_quick), sched, iv,
 792                            ENCRYPT);
 793         gettimeofday(&stop, NULL);
 794         printf("fc_cbc_encrypt = %2.2f us\n",
 795                (stop.tv_sec - start.tv_sec +
 796                 (stop.tv_usec - start.tv_usec) / 1e6) * 10);
 797
 798     }
 799
 800     exit(0);
 801 }
 802 #endif /* TEST */