openssh unix dev - Jul 2000 - Why do I *still* need RSA?

OpenSSH Developers,

	I'm researching whether or not OpenSSH is a viable commercial
alternative to F-SECURE SSH or SSH.COM's ssh, but I'm not getting the
kind of results that I expected from a "Non patent encumbered ssh
client".

	When I attempt to build OpenSSH against an OpenSSL build without rc5,
idea, or rsa it bombs since OpenSSL doesn't place the header files in
the include dir. Now, that's fine and went away after I copied them to
the appropriate location (hoping that it just *needed* the file, but
that it didn't need any rc5, idea, or rsa functions exported by the
OpenSSL libraries) but it looks like the RSA (aka, non SSH-2.0)
functions are required to have a successful build of OpenSSH.

	Then question now is how OpenBSD is making available a solely SSH 2.0
client/server without RSA, IDEA or RC5. I noticed on the OpenBSD web
site that it became RSA equipped upon the installation of the rsaref
module, but how to I make a system like that under something that isn't
OpenBSD?

	I do not believe that in this stage of the game it is wise for me to go
to RSA Security and get a copy of BSAFE. Not only is it costly, but they
charge an arm and a leg for runtime licensing (not to mention it is sort
of stupid to pay that much money for a package that is not going to be
patent encumbered in 3 months.)

	I'm hoping that somebody can shed some light on build options or
library strategies to make my woes go away.

Thanks,


--
Robbie Stone
Serendipity Simplex

Circa 2000-Jul-19 00:16:01 -0700 dixit Robbie Stone:

: OpenSSH Developers,
: 
: 	I'm researching whether or not OpenSSH is a viable commercial
: alternative to F-SECURE SSH or SSH.COM's ssh, but I'm not getting the
: kind of results that I expected from a "Non patent encumbered ssh
: client".
: 
: 	When I attempt to build OpenSSH against an OpenSSL build without rc5,
: idea, or rsa it bombs since OpenSSL doesn't place the header files in
: the include dir. Now, that's fine and went away after I copied them to
: the appropriate location (hoping that it just *needed* the file, but
: that it didn't need any rc5, idea, or rsa functions exported by the
: OpenSSL libraries)

As of openssl-0.9.5a, if you compile with -DOPENSSL_ALGORITHM_DEFINES
-DOPENSSL_THREAD_DEFINES -DOPENSSL_OTHER_DEFINES, you get all the
definitions that OpenSSL was built with (e.g., NO_IDEA, NO_RC5, etc.).
See opensslconf.h in your installed OpenSSL tree for further info.

That may help things a bit.

-- 
jim knoble | jmknoble at jmknoble.cx | http://www.jmknoble.cx/

On Wed, Jul 19, 2000 at 12:16:01AM -0700, Robbie Stone
wrote:
> 	When I attempt to build OpenSSH against an OpenSSL build without rc5,
> idea, or rsa it bombs since OpenSSL doesn't place the header files in
> the include dir. Now, that's fine and went away after I copied them to
> the appropriate location (hoping that it just *needed* the file, but
> that it didn't need any rc5, idea, or rsa functions exported by the
> OpenSSL libraries) but it looks like the RSA (aka, non SSH-2.0)
> functions are required to have a successful build of OpenSSH.
you still need RSA defines and stub-routines if you want to build
OpenSSH w/o RSA. you can patch OpenSSL with a patch similar to the
attached one. it replaces the RSA function calls with functions returning
error codes. but it should be easy to add dummy functions and struct RSA
defines to OpenSSH and exclude RSA from OpenSSL.
> 	Then question now is how OpenBSD is making available a solely SSH 2.0
> client/server without RSA, IDEA or RC5. I noticed on the OpenBSD web
> site that it became RSA equipped upon the installation of the rsaref
> module, but how to I make a system like that under something that isn't
> OpenBSD?
openbsd ships an openssl libcrypto that includes dummy rsa functions
returning errors if called.

