Validators' Security

Introduction to Validator Security

Introduction

To discuss the bridge validator's security, we must properly understand Schnorr's signature strength and how FROST enables threshold signature based on Schnorr. The scientist's last name has almost become a term in our days. However, he is still alive, and we want to pay tribute to his work here.

Dr. Claus Peter Schnorr

Oberwolfach. 2009 (https://opc.mfo.de/) Author: Schmid, Renate

Born on August 4th, 1943, in Germany, C.P. Schnorr worked as a Professor of Mathematics at Goethe University, Frankfurt, Germany (1971-2011) - for 40 years.

The scientist is most famous for the introduction of the following:

1. Algorithmic information theory (AIT) - data complexity study
2. Algorithmically random sequence - binary data (Ex.: 01010101001010101001010) random from the algorithm point of view
3. Schnorr groups
4. Schnorr signature

We gave a brief explanation of what the first concepts describe. We will discuss in greater detail the latter two.

Prime [order] numbers

Prime numbers play a crucial role in cryptography due to their unique properties and the difficulty of certain mathematical problems associated with them. Here are a few reasons why prime numbers are important for cryptography:

1. Key generation: In many cryptographic systems, prime numbers are used to generate cryptographic keys. For example, in asymmetric encryption algorithms like RSA, the security relies on the difficulty of factoring large composite numbers into their prime factors. Prime numbers are used to generate the public and private keys, making it computationally difficult for an attacker to determine the private key from the public key.

2. Prime modulus: Prime numbers are often used as moduli in modular arithmetic operations within cryptographic algorithms. Using a prime modulus enhances the security of operations like exponentiation and modular inversion. It ensures that the computations resist certain mathematical attacks, such as the discrete logarithm problem (see below).

3. Primality testing: Primality testing algorithms determine whether a given number is prime. These algorithms are essential for cryptographic protocols that involve large numbers. Efficient primality testing algorithms help ensure that the prime numbers used in cryptographic operations are indeed prime and not vulnerable to attacks based on the composite nature of the numbers.

4. Random number generation: Prime numbers are often used to generate random numbers for cryptographic purposes. Random prime numbers are desirable due to their inherent unpredictability and difficulty in determining their factors. They provide a crucial foundation for generating secure cryptographic keys and various other cryptographic operations requiring randomness.

The word prime originates from the Latin word primus which means the first, or the foremost.

A number is prime if it is:

1. an Integer (-7 | 0 | 5) from Latin whole, untouched. Integers are whole numbers that have no fractions. I. can be negative or positive.
2. Positive (0,1,2,3) - (>= 0). By convention and definition, prime numbers are specifically restricted to natural numbers defined as positive integers for convenience of algebraic operations.
3. Greater than 1 (> 1). It explains why the first prime is 2, not 1.
4. It must have no positive dividers but:

• 1
• itself

The last point explains why 1 is not a prime number. It would contradict the definition that a prime is divided by 1 & itself because it would be one or itself in both cases.

Example list of prime numbers: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59...]

Primes play an essential role in computationally complex problems:

1. Prime factorization
2. Discrete logarithm problem

Here's a naive easy to understand Rust example algorithm finding prime numbers up to a certain number.

use num_bigint::{BigUint, ToBigUint};
use num_traits::{ToPrimitive};
use std::io::{self, Write};

fn is_even(n: &BigUint) -> bool {
    // Check what we received
    match n.to_u128() {
        // If received a value - check whether even
        Some(value) => value & 1 == 0,
        // Nothing cannot be even
        None => false
    }
}

fn is_prime(n: &BigUint) -> bool {

    // 2 is the first prime number
    if n == &2u32.to_biguint().unwrap() {
        return true;
    }

    // An even number cannot be prime
    // Number 1 & less cannot be prime
    if is_even(n) || n <= &1u32.to_biguint().unwrap() {
        return false;
    }

    // Set the step = 2
    let two = 2u32.to_biguint().unwrap();
    // Set the start to 3 - the next prime after 2
    let mut i = 3u32.to_biguint().unwrap();

    // Loop from 3 to the checked number
    while &i * &i <= *n {
        // If dividend divided by the divisor has the 0 remainder
        if n % &i == 0u32.to_biguint().unwrap() {
            return false;
        }

        // Skip even divisors
        i += &two;
    }

    true
}

fn main() {

    let start = BigUint::from(3u64); // 3
    let end = BigUint::from(1000u64); // 1000
    // Counter - how many steps we took
    let mut step = BigUint::from(0u64); // 0

    // The currently checked number
    let mut current = start.clone();

    let one = BigUint::from(1u32); // 1
    let two = 2u32.to_biguint().unwrap(); // 2

    // To print steps on one line
    let stdout = io::stdout();
    let mut handle = stdout.lock();

    while &current <= &end {

        step += &one; // Operations counter incrementer
        // Print the current step number & the number we're checking
        let _ = write!(handle, "\rStep:{} Current:{}", &step, &current);
        // Clear the line
        let _ = handle.flush();

        if is_prime(&current) {
            // Print the Prime on a new line & 100 spaces to erase chars from steps
            let _ = writeln!(handle, "\rPrime: {}{}", 
                &current,String::from(" ").repeat(100));
        } 

        // Evens cannot be primes - skip them
        current += &two;
        
    }
    // Move the cursor to the new line
    let _ = writeln!(handle,"\n");

}

