search

infincia / bip39-rs

A Rust implementation of BIP-0039
Apache License 2.0
54 stars 61 forks source link

WIP: Regression of seed generation between v0.5.1 and v0.6.0-beta.1 #17

Closed wigy-opensource-developer closed 5 years ago

wigy-opensource-developer commented 5 years ago

I have cross-checked the seeds generated from the mnemonics with some other BIP39 wallets. I found that although the relation between English mnemonics and entropy conforms the BIP-0039 standard, the seed generation did not match even when only using ASCII (0..127) characters in the password (I know the UTF-8 normalization is still missing there).

I have added failing tests, but could not get them pass yet.

To manually cross-check the test-cases I have added based on the Trezor test-vector referenced from the standard, please

I think the problem should be somehow in the crpyto::pbkdf2 implementation, but could not narrow it down.

wigy-opensource-developer commented 5 years ago

I have backported the same tests on top of v0.5.1 and they all pass. So replacing the ring::pbkdf2 call with pbkdf2::pbkdf2 seems to be causing the regression.

I know October 2018 was a loooong time ago, but could maybe @maciejhirsz give us some advise what could be the difference?

wigy-opensource-developer commented 5 years ago

Sorry, it was @QuestofIranon from Hashgraph and not Maciej from ParityTech who changed the crypto.rs and ported the code to the pure rust https://github.com/RustCrypto crates from the ring wrappers in commits 064e692b673edf014b86ad4bd29668e8bd3a714a and b1b8c3e8cb3789a591536135f88ef0cb55fe9e91.

Could you Josh please shed a light on what might have gone wrong with that PBKDF2 replacement?

maciejhirsz commented 5 years ago

That is super strange and should likely be taken upstream. In the mean time, I reckon we should revert back to ring and add unit tests for seed generation to make sure it doesn't happen again.

There is a chance it's a small issue with either the salt of how the number of rounds is being managed on the API surface, I'll look into it.

wigy-opensource-developer commented 5 years ago

As I wrote in the 1st comment, the tests are already there in this PR. And I also backported it on v0.5.1 to show it worked in that version.

steveatinfincia commented 5 years ago

Yikes, good catch! Glad I gave v0.6.0-beta.1 a long testing period.

@wigy-opensource-developer do you want me to merge this as-is since the tests are useful either way, or do you want to push another commit to switch the pbkdf2 implementation back as well?

wigy-opensource-developer commented 5 years ago

This pull request was more like a discussion starter, that is why I gave you commit rights on the branch. If you decided to just revert to ring, I can do it tomorrow.

But if you want to keep the pure rust cryptographic libraries, then I am not sure if it was an integration issue here or an upstream incompatibility. Turning off parallel computation did not help fixing it.

As Maciej said if it turns out it is not an integration issue, we need to file some PRs upstream into the RustCrypto/password-hashing repo. I can also do that tomorrow.

QuestofIranon commented 5 years ago

I'm going to take a look into it tonight as well.

wigy-opensource-developer commented 5 years ago

Well, at least I tried to fix it. Using ring 0.14.3 for PBKDF2 did not help to fix the tests. (Reminder, the same tests backported to bip39-rs 0.5.1 did succeed.) So I definitely need some help from @QuestofIranon to fix this.

QuestofIranon commented 5 years ago

The issue definitely doesn't appear to be the rust implementation of pbkdf2. I checked the seeds generated by @wigy-opensource-developer's tests. They result in the same (wrong) seed generated for both pbkdf2 implementations.

QuestofIranon commented 5 years ago

I reverted it to 70ef062fa494e0f4b0d924d93364bcb76d4c8bb5 to redo my changes and backported the test to run step by step. I found that this commit was also failing with both pbkdf1 libraries. However, as with my previous test, they were producing the same results. I'll look more into what has changed between bip39-rs 0.5.1 and 70ef062fa494e0f4b0d924d93364bcb76d4c8bb5 when I have more time but would appreciate a second look by @maciejhirsz and @steveatinfincia as well.

wigy-opensource-developer commented 5 years ago

Wow. Nice bisection, thanks, Josh.

QuestofIranon commented 5 years ago

Had a little bit of time to do some more testing today. I found that using Seed::generate in the test for 0.5.1 instead of as_seed from the mnemonic creates the same results as the failed tests in newer versions. The newer versions use Seed::new due to Mnemonic no longer having the as_seed method (in other words it no longer stores the seed when generated). Haven't looked into it too much more yet though - quick glance looked like the seed created during Mnemonic generation in the old version also uses Seed::generate so it might be something wrong with how entropy is handled instead of seed creation.

maciejhirsz commented 5 years ago

I tracked the issue to one of my changes, the fix is to change line 30 in seed.rs:

let bytes = pbkdf2(mnemonic.entropy(), &salt);

to:

let bytes = pbkdf2(mnemonic.phrase().as_bytes(), &salt);

I don't know why when refactoring that part I assumed it's entropy instead of phrase, but looking at the spec now makes it clearly wrong :\.

wigy-opensource-developer commented 5 years ago

Thank for @QuestofIranon to fix this in #18