-markus
-------------- next part --------------
diff -u --recursive /usr/src/lib/libssl/src/crypto/rsa/rsa_eay.c
./crypto/rsa/rsa_eay.c
--- /usr/src/lib/libssl/src/crypto/rsa/rsa_eay.c	Tue Apr 11 19:19:52 2000
+++ ./crypto/rsa/rsa_eay.c	Tue Apr 11 19:44:59 2000
@@ -1,13 +1,3 @@
-
-/* This file has been explicitly broken by ryker for OpenBSD, July
- * 1, 1998. In spite of the title, there is no implementation of the
- * RSA algorithm left in this file. All these routines will return an
- * error and fail when called. They exist as stubs and can be
- * ressurected from the bit bucket by someone in the free world once
- * the RSA algorithm is no longer subject to patent problems. Eric
- * Young's original copyright is below. 
- */
-
 /* crypto/rsa/rsa_eay.c */
 /* Copyright (C) 1995-1998 Eric Young (eay at cryptsoft.com)
  * All rights reserved.
@@ -184,13 +174,62 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if ((ctx=BN_CTX_new()) == NULL) goto err;
+	num=BN_num_bytes(rsa->n);
+	if ((buf=(unsigned char *)Malloc(num)) == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
 
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		i=RSA_padding_add_PKCS1_type_1(buf,num,from,flen);
+		break;
+	case RSA_NO_PADDING:
+		i=RSA_padding_add_none(buf,num,from,flen);
+		break;
+	case RSA_SSLV23_PADDING:
+	default:
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (i <= 0) goto err;
+
+	if (BN_bin2bn(buf,num,&f) == NULL) goto err;
+
+	if ((rsa->flags & RSA_FLAG_BLINDING) && (rsa->blinding ==
NULL))
+		RSA_blinding_on(rsa,ctx);
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_convert(&f,rsa->blinding,ctx)) goto err;
+
+	if ( (rsa->flags & RSA_FLAG_EXT_PKEY) ||
+		((rsa->p != NULL) &&
+		(rsa->q != NULL) &&
+		(rsa->dmp1 != NULL) &&
+		(rsa->dmq1 != NULL) &&
+		(rsa->iqmp != NULL)) )
+		{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }
+	else
+		{
+		if
(!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL))
goto err;
+		}
+
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_invert(&ret,rsa->blinding,ctx)) goto err;
+
+	/* put in leading 0 bytes if the number is less than the
+	 * length of the modulus */
+	j=BN_num_bytes(&ret);
+	i=BN_bn2bin(&ret,&(to[num-j]));
+	for (k=0; k<(num-i); k++)
+		to[k]=0;
+
+	r=num;
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
 	BN_clear_free(&ret);
@@ -212,12 +251,77 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
+	ctx=BN_CTX_new();
+	if (ctx == NULL) goto err;
+
+	num=BN_num_bytes(rsa->n);
+
+	if ((buf=(unsigned char *)Malloc(num)) == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
+
+	/* This check was for equality but PGP does evil things
+	 * and chops off the top '0' bytes */
+	if (flen > num)
+		{
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
+		goto err;
+		}
+
+	/* make data into a big number */
+	if (BN_bin2bn(from,(int)flen,&f) == NULL) goto err;
+
+	if ((rsa->flags & RSA_FLAG_BLINDING) && (rsa->blinding ==
NULL))
+		RSA_blinding_on(rsa,ctx);
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_convert(&f,rsa->blinding,ctx)) goto err;
+
+	/* do the decrypt */
+	if ( (rsa->flags & RSA_FLAG_EXT_PKEY) ||
+		((rsa->p != NULL) &&
+		(rsa->q != NULL) &&
+		(rsa->dmp1 != NULL) &&
+		(rsa->dmq1 != NULL) &&
+		(rsa->iqmp != NULL)) )
+		{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }
+	else
+		{
+		if
(!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL))
+			goto err;
+		}
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if (rsa->flags & RSA_FLAG_BLINDING)
+		if (!BN_BLINDING_invert(&ret,rsa->blinding,ctx)) goto err;
+
+	p=buf;
+	j=BN_bn2bin(&ret,p); /* j is only used with no-padding mode */
+
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		r=RSA_padding_check_PKCS1_type_2(to,num,buf,j,num);
+		break;
+#ifndef NO_SHA
+        case RSA_PKCS1_OAEP_PADDING:
+	        r=RSA_padding_check_PKCS1_OAEP(to,num,buf,j,num,NULL,0);
+                break;
+#endif
+ 	case RSA_SSLV23_PADDING:
+		r=RSA_padding_check_SSLv23(to,num,buf,j,num);
+		break;
+	case RSA_NO_PADDING:
+		r=RSA_padding_check_none(to,num,buf,j,num);
+		break;
+	default:
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (r < 0)
+		RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_PADDING_CHECK_FAILED);
 
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
@@ -240,12 +344,56 @@
 	unsigned char *buf=NULL;
 	BN_CTX *ctx=NULL;
 
