1/* $NetBSD: n-fold.c,v 1.2 2017/01/28 21:31:49 christos Exp $ */ 2 3/* 4 * Copyright (c) 1999 Kungliga Tekniska H��gskolan 5 * (Royal Institute of Technology, Stockholm, Sweden). 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * 3. Neither the name of KTH nor the names of its contributors may be 20 * used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY KTH AND ITS CONTRIBUTORS ``AS IS'' AND ANY 24 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL KTH OR ITS CONTRIBUTORS BE 27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 30 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 31 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 32 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 33 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 34 35#include "krb5_locl.h" 36 37static void 38rr13(uint8_t *dst1, uint8_t *dst2, uint8_t *src, size_t len) 39{ 40 int bytes = (len + 7) / 8; 41 int i; 42 const int bits = 13 % len; 43 44 for (i = 0; i < bytes; i++) { 45 int bb; 46 int b1, s1, b2, s2; 47 /* calculate first bit position of this byte */ 48 bb = 8 * i - bits; 49 while(bb < 0) 50 bb += len; 51 /* byte offset and shift count */ 52 b1 = bb / 8; 53 s1 = bb % 8; 54 55 if (bb + 8 > bytes * 8) 56 /* watch for wraparound */ 57 s2 = (len + 8 - s1) % 8; 58 else 59 s2 = 8 - s1; 60 b2 = (b1 + 1) % bytes; 61 dst1[i] = (src[b1] << s1) | (src[b2] >> s2); 62 dst2[i] = dst1[i]; 63 } 64 65 return; 66} 67 68/* 69 * Add `b' to `a', both being one's complement numbers. 70 * This function assumes that inputs *a, *b are aligned 71 * to 4 bytes. 72 */ 73static void 74add1(uint8_t *a, uint8_t *b, size_t len) 75{ 76 int i; 77 int carry = 0; 78 uint32_t x; 79 uint32_t left, right; 80 81 for (i = len - 1; (i+1) % 4; i--) { 82 x = a[i] + b[i] + carry; 83 carry = x > 0xff; 84 a[i] = x & 0xff; 85 } 86 87 for (i = len / 4 - 1; i >= 0; i--) { 88 left = ntohl(((uint32_t *)a)[i]); 89 right = ntohl(((uint32_t *)b)[i]); 90 x = left + right + carry; 91 carry = x < left || x < right; 92 ((uint32_t *)a)[i] = x; 93 } 94 95 for (i = len - 1; (i+1) % 4; i--) { 96 x = a[i] + carry; 97 carry = x > 0xff; 98 a[i] = x & 0xff; 99 } 100 101 for (i = len / 4 - 1; carry && i >= 0; i--) { 102 left = ((uint32_t *)a)[i]; 103 x = left + carry; 104 carry = x < left; 105 ((uint32_t *)a)[i] = x; 106 } 107 108 for (i = len / 4 - 1; i >=0; i--) 109 ((uint32_t *)a)[i] = htonl(((uint32_t *)a)[i]); 110} 111 112KRB5_LIB_FUNCTION krb5_error_code KRB5_LIB_CALL 113_krb5_n_fold(const void *str, size_t len, void *key, size_t size) 114{ 115 /* if len < size we need at most N * len bytes, ie < 2 * size; 116 if len > size we need at most 2 * len */ 117 size_t maxlen = 2 * max(size, len); 118 size_t l = 0; 119 uint8_t *tmp; 120 uint8_t *tmpbuf; 121 uint8_t *buf1; 122 uint8_t *buf2; 123 124 tmp = malloc(maxlen + 2 * len); 125 if (tmp == NULL) 126 return ENOMEM; 127 128 buf1 = tmp + maxlen; 129 buf2 = tmp + maxlen + len; 130 131 memset(key, 0, size); 132 memcpy(buf1, str, len); 133 memcpy(tmp, buf1, len); 134 do { 135 l += len; 136 while(l >= size) { 137 add1(key, tmp, size); 138 l -= size; 139 if(l == 0) 140 break; 141 memmove(tmp, tmp + size, l); 142 } 143 rr13(tmp + l, buf2, buf1, len * 8); 144 tmpbuf = buf1; 145 buf1 = buf2; 146 buf2 = tmpbuf; 147 } while(l != 0); 148 149 memset(tmp, 0, maxlen + 2 * len); 150 free(tmp); 151 return 0; 152} 153