`keyfork mnemonic recover` should accept words in a randomized pattern

ryan commented

2023-08-18 00:09:26 +00:00

Owner

Rationale: Prevent shoulder surfing as well as keyfork mnemonic generate | keyfork mnemonic recover, ensuring users write down their mnemonic.

cc @lrvick

Rationale: Prevent shoulder surfing as well as `keyfork mnemonic generate | keyfork mnemonic recover`, ensuring users write down their mnemonic. cc @lrvick

ryan commented

2023-08-18 00:52:20 +00:00

Author

Owner

additional: attacker-known 24 words only provides about 90 bits of entropy, 12 words even less. have the user type in 36 words regardless, which provides 36! permutations which is more than 2^128 / 128 bits of entropy. purpose: keylogger brute forcing based on words tracked.

ryan commented

2023-08-18 00:56:11 +00:00

Author

Owner

36 looks nicer than 35, which is the actual smallest number whose permutation count (factorial) is > 2^128

ryan commented

2023-08-18 01:07:37 +00:00

Author

Owner

Assumption is that each word is unique but this is only average case, not every case

snail commented

2023-08-18 01:14:51 +00:00

Since an attacker only needs to select 24 of the 36 words, they can let the remaining 12 words take any order.

You'd be looking for (X choose 24)*24! > 2^128, which puts X at 53 for selecting 24 words.

However, since the checksum word is determined from the other 23, the attacker really only needs to find 23 words, which puts the required inputs at 59.

Note: This is ignoring duplicate words in the input, and cases where none of the possible checksum words are in the users input. So the actual answer is likely higher.

Since an attacker only needs to select 24 of the 36 words, they can let the remaining 12 words take any order. You'd be looking for `(X choose 24)*24! > 2^128`, which puts X at 53 for selecting 24 words. However, since the checksum word is determined from the other 23, the attacker really only needs to find 23 words, which puts the required inputs at 59. Note: This is ignoring duplicate words in the input, and cases where none of the possible checksum words are in the users input. So the actual answer is likely higher.

👍 1

ryan commented

2023-08-18 01:14:59 +00:00

Author

Owner

Figuring out the math for the possibility a 24 word mnemonic has duplicate words, using some rough birthday-problem math (https://en.wikipedia.org/wiki/Birthday_problem#Calculating_the_probability):

Vnr = words! / (words - wordcount)! = 2048! / (2048 - 24)! = 25892008055647378700916274834106651525738683598033725572049016676308484096000000
Vt = words ^ wordcount = 2048 ^ 24 = 29642774844752946028434172162224104410437116074403984394101141506025761187823616
P(A) = Vnr / Vt =~ 0.873468
P(B) = 1 - P(A) =~ 0.126532, or 12%

12% chance that we have a shared word.

Figuring out the math for the possibility a 24 word mnemonic has duplicate words, using some rough birthday-problem math (https://en.wikipedia.org/wiki/Birthday_problem#Calculating_the_probability): ``` Vnr = words! / (words - wordcount)! = 2048! / (2048 - 24)! = 25892008055647378700916274834106651525738683598033725572049016676308484096000000 Vt = words ^ wordcount = 2048 ^ 24 = 29642774844752946028434172162224104410437116074403984394101141506025761187823616 P(A) = Vnr / Vt =~ 0.873468 P(B) = 1 - P(A) =~ 0.126532, or 12% ``` 12% chance that we have a shared word.

ryan commented

2023-08-18 04:16:35 +00:00

Author

Owner

The math says this should be 12%. snail's Python code says this should be 12%. My Rust code - even with OS RNG - says this should be 12%. And yet, for some reason, this test stops at 1%.

https://git.distrust.co/public/keyfork/src/branch/main/keyfork-mnemonic-generate/src/main.rs#L236-L250

The math says this should be 12%. snail's Python code says this should be 12%. My Rust code - even with OS RNG - says this should be 12%. And yet, for some reason, this test stops at 1%. https://git.distrust.co/public/keyfork/src/branch/main/keyfork-mnemonic-generate/src/main.rs#L236-L250

ryan commented

2023-08-18 04:21:56 +00:00

Author

Owner

use std::io::Read;
use rand::prelude::*;

fn get_u32_os(file: &mut std::fs::File) -> u32 {
    let mut bytes = [0u8; 4];
    file.read_exact(&mut bytes).unwrap();
    u32::from_le_bytes(bytes)
}

fn get_u32_trng(trng: &mut rand::rngs::ThreadRng) -> u32 {
    trng.next_u32()
}

const MNEMONIC_MAX: u32 = 2048;
const MNEMONIC_SIZE: usize = 24;
const ITERATIONS: usize = 100_000;

fn os_rng() {
    let total = ITERATIONS;
    let mut count = 0;
    let mut file_handler = std::fs::File::open("/dev/urandom").unwrap();
    for _ in 0..ITERATIONS {
        let mut data = [0; MNEMONIC_SIZE];
        for d in &mut data {
            *d = get_u32_os(&mut file_handler) % MNEMONIC_MAX;
        }
        let set = std::collections::HashSet::from(data);
        if set.len() < MNEMONIC_SIZE {
            count += 1;
        }
    }
    dbg!("OS", total, count, total - count);
}

fn thread_rng() {
    let mut rng = rand::thread_rng();
    let total = ITERATIONS;
    let mut count = 0;
    for _ in 0..ITERATIONS {
        let mut data = [0; MNEMONIC_SIZE];
        for d in &mut data {
            *d = get_u32_trng(&mut rng) % MNEMONIC_MAX;
        }
        let set = std::collections::HashSet::from(data);
        if set.len() < MNEMONIC_SIZE {
            count += 1;
        }
    }
    dbg!("Thread RNG", total, count, total - count);

}

fn main() {
    os_rng();
    thread_rng();
}

```rust use std::io::Read; use rand::prelude::*; fn get_u32_os(file: &mut std::fs::File) -> u32 { let mut bytes = [0u8; 4]; file.read_exact(&mut bytes).unwrap(); u32::from_le_bytes(bytes) } fn get_u32_trng(trng: &mut rand::rngs::ThreadRng) -> u32 { trng.next_u32() } const MNEMONIC_MAX: u32 = 2048; const MNEMONIC_SIZE: usize = 24; const ITERATIONS: usize = 100_000; fn os_rng() { let total = ITERATIONS; let mut count = 0; let mut file_handler = std::fs::File::open("/dev/urandom").unwrap(); for _ in 0..ITERATIONS { let mut data = [0; MNEMONIC_SIZE]; for d in &mut data { *d = get_u32_os(&mut file_handler) % MNEMONIC_MAX; } let set = std::collections::HashSet::from(data); if set.len() < MNEMONIC_SIZE { count += 1; } } dbg!("OS", total, count, total - count); } fn thread_rng() { let mut rng = rand::thread_rng(); let total = ITERATIONS; let mut count = 0; for _ in 0..ITERATIONS { let mut data = [0; MNEMONIC_SIZE]; for d in &mut data { *d = get_u32_trng(&mut rng) % MNEMONIC_MAX; } let set = std::collections::HashSet::from(data); if set.len() < MNEMONIC_SIZE { count += 1; } } dbg!("Thread RNG", total, count, total - count); } fn main() { os_rng(); thread_rng(); } ```

ryan commented

2023-08-18 05:29:59 +00:00

Author

Owner

Resolved. Vec::dedup only removes sequential duplicates.

lrvick added this to the Custody Framework project 2024-11-25 10:21:10 +00:00

keyfork mnemonic recover should accept words in a randomized pattern #1

`keyfork mnemonic recover` should accept words in a randomized pattern #1