-        BN_init(&f);
-        BN_init(&ret);
+	BN_init(&f);
+	BN_init(&ret);
+	ctx=BN_CTX_new();
+	if (ctx == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	num=BN_num_bytes(rsa->n);
+	buf=(unsigned char *)Malloc(num);
+	if (buf == NULL)
+		{
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
+
+	/* This check was for equality but PGP does evil things
+	 * and chops off the top '0' bytes */
+	if (flen > num)
+		{
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
+		goto err;
+		}
+
+	if (BN_bin2bn(from,flen,&f) == NULL) goto err;
+	/* do the decrypt */
+	if ((rsa->_method_mod_n == NULL) && (rsa->flags &
RSA_FLAG_CACHE_PUBLIC))
+		{
+		if ((rsa->_method_mod_n=BN_MONT_CTX_new()) != NULL)
+			if (!BN_MONT_CTX_set(rsa->_method_mod_n,rsa->n,ctx))
+			    goto err;
+		}
+
+	if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->e,rsa->n,ctx,
+		rsa->_method_mod_n)) goto err;
+
+	p=buf;
+	i=BN_bn2bin(&ret,p);
+
+	switch (padding)
+		{
+	case RSA_PKCS1_PADDING:
+		r=RSA_padding_check_PKCS1_type_1(to,num,buf,i,num);
+		break;
+	case RSA_NO_PADDING:
+		r=RSA_padding_check_none(to,num,buf,i,num);
+		break;
+	default:
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
+		goto err;
+		}
+	if (r < 0)
+		RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_PADDING_CHECK_FAILED);
 
 err:
 	if (ctx != NULL) BN_CTX_free(ctx);
