NetBSD Problem Report #25609

Received: (qmail 5457 invoked by uid 605); 17 May 2004 10:58:03 -0000
Message-Id: <20040517105753.98765B583@linkdead.gangsta.local>
Date: Mon, 17 May 2004 06:57:53 -0400 (EDT)
From: vax@carolina.rr.com
Sender: gnats-bugs-owner@NetBSD.org
Reply-To: vax@carolina.rr.com
To: gnats-bugs@gnats.netbsd.org
Subject: /crypto/des/des badly broken
X-Send-Pr-Version: 3.95

>Number:         25609
>Category:       kern
>Synopsis:       DES's des_set_key sets up bogus key schedule
>Confidential:   no
>Severity:       critical
>Priority:       high
>Responsible:    kern-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon May 17 10:59:00 +0000 2004
>Closed-Date:    
>Last-Modified:  Wed Jun 16 21:42:00 +0000 2004
>Originator:     VaX#n8
>Release:        NetBSD 1.6.2
>Organization:
School of Heart-Knox

>Environment:


>Description:

The key schedule had a field, weak_key, added to it.
The des_set_key_unchecked routine has not been changed to account for it.

I found this because TCFS wouldn't work properly when compiled into the
kernel.  This was a real brain-bender!

>How-To-Repeat:

This code proves it in userland (compile with -I/sys):

#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#include <strings.h>
#include <sys/malloc.h>
#include <crypto/des/des.h>

int main() {
	des_key_schedule ks;
	int i, j;
	const char *kptr = calloc(1, sizeof(des_cblock));
    unsigned char *p;


	des_set_key_unchecked ((des_cblock *)kptr, ks);

for (j = 0; j<(sizeof(des_key_schedule)/sizeof(struct des_ks_struct)); j++) {
	for (i = 0; i < sizeof(des_cblock); i++) printf("%02x", ks[j].ks.cblock[i]);
	printf(", ");
    p = (char *) &ks[j].weak_key;
	for (i = 0; i < sizeof(int); i++) printf("%02x", p[i]);
	printf("\n");
}

	printf("\n");
	bzero(ks, sizeof(des_key_schedule));

	des_set_key_unchecked ((des_cblock *)kptr, ks);

for (j = 0; j<(sizeof(des_key_schedule)/sizeof(struct des_ks_struct)); j++) {
	for (i = 0; i < sizeof(des_cblock); i++) printf("%02x", ks[j].ks.cblock[i]);
	printf(", ");
    p = (char *) &ks[j].weak_key;
	for (i = 0; i < sizeof(int); i++) printf("%02x", p[i]);
	printf("\n");
}

    exit(0);
}

Sample output:

0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 1f000000 /* uninitialized garbage! */
1f000000ecb8bfbf, 00720548
7c85040870aa0408, 07090000
000000002e850408, 58aa0408
40a90408ecb8bfbf, 1f000000
1f000000ecb8bfbf, 98b8bfbf

0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000
0000000000000000, 00000000

>Fix:

TBD.
>Release-Note:
>Audit-Trail:

From: VaX#n8 <vax@carolina.rr.com>
To: gnats-bugs@gnats.netbsd.org
Cc:  
Subject: kern/25609 DES routine fixed
Date: Mon, 17 May 2004 09:27:17 -0400

 I reviewed the latest OpenSSL source, and they do not have a weak_key field
 in the key schedule, so this is a simple fix, just remove that field.
 This field was added in des.h revision 1.5, but is not used anywhere.
 Perhaps a proper fix would be to eliminate the use of pointer arithmetic
 in des_setkey.c:des_set_key_unchecked, depends on if you really wanted to
 do anything with this field.

 However, files created by the TCFS LKM (which has its own, older OpenSSL
 DES routines) are still not readable using the DES routines from the kernel,
 so my investigation is ongoing.  I'm tempted to write a test harness
 to check output against some test vectors or something.

 How is is that I always find brokenness in stuff?  Gift or curse?
 Any employers out there looking for someone with this trait?

 Index: crypto/des/des.h
 ===================================================================
 RCS file: /usr/local/share/cvsroot/NetBSD/sys/crypto/des/des.h,v
 retrieving revision 1.1
 retrieving revision 1.2
 diff -u -r1.1 -r1.2
 --- crypto/des/des.h	8 Apr 2004 17:08:43 -0000	1.1
 +++ crypto/des/des.h	17 May 2004 13:06:52 -0000	1.2
 @@ -67,7 +67,6 @@
  	 * 8 byte longs */
  	DES_LONG deslong[2];
  	} ks;
 -	int weak_key;
  } des_key_schedule[16];

  #define DES_KEY_SZ 	(sizeof(des_cblock))

