Import Substitution in I2P: Signature in accordance with GOST R 34.10-2012
Elliptical cryptography, possessing high resilience and high prevalence, has always caused a lot of controversy and speculation about possible bookmarks for different curves and signature schemes. At the same time, no one could give an example of such a bookmark or prove their absence. Therefore, in contrast to symmetric cryptography, where leadership unconditionally belongs to AES, asymmetric cryptography is used of different types, depending on preferences, technical or legal requirements. Additional types of address signatures in I2P provide more choice and flexibility for applications. GOST is supported in openssl via the EVP interface, but in version 1.1 it is excluded from the standard delivery, in addition the existing implementation assumes the storage and transmission of public keys and signatures in DER format, and I2P works directly with numbers, determining the necessary parameters from the signature type.
There are currently 9 types of signatures in I2P, where the type of signature is indicated, then the type of hash and, if necessary, the curve or its set of parameters.
Also, old addresses use type 0 - DSA_SHA1, which is considered obsolete.
It is recommended to use types 1 and 7.
For GOST, we, at my request, have two types:
9 - GOSTR3410_GOSTR3411_256_CRYPTO_PRO_A
10 - GOSTR3410_GOSTR3411_512_TC26_A
for 256 and 512-bit keys, respectively.
')
The length of the public key for 9 is 64 bytes (32 bytes for each coordinate of the point) and 128 bytes for 10.
It is assumed that a hash of 256 or 512 bits is signed and verified. Detailed and with examples described here .
The usual elliptic curve is used, so functions from the cryptographic library can be used to work with it. In particular, it is EC_GROUP_ * and EC_POINT_ * from openssl, the main of which is:
used for both multiplying a base point by a number, or an arbitrary point, depending on the parameters.
For a curve, 6 parameters are specified: p is the modulus, a and b are the coefficients of the curve equation, P (x, y) is the base point, q is a prime number, multiplying by which the base point gives zero.
p and q should be large and close to the maximum, because p limits the range of all numbers, and q - the range of secret keys. The base point and q are calculated simultaneously.
As a rule, well-known and well-tested parameter sets are used.
In our implementation, we will use 2 sets of parameters:
Unlike the curve, the signature scheme in GOST is its own, therefore the ECDSA_sign and ECDSA_verify functions cannot be used and you should implement a signature and signature verification in your code.
For the signature (r, s), a random number k is selected, and the point R = k * P is calculated, the x coordinate of which becomes the signature component r. Component s = r * d + h * k, where d is the secret key, h is the hash of the message signature in Big Endian.
To verify the signature, multiply both sides of the equality by the base point P.
Indeed, s * P = r * d * P + h * k * P = r * Q + h * R, where Q is the public key. In this equality, we do not know the point R, and although it is possible to restore the coordinate y by r, this is an extremely slow operation. Therefore, we rewrite the equality in the form h * R = s * P - r * Q, then
R = (s * P -r * Q) / h and the comparison only x coordinates.
Although you can use any function for signing a message that hashes a suitable size, for example, SHA256 / SHA512, we will use the standard GOST R 34.11-2012 prescribed by the standard, including for compatibility with existing implementations. Unlike the signature, the hash is much simpler.
Detailed description and examples . Note the main points:
If the address is connected to the router via the I2CP protocol, then knowledge of the secret key of the signature by the router is not required.
Instead, the router sends a RequestLeaseSetMessage message (or RequestVariableLeaseSetMessage), waiting for a reply with a CreateLeaseSetMessage message containing a LeaseSet signed by the private key of the address. As you can see from the protocol description, in older versions of I2P it was required to transfer this key in the message, this is no longer required.
Thus, an application that implements an I2P address can use the API to sign one of the existing cryptographic providers with GOST, allowing you to effectively integrate the I2P solution into the existing infrastructure.
Currently i2pd fully supports signature types 9 and 10. Any client addresses will work with addresses on i2pd. An example of use. The server addresses require support from the floodfills, or an independent I2P network can be built with netid other than 2. In the main network, it is necessary to wait for it to be implemented in Java or an additional parameter floodfill .
Types of signatures in I2P
There are currently 9 types of signatures in I2P, where the type of signature is indicated, then the type of hash and, if necessary, the curve or its set of parameters.
- ECDSA_SHA256_P256
- ECDSA_SHA384_P384
- ECDSA_SHA512_P521
- RSA_SHA256_2048
- RSA_SHA384_3072
- RSA_SHA512_4096
- EdDSA_SHA512_Ed25519
- EdDSA_SHA512_Ed25519ph
Also, old addresses use type 0 - DSA_SHA1, which is considered obsolete.
It is recommended to use types 1 and 7.
For GOST, we, at my request, have two types:
9 - GOSTR3410_GOSTR3411_256_CRYPTO_PRO_A
10 - GOSTR3410_GOSTR3411_512_TC26_A
for 256 and 512-bit keys, respectively.
')
The length of the public key for 9 is 64 bytes (32 bytes for each coordinate of the point) and 128 bytes for 10.
Signature implementation GOST R 34.10
It is assumed that a hash of 256 or 512 bits is signed and verified. Detailed and with examples described here .
The usual elliptic curve is used, so functions from the cryptographic library can be used to work with it. In particular, it is EC_GROUP_ * and EC_POINT_ * from openssl, the main of which is:
int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *n, const EC_POINT *q, const BIGNUM *m, BN_CTX *ctx) used for both multiplying a base point by a number, or an arbitrary point, depending on the parameters.
For a curve, 6 parameters are specified: p is the modulus, a and b are the coefficients of the curve equation, P (x, y) is the base point, q is a prime number, multiplying by which the base point gives zero.
p and q should be large and close to the maximum, because p limits the range of all numbers, and q - the range of secret keys. The base point and q are calculated simultaneously.
As a rule, well-known and well-tested parameter sets are used.
In our implementation, we will use 2 sets of parameters:
- GostR3410_2001_CryptoPro_A_ParamSet (OID 1.2.643.2.2.35.1) for 256-bit keys, borrowed from GOST R 34.10-2001;
- id-tc26-gost-3410-12-512-paramSetA (OID 1.2.643.7.1.2.1.2.1) for 512-bit keys developed by TK26 (tc26.ru) specially for GOST R 34.10-2012.
Unlike the curve, the signature scheme in GOST is its own, therefore the ECDSA_sign and ECDSA_verify functions cannot be used and you should implement a signature and signature verification in your code.
For the signature (r, s), a random number k is selected, and the point R = k * P is calculated, the x coordinate of which becomes the signature component r. Component s = r * d + h * k, where d is the secret key, h is the hash of the message signature in Big Endian.
To verify the signature, multiply both sides of the equality by the base point P.
Indeed, s * P = r * d * P + h * k * P = r * Q + h * R, where Q is the public key. In this equality, we do not know the point R, and although it is possible to restore the coordinate y by r, this is an extremely slow operation. Therefore, we rewrite the equality in the form h * R = s * P - r * Q, then
R = (s * P -r * Q) / h and the comparison only x coordinates.
In the i2pd code it looks like this
bool GOSTR3410Curve::Verify (const EC_POINT * pub, const BIGNUM * digest, const BIGNUM * r, const BIGNUM * s) { BN_CTX * ctx = BN_CTX_new (); BN_CTX_start (ctx); BIGNUM * q = BN_CTX_get (ctx); EC_GROUP_get_order(m_Group, q, ctx); BIGNUM * h = BN_CTX_get (ctx); BN_mod (h, digest, q, ctx); // h = digest % q BN_mod_inverse (h, h, q, ctx); // 1/h mod q BIGNUM * z1 = BN_CTX_get (ctx); BN_mod_mul (z1, s, h, q, ctx); // z1 = s/h BIGNUM * z2 = BN_CTX_get (ctx); BN_sub (z2, q, r); // z2 = -r BN_mod_mul (z2, z2, h, q, ctx); // z2 = -r/h EC_POINT * C = EC_POINT_new (m_Group); EC_POINT_mul (m_Group, C, z1, pub, z2, ctx); // z1*P + z2*pub BIGNUM * x = BN_CTX_get (ctx); GetXY (C, x, nullptr); // Cx BN_mod (x, x, q, ctx); // Cx % q bool ret = !BN_cmp (x, r); // Cx = r ? EC_POINT_free (C); BN_CTX_end (ctx); BN_CTX_free (ctx); return ret; } Hash function GOST R 34.11-2012 (stribog)
Although you can use any function for signing a message that hashes a suitable size, for example, SHA256 / SHA512, we will use the standard GOST R 34.11-2012 prescribed by the standard, including for compatibility with existing implementations. Unlike the signature, the hash is much simpler.
Detailed description and examples . Note the main points:
- The original message is divided into blocks of 64 bytes. If the message is not a multiple of 64, then the first block is supplemented on the left with zero and single bytes.
- Each block is hashed separately, taking into account the hash of the previous block. For the very first block, the initialization vector (iv) is set as the previous hash. Passing through the blocks is carried out in the reverse order - from the last to the first.
- Each block is "encrypted" by 12 rounds with specified keys, each round is the application of three transformations S, P, L using specified tables and XOR with a round key.
- S is a byte-wise replacement, P is the hash transposition as 8x8 matrices, L is the multiplication by the given matrix.
- A 256-bit hash is the left half of a 512-bit hash, but the other iv is used, so it’s impossible to calculate them at the same time.
Signature by external crypto-provider using I2CP protocol
If the address is connected to the router via the I2CP protocol, then knowledge of the secret key of the signature by the router is not required.
Instead, the router sends a RequestLeaseSetMessage message (or RequestVariableLeaseSetMessage), waiting for a reply with a CreateLeaseSetMessage message containing a LeaseSet signed by the private key of the address. As you can see from the protocol description, in older versions of I2P it was required to transfer this key in the message, this is no longer required.
Thus, an application that implements an I2P address can use the API to sign one of the existing cryptographic providers with GOST, allowing you to effectively integrate the I2P solution into the existing infrastructure.
Implementation
Currently i2pd fully supports signature types 9 and 10. Any client addresses will work with addresses on i2pd. An example of use. The server addresses require support from the floodfills, or an independent I2P network can be built with netid other than 2. In the main network, it is necessary to wait for it to be implemented in Java or an additional parameter floodfill .
Source: https://habr.com/ru/post/325666/
All Articles