Try replaceing these lines:

let start = BigUint::from(3u64); // 3
let end = BigUint::from(1000u64); // 1000

with those:

let start = BigUint::from(2u64).pow(64); // 2^64
let end = BigUint::from(2u64).pow(128); // 2^128

... and you will see that it takes "forever" to find at least one prime number.

Prime Factorization

Prime factorization expresses a positive integer greater than one as a product of its prime factors.

To perform prime factorization, you repeatedly divide the number by the smallest prime numbers (starting from 2) until the quotient becomes 1. The divisors used in this process are prime factors, and their repeated division ultimately yields the prime factorization of the original number.

For example, let's find the prime factorization of the number 84:

1. Start with the number 84.
2. Divide 84 by the smallest prime number, 2. The quotient is 42.
3. Divide 42 by two again. The quotient is 21.
4. Divide 21 by 3, the next prime number. The quotient is 7. Since 7 is a prime number itself, we stop dividing further.

The prime factors obtained from the division are 2, 2, 3, and 7.

Therefore, the prime factorization 84 is 2 2 3 7, or in exponent form, 2^2 3 * 7.

Discrete Logarithm Problem (DLP)

To understand the DLP, let's decompose it word by word and explain each part.

Discrete

The word discrete originates from the Latin word discretus, later converted to its modern form in late middle English with the semantical meaning separate. By convention in mathematics, discrete numbers have the following properties:

Examples:

1. Integers ∈ {..., -3, 0, 2,...}
2. Final sets, ex.:graph with 3 vertices ∈ {x, y z} Features: Individual elements with no intermediary values between them.

In mathematics, the antonym of discrete is composite borrowed into Old English circa 1400 via French from the Latin compositus meaning "placed together." In mathematics, composite numbers are defined as unbroken, connected within a range, continuous structures, including all the intermediaries between them.

Expected attributes of composite numbers are:

1. Real number ∈ {0.00, 0.000001,... , 1.00}
2. Functions or curves, ex.: straight lines, parabolas, sine or cosine curves

Logarithm

The logarithm is a mathematical function that quantifies the exponent to which a given base must be raised to obtain a specific number. In other words, it represents the inverse operation of exponentiation. The logarithm of a number expresses the power to which the base must be raised to equal that number.

The logarithm function is denoted as logₐ(x), where "a" represents the base and "x" represents the number for which the logarithm is being calculated.

The concept of Logarithms was proposed by a Scottish mathematician John Napier (1550-April 4, 1617) to aid in astronomical calculations. Properties of logarithms are still extensively used, especially in modern cryptography.

Problem

The problems in DLP cascade one into another:

1. Lack of effective algorithms => which leads to
2. Exponential search space => which makes it
3. Computationally expensive

DLP Example:

Given:

• Prime number = 11
  
• Base = 2
  
• $2^x~mod~11~≅~5$
  

Problem:

• x = exponent/power?

Brute forcing algorithm:

Since no known effective mechanism exists, we use brute force to crack the task. The steps can look like this:

1. $2^1~mod~11~=~2~\%~11~≅~2$, $2~!=~5$ - Continue.
2. $2^2~mod~11~=~4~\%~11~≅~4$, $4~!=~5$ - Continue.
3. $2^3~mod~11~=~8~\%~11~≅~8$, $8~!=~5$ - Continue.
4. $2^4~mod~11~=~16~\%~11~≅~5$, $5~==~5$ - Solution found.

Solution explanation:

$2^x~=~2~*~2~*~2~*~2~=~16$

$16~\%~11~=~16~-~11~≅~5$

Result: $x~=~4$

The solution looks quite simple. It only took us four steps to find the answer. The real problem begins when the numbers become very big.

Extremely Large Numbers (BigNum)

The larger the elliptic curve parameters are, the more computationally expensive they are:

Bad for benevolent users:

1. Signature generation
2. Message signing
3. Signature verification

Bad for malicious adversaries:

4. Brute force attacking

Therefore, the size selection is always a tradeoff between:

1. security (complexity for the attackers) and
2. usability (reasonable time of execution for the users).

n-bit security level:

A measure in bits has been introduced to quantify the difficulty of a brute-force attack. An attacker must try up to $2^n$ combinations to find the answer.

For example:

• 128-bit security means an attacker needs up to $2^{128}$ or $3.4~x~10^{38}$ combinations to break it.
• 265-bit security requires an attacker to try up to $1.16~x~10^{77}$ times.

Bridge validator security is a very complex but a crucially important question. Therefore, we divided it into several parts:

1. Schnorr Key Generation

2. Signing with FROST

3. Signature verification