From: VaX#n8 <vax@carolina.rr.com>
To: gnats-bugs@gnats.netbsd.org
Cc:  
Subject: kern/25609 DES routine fixed
Date: Tue, 18 May 2004 00:21:57 -0400

 There is a library/program called fast-des, and it has a program
 called desvalid and some test vectors called testdata.des which
 came from NIST Special Publication 500-20 "Validating the Correctness
 of Hardware Implementations of the NBS Data Encryption Standard".
 The NetBSD kernel's /crypto/des routines produce the correct data
 after applying the patch in my last email.  The old TCFS routines do not.

 I have included the patch to test them below.

 If could be talked into writing a regression suite for crypto, if I had
 some guidance on how to structure it and make sure it gets into the
 source tree and gets run.  Encrypting you data packets does not do much
 good if your crypto routines produce incorrect data.  And you could be
 in for a nasty surprise if you use it for encrypted storage and upgrade
 to a properly functioning implementation.


 --- desvalid.c.orig	Fri Sep 20 01:55:09 1996
 +++ desvalid.c	Mon May 17 11:04:23 2004
 @@ -10,6 +10,8 @@
  #include <stdio.h>
  #include <string.h>
  #include "des.h"
 +#include <stdlib.h>
 +#include <crypto/des/des.h>

  extern int errno;
  extern int optind;
 @@ -98,7 +100,7 @@
     int	    ch, decr = 0, exitcode = 0;
     char	    *chp;
     int	    keylen;
 -   keyType  key;
 +   des_key_schedule openssl_sched;
     char	    line[LINELEN];
     block    cipher, plain, keystr, wbuf;
     int 	    lineno = 0;
 @@ -122,7 +124,6 @@

     if (argc != 0) goto usage;

 -   key = (keyType) 0;
     keylen = 8;
     do {
        lineno++;
 @@ -139,18 +140,13 @@
  	 continue;
        }

 -      desMakeKey(&key, keystr, keylen, decr);
 -      if (key == (keyType) 0) {
 -	 fprintf(stderr, "%s: couldn't allocate memory for encryption key\n",
 -	    progName);
 -	 return 1;	 
 -      }
 +      des_set_key_unchecked((des_cblock *)&keystr, openssl_sched);

        if (!decr) {
 -	 des(wbuf, plain, key);
 +         des_ecb_encrypt((des_cblock *)plain, (des_cblock *)wbuf, openssl_sched, DES_ENCRYPT);
  	 res = memcmp(wbuf, cipher, 8);
        } else {
 -	 des(wbuf, cipher, key);
 +         des_ecb_encrypt((des_cblock *)cipher, (des_cblock *)wbuf, openssl_sched, DES_DECRYPT);
  	 res = memcmp(wbuf, plain, 8);
        }
        if (res != 0) {
 @@ -176,6 +172,5 @@
        }
     }

 -   free(key);
     return exitcode;
  }

From: VaX#n8 <vax@carolina.rr.com>
To: gnats-bugs@gnats.netbsd.org
Cc:  
Subject: kern/25609 another way to fix DES
Date: Wed, 16 Jun 2004 17:09:31 -0400

 This is another way to fix the DES code.
 I have not tested this.

 Index: des.h
 ===================================================================
 RCS file: /usr/local/share/cvsroot/NetBSD/sys/crypto/des/des.h,v
 retrieving revision 1.2
 diff -u -r1.2 des.h
 --- des.h	17 May 2004 13:06:52 -0000	1.2
 +++ des.h	16 Jun 2004 21:00:46 -0000
 @@ -58,6 +58,9 @@
  /* must be 32bit quantity */
  #define DES_LONG u_int32_t

 +#define ITERATIONS 16 
 +#define HALF_ITERATIONS (ITERATIONS / 2)
 +
  typedef unsigned char des_cblock[8];
  typedef struct des_ks_struct
  	{
 @@ -67,7 +70,7 @@
  	 * 8 byte longs */
  	DES_LONG deslong[2];
  	} ks;
 -} des_key_schedule[16];
 +} des_key_schedule[ITERATIONS];

  #define DES_KEY_SZ 	(sizeof(des_cblock))
  #define DES_SCHEDULE_SZ (sizeof(des_key_schedule))
 Index: des_locl.h
 ===================================================================
 RCS file: /usr/local/share/cvsroot/NetBSD/sys/crypto/des/des_locl.h,v
 retrieving revision 1.1.1.1
 diff -u -r1.1.1.1 des_locl.h
 --- des_locl.h	8 Apr 2004 17:08:43 -0000	1.1.1.1
 +++ des_locl.h	16 Jun 2004 21:00:55 -0000
 @@ -59,9 +59,6 @@
  #undef NOPROTO
  #endif

 -#define ITERATIONS 16
 -#define HALF_ITERATIONS 8
 -
  /* used in des_read and des_write */
  #define MAXWRITE	(1024*16)
  #define BSIZE		(MAXWRITE+4)
 Index: des_setkey.c
 ===================================================================
 RCS file: /usr/local/share/cvsroot/NetBSD/sys/crypto/des/des_setkey.c,v
 retrieving revision 1.1.1.1
 diff -u -r1.1.1.1 des_setkey.c
 --- des_setkey.c	8 Apr 2004 17:08:43 -0000	1.1.1.1
 +++ des_setkey.c	16 Jun 2004 21:04:41 -0000
 @@ -178,10 +178,8 @@
  	static int shifts2[16]={0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0};
  	register DES_LONG c,d,t,s,t2;
  	register const unsigned char *in;
 -	register DES_LONG *k;
  	register int i;

 -	k = &schedule->ks.deslong[0];
  	in = &(*key)[0];

  	c2l(in,c);
 @@ -222,10 +220,10 @@

  		/* table contained 0213 4657 */
  		t2=((t<<16L)|(s&0x0000ffffL))&0xffffffffL;
 -		*(k++)=ROTATE(t2,30)&0xffffffffL;
 +		schedule[i].ks.deslong[0]=ROTATE(t2,30)&0xffffffffL;

  		t2=((s>>16L)|(t&0xffff0000L));
 -		*(k++)=ROTATE(t2,26)&0xffffffffL;
 +		schedule[i].ks.deslong[1]=ROTATE(t2,26)&0xffffffffL;
  	}
  }

>Unformatted:

Home	PR Database Search