1  /*
  2   * Copyright (c) 1999 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 KTH nor the names of its contributors may be
 18   *    used to endorse or promote products derived from this software without
 19   *    specific prior written permission.
 20   *
 21   * THIS SOFTWARE IS PROVIDED BY KTH AND ITS CONTRIBUTORS ``AS IS'' AND ANY
 22   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 23   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 24   * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL KTH OR ITS CONTRIBUTORS BE
 25   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 26   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 27   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 28   * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 29   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 30   * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 31   * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
 32  
 33  #include "krb5_locl.h"
 34  
 35  static krb5_error_code
 36  rr13(unsigned char *buf, size_t len)
 37  {
 38      unsigned char *tmp;
 39      size_t bytes = (len + 7) / 8;
 40      size_t i;
 41      if(len == 0)
 42  	return 0;
 43      {
 44  	const int bits = 13 % len;
 45  	const int lbit = len % 8;
 46  
 47  	tmp = malloc(bytes);
 48  	if (tmp == NULL)
 49  	    return ENOMEM;
 50  	memcpy(tmp, buf, bytes);
 51  	if(lbit) {
 52  	    /* pad final byte with inital bits */
 53  	    tmp[bytes - 1] &= 0xff << (8 - lbit);
 54  	    for(i = lbit; i < 8; i += len)
 55  		tmp[bytes - 1] |= buf[0] >> i;
 56  	}
 57  	for(i = 0; i < bytes; i++) {
 58  	    ssize_t bb;
 59  	    ssize_t b1, s1, b2, s2;
 60  	    /* calculate first bit position of this byte */
 61  	    bb = 8 * i - bits;
 62  	    while(bb < 0)
 63  		bb += len;
 64  	    /* byte offset and shift count */
 65  	    b1 = bb / 8;
 66  	    s1 = bb % 8;
 67  
 68  	    if((size_t)bb + 8 > bytes * 8)
 69  		/* watch for wraparound */
 70  		s2 = (len + 8 - s1) % 8;
 71  	    else
 72  		s2 = 8 - s1;
 73  	    b2 = (b1 + 1) % bytes;
 74  	    buf[i] = (tmp[b1] << s1) | (tmp[b2] >> s2);
 75  	}
 76  	free(tmp);
 77      }
 78      return 0;
 79  }
 80  
 81  /* Add `b' to `a', both being one's complement numbers. */
 82  static void
 83  add1(unsigned char *a, unsigned char *b, size_t len)
 84  {
 85      ssize_t i;
 86      int carry = 0;
 87      for(i = len - 1; i >= 0; i--){
 88  	int x = a[i] + b[i] + carry;
 89  	carry = x > 0xff;
 90  	a[i] = x & 0xff;
 91      }
 92      for(i = len - 1; carry && i >= 0; i--){
 93  	int x = a[i] + carry;
 94  	carry = x > 0xff;
 95  	a[i] = x & 0xff;
 96      }
 97  }
 98  
 99  KRB5_LIB_FUNCTION krb5_error_code KRB5_LIB_CALL
100  _krb5_n_fold(const void *str, size_t len, void *key, size_t size)
101  {
102      /* if len < size we need at most N * len bytes, ie < 2 * size;
103         if len > size we need at most 2 * len */
104      krb5_error_code ret = 0;
105      size_t maxlen = 2 * max(size, len);
106      size_t l = 0;
107      unsigned char *tmp = malloc(maxlen);
108      unsigned char *buf = malloc(len);
109  
110      if (tmp == NULL || buf == NULL) {
111          ret = ENOMEM;
112  	goto out;
113      }
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);
131  out:
132      if (buf) {
133          memset(buf, 0, len);
134  	free(buf);
135      }
136      if (tmp) {
137          memset(tmp, 0, maxlen);
138  	free(tmp);
139      }
140      return ret;
141  }