Cryptographic puzzle: import of a key of WebMoney in Crypto Service Provider

Private keys in the Windows system are usually stored in a special keystore. Work with these keys occurs by calling the functions of the cryptographic provider (hereinafter referred to as CSP). When using the standard CSP (Microsoft Base Cryptographic Provider), the user's keys are stored in the C: \ Users \ [Vasia] \ AppData \ Roaming \ Microsoft \ Crypto folder. When using special devices, the keys are stored in the memory of the device itself.

To increase security, it was decided to import the key WebMoney (the same .kwm, which sign requests to the interfaces) in the CSP. Usually, those who use the key to sign requests to WM interfaces store it either as a .kwm file in the file system, or as an xml view — both are not very secure.

It turned out not so easy.
')
In detail about the problems that you will encounter, while increasing the security of your payment service, read under the cut.



So. Let's start with the kwm file format. The file has a non-intricate format (little things are missing):

1. Hash to verify integrity.
2. Encrypted private RSA exhibitor (D).
H. Encrypted RSA-module (Modulus).

Problem number 1: after decrypting the key file, we get only 2 of the 8 parameters we need.

We have: D and Modulus, we need: Exponent, Modulus, P, Q, DP, DQ, InverseQ, D (for details on the structure to which you need to bring the key to import into CSP, see MSDN msdn.microsoft.com/en- us / library / Aa387401 ).

If you knew E (open exponent), it would not be difficult to find all these parameters. Usually E take one of the numbers Farm: 17, 257, 65537 or 4294967297. The check is very simple:

1. Encrypt an arbitrary message by our parameters D and Modulus:

encrypted = message^D % Modulus


2. We are trying to decrypt using Exponent (assumed) and Modulus:

message = encrypted^Exponent % Modulus


If the message received after decryption coincided with the original, then Exponent was selected correctly.

Note: hereinafter, the operator "^" is exponentiation, and the operator "%" is the remainder of the division .

Problem number 2: the open exhibitor is not known to us, and it is quite large.

Unfortunately, none of these numbers Farm did not fit as an open exponent. This is a bit upsetting. Further, hoping that this number is still not too large - all numbers less than 4 bytes were tried (by brute force). None of them fit. It seems to be a dead end and it would be possible to forget about this idea ...

This could all end. It was not possible to get an open exhibitor: to brute force it for several dozen (or even hundreds) years.

However, the story continues. There lived a man like Michael J. Wiener who came up with a way to break into the RSA system, in the case of a small value of d. We have a little the opposite: the small value of the open exponent, which we do not know.

Indeed, by applying Wiener's attack on RSA, you can almost instantly find the open exponent of any key (if it is not very long).

Here's what happened:

Original values ​​of D and Modulus (obtained from the kwm file):

D: 19715AB67A97257C5C80C8CD8F97448199F6F3FF8A3724DEA911C32CB5E64395D3175D6112A51DC14911FBA4E8FD107C1C65BE062A3491B1131168DF423408E2593

Modulus: 789BE5F2D0C90430EAEFC640B752FE707D75EB12C9C76F776C981014C1825C48989F15F5F53AFBF9B9C11D5C9AF184CC4F3938A48045414F814636C1275321F3AB9


An open exhibitor that was instantly restored using Wiener's attack on RSA:

Exponent: 21EA463DEB0B


It seemed to be the case: to bring the received parameters to the Private Key BLOBs structure and import into any crypto provider. But it's not so easy ...

Problem number 3: a public exponent is longer than 4 bytes, and the Private Key BLOBs format only allows exhibitors up to 4 bytes in length (4 bytes inclusive).

That is the trouble! It would seem that the task has no solution and you can forget about it (for the second time).

Although ... After all, we have cryptosystem parameters (in particular, prime numbers p and q). Therefore, you can do this:

1. Take the original parameters P and Q.

2. Choose the appropriate Exponent2 public exponent (no more than 4 bytes). Take the number Farm 65537.

3. Calculate the closed exponent D2 (multiplicatively inverse to the number e modulo (P-1) *
(Q-1)). D2 will be different from the original D from the kwm file.

