Hi Dave,
Thanks for your reply. I've attached a simple console app that attempts to
import the key data into a .NET RSACryptoServiceProvider. Internally this class
just sends it straight onto the Windows OS crypto library, which includes the
checks that P and Q must have equal lengths. The code includes a
ValidateParameters method that has the same checks that Windows internally uses
to determine whether it is Bad Data or not.
It would seem that your certificate test that you ran (and thank you very much
for the time you took trying it out!) might have somehow bypassed the test of
lengths. Whether that can somehow be leveraged in a .NET app and used for both
encryption and authentication is (for me) the ultimate question.
Sent from Surface Pro
From: Dave Thompson
Sent: Friday, March 21, 2014 3:37 PM
To: openssl-users@openssl.org
To be clear: it is conventional to generate P with a larger *value* than Q, AIR
so that
CRT qinv-modp works right. There are several ways to do this; openssl just
generates
two suitable primes and chooses the larger one as P. Your issue is that P has
*more
significant bits*, 257 instead of 256.
I don’t think this violates any standard and it works fine on my Windows (which
is 7).
I took your privatekey, which is indeed PKCS#1, generated a (fake) cert, put
them in a PKCS12,
which Windows imported okay and IE(9) was then able to use to authenticate to
my test server (which trusts the fake cert). Where are you seeing the “Bad
Data”?
AIVR there is an attack on RSA if the two primes are *very* close (maybe
something
like 256-bit primes within 2^64 or so). It’s conceivable that iOS went *way*
overboard
in avoiding that weakness. AFAICS openssl doesn’t even check, apparently
relying on
the fact the primes chosen independently in 2^(n-1) to 2^n are overwhelming
unlikely
to be too close – probably less likely than your computer turning into cottage
cheese
during the key generation process.
From: owner-openssl-us...@openssl.org [mailto:owner-openssl-us...@openssl.org]
On Behalf Of Andrew Arnott
Sent: Friday, March 21, 2014 01:32
To: openssl-users@openssl.org
Subject: *** Spam *** When P is larger than Q
I've noticed that iOS RSA keys (which I believe are generated using openssl
underneath it all) are created with P larger than Q, which is posing a problem
for me.
When I export the 512-bit private key from iOS, I get a PKCS#1 formatted key.
When I decode that into RSAParameters, I see that P and Q are of unequal size
(Q is 32 bytes and P is 33). This makes Windows reject it as Bad Data, since it
is expecting both P and Q to be exactly half the length of the modulus. Note
that the extra byte is not a leading (or trailing) zero. The first byte is a 1.
And that 1 is significant. I verified that p*q=mod when p includes the leading
1. So I’m a little dumbfounded that iOS would produce a key where p is longer
than q, particularly since Windows seems to disallow that. Given this, I don’t
know how to pass a private key from iOS to Windows.
I'm wondering whether P is supposed to be larger than Q, if there is something
I can do to suppress that when generating keys, or if there's anything I can do
to coerce them to be the same length later. I tried just padding Q with a
leading 0, and then padding the modulus as well since it's supposed to be twice
the length of P and Q, but that led to encryption that had leading zeros in the
ciphertext and decryption failed.
Thanks.
Any ideas? One specific 512-bit key I generated as part of a test is below,
with all the variables I decoded from it, in big endian.
* Raw private key data exported from iOS (believed to be PKCS#1
format): MIIBOgIBAAJBALx0Z0O1n/2E+
Boyt7UEIQD62y8MQQPILJC2AguHvPfo8E5ScBBPa8dMCHVRCcKJJ868F
JdebracYthqCHn19KMCAwEAAQJBAKAgsFXCD+2UfFOWYK44keqJPJBfcybJgcR8QoSVk6V40MkwgAm
jVn4cumCLZgxwJ+O5fbS/xmzeRSBz8gdPfrECIQGbqLr8paSZLW80ixXQK9YCx76nkg4I2UdBq+h5taAwn
QIgdTHt32eGkYjiVT81BnM6D9pmX508VulYsBalYtbmlj8CIEYX4dbZAYDPeqrwr8MlY6hPiIgR12/sRzTIZ6
opoeAFAiAtESA6UuNKv+rZgU7wxgrD4eaQSjTT7zPtsyeyVJWjnQIhAONhytT6rHH9n3nE4K7Xxz3DjYodX
zzM6Bm2C1jiGrEM
*
Modulus:
vHRnQ7Wf/YT4GjK3tQQhAPrbLwxBA8gskLYCC4e89+jwTlJwEE9rx0wIdVEJwoknzrwUl15utpxi2GoIefX0ow==
Exponent: AQAB
D:
oCCwVcIP7ZR8U5ZgrjiR6ok8kF9zJsmBxHxChJWTpXjQyTCACaNWfhy6YItmDHAn47l9tL/GbN5FIHPyB09+sQ==
P: AZuouvylpJktbzSLFdAr1gLHvqeSDgjZR0Gr6Hm1oDCd
DP: Rhfh1tkBgM96qvCvwyVjqE+IiBHXb+xHNMhnqimh4AU=
DQ: LREgOlLjSr/q2YFO8MYKw+HmkEo00+8z7bMnslSVo50=
Q: dTHt32eGkYjiVT81BnM6D9pmX508VulYsBalYtbmlj8=
InverseQ: 42HK1Pqscf2fecTgrtfHPcONih1fPMzoGbYLWOIasQw=
--
Andrew Arnott
"I [may] not agree with what you have to say, but I'll defend to the death your
right to say it." - S. G. Tallentyre
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
using Validation;
namespace ConsoleApplication3
{
static class Program
{
/*
* Big Endian 4 3 2 1 RSAParameters; aka 'network byte order'
* Little Endian 1 2 3 4 WINDOWS, .NET BigInteger
*
* Raw private key data exported from iOS (believed to be PKCS#1
format):
MIIBOgIBAAJBALx0Z0O1n/2E+Boyt7UEIQD62y8MQQPILJC2AguHvPfo8E5ScBBPa8dMCHVRCcKJJ868FJdebracYthqCHn19KMCAwEAAQJBAKAgsFXCD+2UfFOWYK44keqJPJBfcybJgcR8QoSVk6V40MkwgAmjVn4cumCLZgxwJ+O5fbS/xmzeRSBz8gdPfrECIQGbqLr8paSZLW80ixXQK9YCx76nkg4I2UdBq+h5taAwnQIgdTHt32eGkYjiVT81BnM6D9pmX508VulYsBalYtbmlj8CIEYX4dbZAYDPeqrwr8MlY6hPiIgR12/sRzTIZ6opoeAFAiAtESA6UuNKv+rZgU7wxgrD4eaQSjTT7zPtsyeyVJWjnQIhAONhytT6rHH9n3nE4K7Xxz3DjYodXzzM6Bm2C1jiGrEM
*
Modulus:
vHRnQ7Wf/YT4GjK3tQQhAPrbLwxBA8gskLYCC4e89+jwTlJwEE9rx0wIdVEJwoknzrwUl15utpxi2GoIefX0ow==
Exponent: AQAB
D:
oCCwVcIP7ZR8U5ZgrjiR6ok8kF9zJsmBxHxChJWTpXjQyTCACaNWfhy6YItmDHAn47l9tL/GbN5FIHPyB09+sQ==
P: AZuouvylpJktbzSLFdAr1gLHvqeSDgjZR0Gr6Hm1oDCd
DP: Rhfh1tkBgM96qvCvwyVjqE+IiBHXb+xHNMhnqimh4AU=
DQ: LREgOlLjSr/q2YFO8MYKw+HmkEo00+8z7bMnslSVo50=
Q: dTHt32eGkYjiVT81BnM6D9pmX508VulYsBalYtbmlj8=
InverseQ: 42HK1Pqscf2fecTgrtfHPcONih1fPMzoGbYLWOIasQw=
*
*/
/// <summary>
/// Mains the specified arguments.
/// </summary>
/// <param name="args">The arguments.</param>
static void Main(string[] args)
{
var parameters = new RSAParameters
{
Modulus =
TrimLeadingZero(Convert.FromBase64String("vHRnQ7Wf/YT4GjK3tQQhAPrbLwxBA8gskLYCC4e89+jwTlJwEE9rx0wIdVEJwoknzrwUl15utpxi2GoIefX0ow==")),
Exponent = TrimLeadingZero(Convert.FromBase64String("AQAB")),
D =
TrimLeadingZero(Convert.FromBase64String("oCCwVcIP7ZR8U5ZgrjiR6ok8kF9zJsmBxHxChJWTpXjQyTCACaNWfhy6YItmDHAn47l9tL/GbN5FIHPyB09+sQ==")),
P =
TrimLeadingZero(Convert.FromBase64String("AZuouvylpJktbzSLFdAr1gLHvqeSDgjZR0Gr6Hm1oDCd")),
DP =
TrimLeadingZero(Convert.FromBase64String("Rhfh1tkBgM96qvCvwyVjqE+IiBHXb+xHNMhnqimh4AU=")),
DQ =
TrimLeadingZero(Convert.FromBase64String("LREgOlLjSr/q2YFO8MYKw+HmkEo00+8z7bMnslSVo50=")),
Q =
TrimLeadingZero(Convert.FromBase64String("dTHt32eGkYjiVT81BnM6D9pmX508VulYsBalYtbmlj8=")),
InverseQ =
TrimLeadingZero(Convert.FromBase64String("42HK1Pqscf2fecTgrtfHPcONih1fPMzoGbYLWOIasQw=")),
};
//parameters.Modulus =
EnsureLengthByAddingLeadingZeros(parameters.Modulus, parameters.P.Length * 2-1);
//parameters.D = EnsureLengthByAddingLeadingZeros(parameters.D,
parameters.Modulus.Length);
//parameters.DP = EnsureLengthByAddingLeadingZeros(parameters.DP,
parameters.P.Length);
//parameters.DQ = EnsureLengthByAddingLeadingZeros(parameters.DQ,
parameters.P.Length);
//parameters.Q = EnsureLengthByAddingLeadingZeros(parameters.Q,
parameters.P.Length);
//parameters.InverseQ =
EnsureLengthByAddingLeadingZeros(parameters.InverseQ, parameters.P.Length);
var p = FromBigEndian(parameters.P);
var q = FromBigEndian(parameters.Q);
var mod = p * q;
if (mod == FromBigEndian(parameters.Modulus))
{
Console.WriteLine("Looks good");
}
ValidateParameters(parameters);
var rsa = new RSACryptoServiceProvider(512);
//var goodParameters = rsa.ExportParameters(true);
//ValidateParameters(goodParameters);
var publicParameters = new RSAParameters
{
Exponent = parameters.Exponent,
Modulus = parameters.Modulus,
};
rsa.ImportParameters(publicParameters);
byte[] ciphertext = rsa.Encrypt(new byte[] { 1, 2, 3 }, true);
// This throws Bad Data, because P and Q have unequal significant
bits.
rsa.ImportParameters(parameters);
//rsa.ExportCspBlob(true);
//var exportedParameters = rsa.ExportParameters(true);
byte[] plaintext = rsa.Decrypt(ciphertext, true);
}
private static void ValidateParameters(RSAParameters parameters)
{
int cbHalfModulus = (parameters.Modulus.Length + 1) / 2;
if (parameters.P.Length != cbHalfModulus ||
parameters.Q.Length != cbHalfModulus ||
parameters.DP.Length != cbHalfModulus ||
parameters.DQ.Length != cbHalfModulus ||
parameters.InverseQ.Length != cbHalfModulus ||
parameters.D.Length != parameters.Modulus.Length)
{
Console.WriteLine("Bad data");
}
}
public static BigInteger FromBase64(string base64)
{
byte[] p = Convert.FromBase64String(base64).Reverse().ToArray();
return FromBigEndian(p);
}
public static BigInteger FromBigEndian(byte[] input)
{
byte[] p = new byte[input.Length];
Array.Copy(input, p, input.Length);
Array.Reverse(p);
if (p[p.Length - 1] > 127)
{
Array.Resize(ref p, p.Length + 1);
p[p.Length - 1] = 0;
}
return new BigInteger(p);
}
/// <summary>
/// Trims up to one leading byte from the start of a buffer if that
byte is a 0x00
/// without modifying the original buffer.
/// </summary>
/// <param name="buffer">The buffer.</param>
/// <returns>A buffer without a leading zero. It may be the same buffer
as was provided if no leading zero was found.</returns>
internal static byte[] TrimLeadingZero(byte[] buffer)
{
if (buffer.Length > 0 && buffer[0] == 0)
{
byte[] trimmed = new byte[buffer.Length - 1];
Buffer.BlockCopy(buffer, 1, trimmed, 0, trimmed.Length);
return trimmed;
}
return buffer;
}
internal static byte[] EnsureLengthByAddingLeadingZeros(byte[] buffer,
int length)
{
if (buffer.Length < length)
{
byte[] larger = new byte[length];
Buffer.BlockCopy(buffer, 0, larger, length - buffer.Length,
buffer.Length);
return larger;
}
return buffer;
}
}
}