@@ -263,15 +411,59 @@
 	{
 	BIGNUM r1,m1;
 	int ret=0;
-	BN_CTX *ctx = NULL;
+	BN_CTX *ctx;
 
+	if ((ctx=BN_CTX_new()) == NULL) goto err;
 	BN_init(&m1);
 	BN_init(&r1);
-	if ((ctx=BN_CTX_new()) == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	if (rsa->flags & RSA_FLAG_CACHE_PRIVATE)
+		{
+		if (rsa->_method_mod_p == NULL)
+			{
+			if ((rsa->_method_mod_p=BN_MONT_CTX_new()) != NULL)
+				if (!BN_MONT_CTX_set(rsa->_method_mod_p,rsa->p,
+						     ctx))
+					goto err;
+			}
+		if (rsa->_method_mod_q == NULL)
+			{
+			if ((rsa->_method_mod_q=BN_MONT_CTX_new()) != NULL)
+				if (!BN_MONT_CTX_set(rsa->_method_mod_q,rsa->q,
+						     ctx))
+					goto err;
+			}
+		}
+
+	if (!BN_mod(&r1,I,rsa->q,ctx)) goto err;
+	if (!rsa->meth->bn_mod_exp(&m1,&r1,rsa->dmq1,rsa->q,ctx,
+		rsa->_method_mod_q)) goto err;
+
+	if (!BN_mod(&r1,I,rsa->p,ctx)) goto err;
+	if (!rsa->meth->bn_mod_exp(r0,&r1,rsa->dmp1,rsa->p,ctx,
+		rsa->_method_mod_p)) goto err;
+
+	if (!BN_sub(r0,r0,&m1)) goto err;
+	/* This will help stop the size of r0 increasing, which does
+	 * affect the multiply if it optimised for a power of 2 size */
+	if (r0->neg)
+		if (!BN_add(r0,r0,rsa->p)) goto err;
+
+	if (!BN_mul(&r1,r0,rsa->iqmp,ctx)) goto err;
+	if (!BN_mod(r0,&r1,rsa->p,ctx)) goto err;
+	/* If p < q it is occasionally possible for the correction of
+         * adding 'p' if r0 is negative above to leave the result still
+	 * negative. This can break the private key operations: the following
+	 * second correction should *always* correct this rare occurrence.
+	 * This will *never* happen with OpenSSL generated keys because
+         * they ensure p > q [steve]
+         */
+	if (r0->neg)
+		if (!BN_add(r0,r0,rsa->p)) goto err;
+	if (!BN_mul(&r1,r0,rsa->q,ctx)) goto err;
+	if (!BN_add(r0,&r1,&m1)) goto err;
+
+	ret=1;
 err:
 	BN_clear_free(&m1);
 	BN_clear_free(&r1);
diff -u --recursive /usr/src/lib/libssl/src/crypto/rsa/rsa_gen.c
./crypto/rsa/rsa_gen.c
--- /usr/src/lib/libssl/src/crypto/rsa/rsa_gen.c	Sun Mar 19 04:11:39 2000
+++ ./crypto/rsa/rsa_gen.c	Tue Apr 11 19:44:59 2000
@@ -74,11 +74,108 @@
 	if (ctx == NULL) goto err;
 	ctx2=BN_CTX_new();
 	if (ctx2 == NULL) goto err;
+	BN_CTX_start(ctx);
+	r0 = BN_CTX_get(ctx);
+	r1 = BN_CTX_get(ctx);
+	r2 = BN_CTX_get(ctx);
+	r3 = BN_CTX_get(ctx);
+	if (r3 == NULL) goto err;
 
-	/* Body of this routine removed for OpenBSD - will return
-	 * when the RSA patent expires
-	 */
+	bitsp=(bits+1)/2;
+	bitsq=bits-bitsp;
+	rsa=RSA_new();
+	if (rsa == NULL) goto err;
 
+	/* set e */ 
+	rsa->e=BN_new();
+	if (rsa->e == NULL) goto err;
+
+#if 1
+	/* The problem is when building with 8, 16, or 32 BN_ULONG,
+	 * unsigned long can be larger */
+	for (i=0; i<sizeof(unsigned long)*8; i++)
+		{
+		if (e_value & (1<<i))
+			BN_set_bit(rsa->e,i);
+		}
+#else
+	if (!BN_set_word(rsa->e,e_value)) goto err;
+#endif
+
+	/* generate p and q */
+	for (;;)
+		{
+		rsa->p=BN_generate_prime(NULL,bitsp,0,NULL,NULL,callback,cb_arg);
+		if (rsa->p == NULL) goto err;
+		if (!BN_sub(r2,rsa->p,BN_value_one())) goto err;
+		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;
+		if (BN_is_one(r1)) break;
+		if (callback != NULL) callback(2,n++,cb_arg);
+		BN_free(rsa->p);
+		}
+	if (callback != NULL) callback(3,0,cb_arg);
+	for (;;)
+		{
+		rsa->q=BN_generate_prime(NULL,bitsq,0,NULL,NULL,callback,cb_arg);
+		if (rsa->q == NULL) goto err;
+		if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;
+		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;
+		if (BN_is_one(r1) && (BN_cmp(rsa->p,rsa->q) != 0))
+			break;
+		if (callback != NULL) callback(2,n++,cb_arg);
+		BN_free(rsa->q);
+		}
+	if (callback != NULL) callback(3,1,cb_arg);
+	if (BN_cmp(rsa->p,rsa->q) < 0)
+		{
+		tmp=rsa->p;
+		rsa->p=rsa->q;
+		rsa->q=tmp;
+		}
+
+	/* calculate n */
+	rsa->n=BN_new();
+	if (rsa->n == NULL) goto err;
+	if (!BN_mul(rsa->n,rsa->p,rsa->q,ctx)) goto err;
+
+	/* calculate d */
+	if (!BN_sub(r1,rsa->p,BN_value_one())) goto err;	/* p-1 */
+	if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;	/* q-1 */
+	if (!BN_mul(r0,r1,r2,ctx)) goto err;	/* (p-1)(q-1) */
+
+/* should not be needed, since gcd(p-1,e) == 1 and gcd(q-1,e) == 1 */
+/*	for (;;)
+		{
+		if (!BN_gcd(r3,r0,rsa->e,ctx)) goto err;
+		if (BN_is_one(r3)) break;
+
+		if (1)
+			{
+			if (!BN_add_word(rsa->e,2L)) goto err;
+			continue;
+			}
+		RSAerr(RSA_F_RSA_GENERATE_KEY,RSA_R_BAD_E_VALUE);
+		goto err;
+		}
+*/
+	rsa->d=BN_mod_inverse(NULL,rsa->e,r0,ctx2);	/* d */
+	if (rsa->d == NULL) goto err;
+
+	/* calculate d mod (p-1) */
+	rsa->dmp1=BN_new();
+	if (rsa->dmp1 == NULL) goto err;
+	if (!BN_mod(rsa->dmp1,rsa->d,r1,ctx)) goto err;
+
+	/* calculate d mod (q-1) */
+	rsa->dmq1=BN_new();
+	if (rsa->dmq1 == NULL) goto err;
+	if (!BN_mod(rsa->dmq1,rsa->d,r2,ctx)) goto err;
+
+	/* calculate inverse of q mod p */
+	rsa->iqmp=BN_mod_inverse(NULL,rsa->q,rsa->p,ctx2);
+	if (rsa->iqmp == NULL) goto err;
+
+	ok=1;
 err:
 	if (ok == -1)
 		{