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
37 static void
rr13(uint8_t * dst1,uint8_t * dst2,uint8_t * src,size_t len)38 rr13(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 */
73 static void
add1(uint8_t * a,uint8_t * b,size_t len)74 add1(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
112 KRB5_LIB_FUNCTION krb5_error_code KRB5_LIB_CALL
_krb5_n_fold(const void * str,size_t len,void * key,size_t size)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