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