4. Calculate the parameters: DP2, DQ2, InverseQ2. They are needed to quickly obtain a signature, using the Chinese theorem on residuals .

5. The most important thing! We calculate the difference between the original D (which is in the original key kwm) and D2 of our modified cryptosystem (ie, D2 - D).

Now the modified key can be saved in the CSP storage (for example, eToken PRO) as a private RSA key, and the deviation can be saved as a PKCS # 11 object. When using Microsoft CSP, deviation can be saved to the user's store.

In principle, the deviation value is not secret, now our modified key (which is stored in the CSP) is secret.

Here is an example in C # that is responsible for importing the modified key into the CSP:

public void ImportPrivateKey( byte [] modulusBytes, byte [] privateExponentBytes)
{
//

var modulus = new BigInteger(modulusBytes);
var d = new BigInteger(privateExponentBytes);

var p = Wiener.Calculate(d, modulus); // RSA P ( )
var q = modulus/p;
var f = (p - 1)*(q - 1); //
var e = new BigInteger( new byte [] {1, 0, 1}); // 65537

var d2 = e.modInverse(f); // d2 --

var dp2 = d2%(p - 1);
var dq2 = d2%(q - 1);
var iq = q.modInverse(p);

var rsaParameters = new RSAParameters
{
D = toByteArray(d2),
DP = toByteArray(dp2),
DQ = toByteArray(dq2),
Exponent = toByteArray(e),
InverseQ = toByteArray(iq),
Modulus = toByteArray(modulus),
P = toByteArray(p),
Q = toByteArray(q)
};

BigInteger deviation;
byte flag; // d > d2,

if (d > d2)
{
deviation = d - d2;
flag = 0;
}
else
{
deviation = d2 - d;
flag = 1;
}

// CSP ( eToken, CSP "eToken Base Cryptographic Provider")
var cspParameters = new CspParameters
{
Flags =
CspProviderFlags.UseNonExportableKey | CspProviderFlags.UseUserProtectedKey,
KeyNumber = ( int )KeyNumber.Exchange,
KeyContainerName = _containerName
};

//
RSACryptoServiceProvider.UseMachineKeyStore = false ;

using ( var cryptoServiceProvider = new RSACryptoServiceProvider(cspParameters))
{
//
cryptoServiceProvider.ImportParameters(rsaParameters);
}

// deviation ( )
Storage.SaveDataInStorage(_containerName, toByteArray(deviation));
Storage.SaveDataInStorage(_containerName + "_flag" , new [] {flag});
}

* This source code was highlighted with Source Code Highlighter .

How now to receive the message signature message?

The original signature is obtained as follows:

signature = hash ^ D % Modulus


We now have no D, but there is D2 and deviation, and D2 + deviation = D. There is no direct access to D2, since it is run by CSP: you can only get the signature of this D2, by calling standard functions. Remember algebra:

a^(b+c) = a^b * a^c


This law also applies to modular algebra. So, our original signature (without knowledge D) is this:

part1 = hash ^ D2 % Modulus

part2 = hash ^ deviation % Modulus

signature = part1 * part2 % Modulus


Profit! Now our key is run by CSP (in the case of a hardware device, this is pretty reliable). A little trouble - the whole “did not fit together”, there was still a “piece” in the form of deviation. But this deviation is not a secret; without the knowledge of D2, it practically does not introduce any clue about the original D.

But do not rush to relax.

Problem number 4: the structure of the signed data is different from the generally accepted.

If you decrypt the signature obtained by means of Win CAPI (you can decrypt the public exponent and module), you will see something like this structure:

1FFFFFFFFFFFFFFFFFFFFFFFF003031300D0609608648016503040201050004209F64A747E1B97F131FABB6B447296C9B6F0201E79FB3C5356E6C77E89B6A806


at the beginning of the standard header, and at the end of 32 bytes of the hash of the message being signed (cited for SHA-256).

The WebMoney Signer signature is different: the first bytes are filled with random numbers, then 16 bytes of the MD4 hash, then a header of 2 bytes.

