Line data    Source code

       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 void
      36    49287862 : rr13(uint8_t *dst1, uint8_t *dst2, uint8_t *src, size_t len)
      37             : {
      38    49287862 :     int bytes = (len + 7) / 8;
      39     1630576 :     int i;
      40    49287862 :     const int bits = 13 % len;
      41             : 
      42   274297846 :     for (i = 0; i < bytes; i++) {
      43     7313824 :         int bb;
      44     7313824 :         int b1, s1, b2, s2;
      45             :         /* calculate first bit position of this byte */
      46   225009984 :         bb = 8 * i - bits;
      47   323585708 :         while(bb < 0)
      48    98575724 :             bb += len;
      49             :         /* byte offset and shift count */
      50   225009984 :         b1 = bb / 8;
      51   225009984 :         s1 = bb % 8;
      52             : 
      53   225009984 :         if (bb + 8 > bytes * 8)
      54             :             /* watch for wraparound */
      55    49287862 :             s2 = (len + 8 - s1) % 8;
      56             :         else
      57   175722122 :             s2 = 8 - s1;
      58   225009984 :         b2 = (b1 + 1) % bytes;
      59   225009984 :         dst1[i] = (src[b1] << s1) | (src[b2] >> s2);
      60   225009984 :         dst2[i] = dst1[i];
      61             :     }
      62             : 
      63    49287862 :     return;
      64             : }
      65             : 
      66             : /*
      67             :  * Add `b' to `a', both being one's complement numbers.
      68             :  * This function assumes that inputs *a, *b are aligned
      69             :  * to 4 bytes.
      70             :  */
      71             : static void
      72    14063124 : add1(uint8_t *a, uint8_t *b, size_t len)
      73             : {
      74      457114 :     int i;
      75    14063124 :     int carry = 0;
      76      457114 :     uint32_t x;
      77      457114 :     uint32_t left, right;
      78             : 
      79    14063124 :     for (i = len - 1; (i+1) % 4; i--) {
      80           0 :         x = a[i] + b[i] + carry;
      81           0 :         carry = x > 0xff;
      82           0 :         a[i] = x & 0xff;
      83             :     }
      84             : 
      85    70315620 :     for (i = len / 4 - 1; i >= 0; i--) {
      86    56252496 :         left = ntohl(((uint32_t *)a)[i]);
      87    56252496 :         right = ntohl(((uint32_t *)b)[i]);
      88    56252496 :         x = left + right + carry;
      89    56252496 :         carry = x < left || x < right;
      90    56252496 :         ((uint32_t *)a)[i]  = x;
      91             :     }
      92             : 
      93    14063124 :     for (i = len - 1; (i+1) % 4; i--) {
      94           0 :         x = a[i] + carry;
      95           0 :         carry = x > 0xff;
      96           0 :         a[i] = x & 0xff;
      97             :     }
      98             : 
      99    15062574 :     for (i = len / 4 - 1; carry && i >= 0; i--) {
     100      999450 :         left = ((uint32_t *)a)[i];
     101      999450 :         x = left + carry;
     102      999450 :         carry = x < left;
     103      999450 :         ((uint32_t *)a)[i] = x;
     104             :     }
     105             : 
     106    70315620 :     for (i = len / 4 - 1; i >=0; i--)
     107    56252496 :         ((uint32_t *)a)[i] = htonl(((uint32_t *)a)[i]);
     108    14063124 : }
     109             : 
     110             : KRB5_LIB_FUNCTION krb5_error_code KRB5_LIB_CALL
     111     3155128 : _krb5_n_fold(const void *str, size_t len, void *key, size_t size)
     112             : {
     113             :     /* if len < size we need at most N * len bytes, ie < 2 * size;
     114             :        if len > size we need at most 2 * len */
     115     3155128 :     size_t maxlen = 2 * max(size, len);
     116     3155128 :     size_t l = 0;
     117      103346 :     uint8_t *tmp;
     118      103346 :     uint8_t *tmpbuf;
     119      103346 :     uint8_t *buf1;
     120      103346 :     uint8_t *buf2;
     121             : 
     122     3155128 :     tmp = malloc(maxlen + 2 * len);
     123     3155128 :     if (tmp == NULL)
     124           0 :         return ENOMEM;
     125             : 
     126     3155128 :     buf1 = tmp + maxlen;
     127     3155128 :     buf2 = tmp + maxlen + len;
     128             : 
     129     3155128 :     memset(key, 0, size);
     130     3155128 :     memcpy(buf1, str, len);
     131     3155128 :     memcpy(tmp, buf1, len);
     132     1630576 :     do {
     133    49287862 :         l += len;
     134    59842090 :         while(l >= size) {
     135    14063124 :             add1(key, tmp, size);
     136    14063124 :             l -= size;
     137    14063124 :             if(l == 0)
     138     3051782 :                 break;
     139    12538572 :             memmove(tmp, tmp + size, l);
     140             :         }
     141    49287862 :         rr13(tmp + l, buf2, buf1, len * 8);
     142    49287862 :         tmpbuf = buf1;
     143    49287862 :         buf1 = buf2;
     144    49287862 :         buf2 = tmpbuf;
     145    49287862 :     } while(l != 0);
     146             : 
     147     3155128 :     memset(tmp, 0, maxlen + 2 * len);
     148     3155128 :     free(tmp);
     149     3155128 :     return 0;
     150             : }