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