The problem is that the CSP does not support the direct function of modular exponentiation with a private key (if it were possible, everything would work out). Allowed only:

1. Sign the message. In an explicit form does not suit us, because WebMoney will not recognize our signature - because the structure is different.

2. Encrypt the message. Again - a kind of encryption (the original message is modified, supplemented by random numbers) - it does not agree with our format.

Again a deadlock. Although ... And what if you slip our CSP is not a real hash, but a pseudo-hash, in which we fit the data in the format we need? The hash function is not reversible, so there is not a single way to check if the hash is real.

To do this, we need to choose an algorithm that has a long enough hash: so that our 16 byte MD4 contains, and a 2-byte header, and it would be nice for security to supplement the data with random numbers.

SHA-512 was too big, but SHA-256 just right.

This is the function for generating a signature:

public string Sign( string value )
{
if ( string .IsNullOrEmpty( value ))
throw new ArgumentNullException( "value" );

var toSign = new byte [32]; // - SHA256

var random = new byte [14]; //
var hash = getHash( value ); // MD4
var prefix = new byte [] {0, 56}; // WebMoney

var rngCryptoServiceProvider = new RNGCryptoServiceProvider();
rngCryptoServiceProvider.GetBytes(random);

Buffer.BlockCopy(random, 0, toSign, 0, random.Length);
Buffer.BlockCopy(hash, 0, toSign, random.Length, hash.Length);
Buffer.BlockCopy(prefix, 0, toSign, random.Length + hash.Length, prefix.Length);

var cspParameters = new CspParameters
{
Flags =
CspProviderFlags.UseNonExportableKey | CspProviderFlags.UseUserProtectedKey,
KeyNumber = ( int ) KeyNumber.Exchange,
KeyContainerName = _containerName
};

byte [] signature1;
BigInteger modulus;

using ( var rsaCryptoServiceProvider = new RSACryptoServiceProvider(528, cspParameters))
{
signature1 = rsaCryptoServiceProvider.SignHash(toSign, CryptoConfig.MapNameToOID( "SHA256" ));
modulus = new BigInteger(rsaCryptoServiceProvider.ExportParameters( false ).Modulus);
}

var deviation = new BigInteger(Storage.LoadDataFromStorage(_containerName));

// SHA-256
var header = new byte []
{
0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00,
0x30,
0x31, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01,
0x05,
0x00, 0x04, 0x20
};

var toEncrypt = new byte [65];

Buffer.BlockCopy(header, 0, toEncrypt, 0, header.Length);
Buffer.BlockCopy(random, 0, toEncrypt, header.Length, random.Length);
Buffer.BlockCopy(hash, 0, toEncrypt, header.Length + random.Length, hash.Length);
Buffer.BlockCopy(prefix, 0, toEncrypt, header.Length + random.Length + hash.Length, prefix.Length);

byte flag = Storage.LoadDataFromStorage(_containerName + "_flag" )[0];

var part1 = new BigInteger(signature1);
BigInteger part2;

if (1 == flag)
{
// -- --
part2 = new BigInteger(toEncrypt).modInverse(modulus).modPow(deviation, modulus);
}
else
part2 = new BigInteger(toEncrypt).modPow(deviation, modulus);

var signature = toByteArray((part1*part2)%modulus);

// little-endian
Array.Reverse(signature);

//
var uResult = new ushort [KeyBytesLength/2];

Buffer.BlockCopy(signature, 0, uResult, 0, signature.Length);

var stringBuilder = new StringBuilder ();

for ( int pos = 0; pos < uResult.Length; pos++)
stringBuilder.Append( string .Format(CultureInfo.InvariantCulture, "{0:x4}" , uResult[pos]));

return stringBuilder.ToString();
}

* This source code was highlighted with Source Code Highlighter .

Now everything works like a clock: the key is compatible with any cryptographic device running on a Windows system (aka eToken, ruToken - whatever), the signature is valid.

PS
From the author.

It may be difficult for someone to understand why I did not choose the “easy way”. I explain: I love cryptographic puzzles. Some people solve scanwords, but I like puzzles more like this.