n-fold.c revision 178825
1131087Smarcel/* 2131087Smarcel * Copyright (c) 1999 Kungliga Tekniska H�gskolan 3138215Smarcel * (Royal Institute of Technology, Stockholm, Sweden). 4138215Smarcel * All rights reserved. 5131087Smarcel * 6136910Sru * Redistribution and use in source and binary forms, with or without 7137440Smarcel * modification, are permitted provided that the following conditions 8137440Smarcel * are met: 9137440Smarcel * 10137440Smarcel * 1. Redistributions of source code must retain the above copyright 11137440Smarcel * notice, this list of conditions and the following disclaimer. 12137440Smarcel * 13137440Smarcel * 2. Redistributions in binary form must reproduce the above copyright 14137440Smarcel * notice, this list of conditions and the following disclaimer in the 15137440Smarcel * documentation and/or other materials provided with the distribution. 16137440Smarcel * 17137440Smarcel * 3. Neither the name of KTH nor the names of its contributors may be 18137440Smarcel * used to endorse or promote products derived from this software without 19137440Smarcel * specific prior written permission. 20137440Smarcel * 21138215Smarcel * THIS SOFTWARE IS PROVIDED BY KTH AND ITS CONTRIBUTORS ``AS IS'' AND ANY 22137440Smarcel * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23137440Smarcel * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 24138215Smarcel * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL KTH OR ITS CONTRIBUTORS BE 25138215Smarcel * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 26137440Smarcel * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 27137440Smarcel * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 28137440Smarcel * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 29137440Smarcel * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 30137440Smarcel * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 31137440Smarcel * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 32137440Smarcel 33137440Smarcel#include "krb5_locl.h" 34137440Smarcel 35137440SmarcelRCSID("$Id: n-fold.c 22190 2007-12-06 16:24:22Z lha $"); 36137440Smarcel 37137440Smarcelstatic krb5_error_code 38137440Smarcelrr13(unsigned char *buf, size_t len) 39137440Smarcel{ 40138383Smarcel unsigned char *tmp; 41138383Smarcel int bytes = (len + 7) / 8; 42137440Smarcel int i; 43137440Smarcel if(len == 0) 44137440Smarcel return 0; 45137440Smarcel { 46137440Smarcel const int bits = 13 % len; 47137440Smarcel const int lbit = len % 8; 48137440Smarcel 49134154Sdavidxu tmp = malloc(bytes); 50131087Smarcel if (tmp == NULL) 51138380Smarcel return ENOMEM; 52138215Smarcel memcpy(tmp, buf, bytes); 53138215Smarcel if(lbit) { 54138215Smarcel /* pad final byte with inital bits */ 55134154Sdavidxu tmp[bytes - 1] &= 0xff << (8 - lbit); 56134154Sdavidxu for(i = lbit; i < 8; i += len) 57138215Smarcel tmp[bytes - 1] |= buf[0] >> i; 58138215Smarcel } 59131087Smarcel for(i = 0; i < bytes; i++) { 60131087Smarcel int bb; 61131087Smarcel int b1, s1, b2, s2; 62131087Smarcel /* calculate first bit position of this byte */ 63131087Smarcel bb = 8 * i - bits; 64131087Smarcel while(bb < 0) 65131087Smarcel bb += len; 66131087Smarcel /* byte offset and shift count */ 67131087Smarcel b1 = bb / 8; 68 s1 = bb % 8; 69 70 if(bb + 8 > bytes * 8) 71 /* watch for wraparound */ 72 s2 = (len + 8 - s1) % 8; 73 else 74 s2 = 8 - s1; 75 b2 = (b1 + 1) % bytes; 76 buf[i] = (tmp[b1] << s1) | (tmp[b2] >> s2); 77 } 78 free(tmp); 79 } 80 return 0; 81} 82 83/* Add `b' to `a', both being one's complement numbers. */ 84static void 85add1(unsigned char *a, unsigned char *b, size_t len) 86{ 87 int i; 88 int carry = 0; 89 for(i = len - 1; i >= 0; i--){ 90 int x = a[i] + b[i] + carry; 91 carry = x > 0xff; 92 a[i] = x & 0xff; 93 } 94 for(i = len - 1; carry && i >= 0; i--){ 95 int x = a[i] + carry; 96 carry = x > 0xff; 97 a[i] = x & 0xff; 98 } 99} 100 101krb5_error_code KRB5_LIB_FUNCTION 102_krb5_n_fold(const void *str, size_t len, void *key, size_t size) 103{ 104 /* if len < size we need at most N * len bytes, ie < 2 * size; 105 if len > size we need at most 2 * len */ 106 krb5_error_code ret = 0; 107 size_t maxlen = 2 * max(size, len); 108 size_t l = 0; 109 unsigned char *tmp = malloc(maxlen); 110 unsigned char *buf = malloc(len); 111 112 if (tmp == NULL || buf == NULL) 113 return ENOMEM; 114 115 memcpy(buf, str, len); 116 memset(key, 0, size); 117 do { 118 memcpy(tmp + l, buf, len); 119 l += len; 120 ret = rr13(buf, len * 8); 121 if (ret) 122 goto out; 123 while(l >= size) { 124 add1(key, tmp, size); 125 l -= size; 126 if(l == 0) 127 break; 128 memmove(tmp, tmp + size, l); 129 } 130 } while(l != 0); 131out: 132 memset(buf, 0, len); 133 free(buf); 134 memset(tmp, 0, maxlen); 135 free(tmp); 136 return ret; 137} 138