aezeed: add new package implementing the aezeed cipher seed scheme by Roasbeef · Pull Request #773 · lightningnetwork/lnd

Roasbeef · 2018-02-23T01:18:04Z

In this PR, we add a new package implementing the aezeed cipher
seed scheme (based on aez).

This is a new scheme developed that aims to overcome the
two major short comings of BIP39: a lack of a version, and a lack of a
wallet birthday. A lack a version means that wallets may not
necessarily know how to re-derive addresses during the recovery
process. A lack of a birthday means that wallets don’t know how far
back to look in the chain to ensure that they derive all the proper
user addresses. Additionally, BIP39 use a very weak KDF. We use
scrypt with modern parameters (n=32768, r=8, p=1). A set of benchmarks has
been added, on my laptop I get about 100ms per attempt):

⛰ go test -run=XXX -bench=.

goos: darwin
goarch: amd64
pkg: github.com/lightningnetwork/lnd/aezeed
BenchmarkToMnenonic-4     	      10	 102287840 ns/op
BenchmarkFromMnenonic-4   	      10	 105874973 ns/op
PASS
ok  	github.com/lightningnetwork/lnd/aezeed	3.036s

Aside from addressing the shortcomings of BIP 39 a cipher seed
can: be upgraded, and have it's password changed,

Sample seed:

ability dance scatter raw fly dentist bar nominee exhaust wine snap super cost case coconut ticket spread funny grain chimney aspect business quiz ginger

Plaintext `aezeed` encoding

The aezeed scheme addresses these two drawbacks and adds a number of
desirable features. First, we start with the following plaintext seed:

1 byte internal version || 2 byte timestamp || 16 bytes of entropy

The version field is for wallets to be able to know how to re-derive
the keys of the wallet.

The 2 byte timestamp is expressed in Bitcoin Days Genesis, meaning that
the number of days since the timestamp in Bitcoin’s genesis block. This
allow us to save space, and also avoid using a wasteful level of
granularity. With the currently, this can express time up until 2188.

Finally, the entropy is raw entropy that should be used to derive
wallet’s HD root.

`aezeed` enciphering/deciperhing

Next, we’ll take the plaintext seed described above and encipher it to
procure a final cipher text. We’ll then take this cipher text (the
CipherSeed) and encode that using a 24-word mnemonic. The enciphering
process takes a user defined passphrase. If no passphrase is provided,
then the string “aezeed” will be used.

To encipher a plaintext seed (19 bytes) to arrive at an enciphered
cipher seed (33 bytes), we apply the following operations:

First we take the external version an append it to our buffer. The
external version describes how we encipher. For the first version
(version 0), we’ll use scrypt(n=32768, r=8, p=1) and aezeed.
Next, we’ll use scrypt (with the version 9 params) to generate a
strong key for encryption. We’ll generate a 32-byte key using 5 bytes
as a salt. The usage of the salt is meant to make the creation of
rainbow tables infeasible.
Next, the enciphering process. We use aez, modern AEAD with
nonce-misuse resistance properties. The important trait we exploit is
that it’s an arbitrary input length block cipher. Additionally, it
has what’s essentially a configurable MAC size. In our scheme we’ll use
a value of 8, which acts as a 64-bit checksum. We’ll encrypt with our
generated seed, and use an AD of (version || salt).
Finally, we’ll encode this 33-byte cipher text using the default
world list of BIP 39 to produce 24 english words.

Properties of the aezeed cipher seed

The aezeed cipher seed scheme has a few cool properties, notably:

The mnemonic itself is a cipher text, meaning leaving it in
plaintext is advisable if the user also set a passphrase. This is in
contrast to BIP 39 where the mnemonic alone (without a passrphase) may
be sufficient to steal funds.
A cipherseed can be modified to change the passphrase. This
means that if the users wants a stronger passphrase, they can decipher
(with the old passphrase), then encipher (with a new passphrase).
Compared to BIP 39, where if the users used a passphrase, since the
mapping is one way, they can’t change the passphrase of their existing
HD key chain.
A cipher seed can be upgraded. Since we have an external version,
offline tools can be provided to decipher using the old params, and
encipher using the new params. In the future if we change ciphers,
change scrypt, or just the parameters of scrypt, then users can easily
upgrade their seed with an offline tool.

alexbosworth · 2018-02-23T01:35:31Z

aezeed/cipherseed.go

should this be CipherTextExpansion?

jonathancross · 2018-02-23T10:58:24Z

This is fantastic! Exactly what we'd need to bring Electrum and BIP39 wallets into a common standard without compromising the benefits of each approach. Will you be submitting a BIP for this?

wpaulino

Solid set of changes! Excited to see this merged 💯

I really dig the simplicity of the cipher seed scheme and the properties it enables. I've left a couple comments, but they're mostly pretty minor.

wpaulino · 2018-02-23T19:44:54Z

aezeed/cipherseed.go

typo: generate*

wpaulino · 2018-02-23T19:54:24Z

aezeed/cipherseed.go

nit: s/wallet/wallets

wpaulino · 2018-02-23T19:55:47Z

aezeed/cipherseed.go

nit: s/maintain/maintaining

wpaulino · 2018-02-23T19:58:51Z

aezeed/cipherseed.go

nit: extra "to"

wpaulino · 2018-02-23T20:01:07Z

aezeed/cipherseed.go

nit: s/encode/encoded

wpaulino · 2018-02-23T21:50:27Z

aezeed/cipherseed.go

Shouldn't this be 5 bytes?

Yep, we modified the params a bit recently.

wpaulino · 2018-02-23T21:59:37Z

aezeed/cipherseed.go

nit: missing comment

Added comment.

wpaulino · 2018-02-23T22:01:07Z

aezeed/cipherseed.go

nit: "of" isn't needed

wpaulino · 2018-02-23T22:16:11Z

aezeed/cipherseed.go

This doesn't seem to be used other than setting it when computing the ciphertext. If it's meant to be a cache, then we'd want to check if it was set before trying to compute it.

Yeah I had an initial use for it, but changed my mind towards the end. Updated to remove the field all together.

wpaulino · 2018-02-23T22:17:51Z

aezeed/cipherseed.go

Shouldn't we cache the ciphertext here as well?

Also, we'll want to check if a password was provided like in ToMnemonic. It might be better to move the check into encipher to avoid having to do it in both Encipher and ToMnemonic.

Roasbeef · 2018-02-23T23:40:16Z

@jonathancross once we get a bit of real world usage, we may submit a BIP. For now, it fits our use case precisely, so we'd rather include it immediately in the next release, rather than trying to make it a standard from the get go. Since we have an external version, if anything changes in the process, then we can provide an upgrade tool for anyone with an existing tool.

cfromknecht

Super excited about this new seed format, it offers so many benefits/improvements over current BIP39, e.g. birthdays! Also cool to see some more example of the quick testing package in action :)

Biggest change is just a simple %s/mnenonic/mnemonic/g, plus some others that exist due to casing. I tried to comment on the important functions/variables/types that had the mispelling, but there be others.

cfromknecht · 2018-02-23T08:08:54Z

aezeed/cipherseed.go

The bytes.Buffer struct has a 64-byte bootstrap array. We can get rid of two allocations by just using

var seedBytes bytes.Buffer

cfromknecht · 2018-02-23T08:09:58Z

aezeed/cipherseed.go

Comment formatting needs fixing

ignore this, was carried over from review i had started a few days ago

cfromknecht · 2018-02-28T00:16:52Z

aezeed/cipherseed.go

Add note that these constants are tied to external version 0?

cfromknecht · 2018-02-28T00:17:53Z

aezeed/cipherseed.go

dates -> days

cfromknecht · 2018-02-28T00:23:28Z

aezeed/cipherseed.go

unnecessary dereference? or is this our preferred syntax within lnd style guidelines?

cfromknecht · 2018-02-28T00:49:03Z

aezeed/errors.go

mnenonic -> mnemonic

cfromknecht · 2018-02-28T00:52:27Z

aezeed/cipherseed.go

Use saltOffset constant described above here and next line

cfromknecht · 2018-02-28T00:57:43Z

aezeed/cipherseed.go

This operation assumes that every word of mnemonic is actually in the reversed word list. This seems like the logical place to verify that the provided words are valid, maybe returning ErrUnknownMnenomicWord if we don't know a particular one.

cfromknecht · 2018-02-28T00:59:08Z

aezeed/cipherseed.go

NumMnenonicWords -> NumMnemonicWords

cfromknecht · 2018-02-28T00:59:33Z

aezeed/bench_test.go

almost! BenchmarkToMnenonic -> BenchmarkToMnemonic

cfromknecht · 2018-02-28T02:00:20Z

aezeed/bench_test.go

Add b.ReportAllocs() here as well

cfromknecht · 2018-02-28T02:00:42Z

aezeed/bench_test.go

Add b.ReportAllocs() here so that we can measure bytes/allocs per invocation?

ecdsa · 2018-02-28T07:57:33Z

interesting.
do you really need day granularity for the timestamp? you could use block_height//2016

cfromknecht · 2018-02-28T08:39:02Z

@ecdsa tying the birthday to a particular block height would require the seed format to know about the parameters of the underlying chain. the rationale behind not doing so is that an aezeed can be used to secure keys on any/multiple chains without modification, while also being flexible enough to allow the same seed to add derivation paths for other currencies at a later time.

most importantly, using the block height in the birthday would require you to sync the [header] chain before creating the seed.

that aside, I believe your point is about potentially increasing the granularity? we definitely could increase it, though with day granularity we should be good until almost 2188. with 2-week intervals, it would approach the year 4251. note that this is only a bound on the birthday of the seed, not a bound on the seed's lifetime. IMO I think this is a happy medium in terms of granularity, has a super simple implementation, and works on any chain!

Roasbeef · 2018-03-01T02:34:57Z

Alrighty, pushed out a fixup commit that adds the ability to detect if a word isn't in the original list, and also if the mnemonic was entered incorrectly.

@cfromknecht PTAL.

cfromknecht

Alrighty, I really like this last set of changes. The addition of an external checksum gives us some integrity, as well as a way to distinguish invalid passwords from invalid mnemonics. LGTM conditioned on one last spelling correction! Long live aezeed ⚡️

cfromknecht · 2018-03-01T03:10:15Z

aezeed/cipherseed.go

Nice additions!

cfromknecht · 2018-03-01T03:16:23Z

aezeed/cipherseeed_test.go

cfromknecht · 2018-03-01T03:18:16Z

aezeed/cipherseed.go

remove* and verify

dabura667 · 2018-03-01T10:56:36Z

Super cool.

halseth · 2018-03-01T14:20:55Z

aezeed/cipherseed.go

Is the non-exported version of this method really needed?

halseth · 2018-03-01T14:23:46Z

aezeed/cipherseed.go

extract the default passphrase into constant?

halseth · 2018-03-01T14:30:28Z

aezeed/cipherseed.go

this should be "aezeed"?

halseth · 2018-03-01T14:30:55Z

aezeed/cipherseed.go

halseth · 2018-03-01T14:32:45Z

aezeed/cipherseed.go

I don't get this... That the users can encrypt the plaintext unders distinct passwords, is that a desirable feature or not?

Yes, this means they can replicate the same seed widely under distinct passwords. Each one when decrypted will allow then to restore their wallet.

One can even take an existing seed, and then produce a new one with a diff passphrase.

cfromknecht · 2018-03-01T21:45:26Z

I thought about the case in which we may want to allow the user to just copy and paste the raw seed output (including the header and footer) and the need to make the seed easily parseable. I made another version that both writes and reads the seed entirely, the primary distinction is that each field is now just <num>:<word> instead of <num>. <word> which makes parsing simpler.

Some demo code in a playground is here: https://play.golang.org/p/nD4YLW_HW5o

This isn't necessary for this PR, but figured I'd make note of it here in case we want to add or come back to this later.

The new logic also is more general to allow us to try varying the number of columns. I still think 4 looks the best, but this should allow us to try out whatever combinations we want :)

In this commit, we add a new package implementing the aezeed cipher seed scheme. This is a new scheme developed that aims to overcome the two major short comings of BIP39: a lack of a version, and a lack of a wallet birthday. A lack a version means that wallets may not necessarily know *how* to re-derive addresses during the recovery process. A lack of a birthday means that wallets don’t know how far back to look in the chain to ensure that they derive *all* the proper user addresses. The aezeed scheme addresses these two drawbacks and adds a number of desirable features. First, we start with the following plaintext seed: {1 byte internal version || 2 byte timestamp || 16 bytes of entropy}. The version field is for wallets to be able to know *how* to re-derive the keys of the wallet. The 2 byte timestamp is expressed in Bitcoin Days Genesis, meaning that the number of days since the timestamp in Bitcoin’s genesis block. This allow us to save space, and also avoid using a wasteful level of granularity. With the currently, this can express time up until 2188. Finally, the entropy is raw entropy that should be used to derive wallet’s HD root. Next, we’ll take the plaintext seed described above and encipher it to procure a final cipher text. We’ll then take this cipher text (the CipherSeed) and encode that using a 24-word mnemonic. The enciphering process takes a user defined passphrase. If no passphrase is provided, then the string “aezeed” will be used. To encipher a plaintext seed (19 bytes) to arrive at an enciphered cipher seed (33 bytes), we apply the following operations: * First we take the external version an append it to our buffer. The external version describes *how* we encipher. For the first version (version 0), we’ll use scrypt(n=32768, r=8, p=1) and aezeed. * Next, we’ll use scrypt (with the version 9 params) to generate a strong key for encryption. We’ll generate a 32-byte key using 5 bytes as a salt. The usage of the salt is meant to make the creation of rainbow tables infeasible. * Next, the enciphering process. We use aezeed, modern AEAD with nonce-misuse resistance properties. The important trait we exploit is that it’s an *arbitrary input length block cipher*. Additionally, it has what’s essentially a configurable MAC size. In our scheme we’ll use a value of 4, which acts as a 32-bit checksum. We’ll encrypt with our generated seed, and use an AD of (version || salt). We'll them compute a checksum over all the data, using crc-32, appending the result to the end. * Finally, we’ll encode this 33-byte cipher text using the default world list of BIP 39 to produce 24 english words. The `aezeed` cipher seed scheme has a few cool properties, notably: * The mnemonic itself is a cipher text, meaning leaving it in plaintext is advisable if the user also set a passphrase. This is in contrast to BIP 39 where the mnemonic alone (without a passphrase) may be sufficient to steal funds. * A cipherseed can be modified to *change* the passphrase. This means that if the users wants a stronger passphrase, they can decipher (with the old passphrase), then encipher (with a new passphrase). Compared to BIP 39, where if the users used a passphrase, since the mapping is one way, they can’t change the passphrase of their existing HD key chain. * A cipher seed can be *upgraded*. Since we have an external version, offline tools can be provided to decipher using the old params, and encipher using the new params. In the future if we change ciphers, change scrypt, or just the parameters of scrypt, then users can easily upgrade their seed with an offline tool. * We're able to verify that a user has input the incorrect passphrase, and that the user has input the incorrect mnemonic independently.

In this commit we add a set of benchmarks to be able to measure the enciphering and deciphering speed of the current scheme with the current scrypt parameters. On my laptop I get about 100ms per attempt: ⛰ go test -run=XXX -bench=. goos: darwin goarch: amd64 pkg: github.com/lightningnetwork/lnd/aezeed BenchmarkToMnenonic-4 10 102287840 ns/op BenchmarkFromMnenonic-4 10 105874973 ns/op PASS ok github.com/lightningnetwork/lnd/aezeed 3.036s

ecdsa · 2018-03-02T09:25:20Z

@Roasbeef can you clarify the purpose of the version number? is it there only in order to be able to upgrade the cipher (and the key derivation remains unspecified, as in BIP43) , or will it also be used to specify the key derivation?

Roasbeef · 2018-03-03T02:48:06Z

@ecdsa there're two versions: external and internal.

The external version governs how to decipher the cipher seed. So: key derivation parameters, checksum verification, salt. In the future if we upgrade any of these parameters, users can use an offline tool to "upgrade" their seed.

The internal version is for the wallet. It tells that wallet how to go about re-deriving all the addresses for the user. Unlike the external version (in my mental model at least), wallets don't need to agree on what this value is, or how it should be interpreted. So for example a version of 0 could mean to a wallet: "use bip44". While a version of 1 could mean: "use bip49 and bip84". If a wallet gets the deciphered cipher seed, and doesn't recognize the version, then it should reject it.

jimpo

Looks really good. The design is sweet.

jimpo · 2018-03-03T14:04:18Z

aezeed/cipherseed.go

+	// With CipherSeedVersion we encipher as follows: we use
+	// scrypt(n=32768, r=8, p=1) to derive a 32-byte key from an optional
+	// user passphrase. We then encipher the plaintext seed using a value
+	// of tau (with aez) of 8-bytes (so essentially a 32-bit MAC).  When


tau of 4 bytes

jimpo · 2018-03-03T14:05:44Z

aezeed/cipherseed.go

+	// computing our checksum.
+	crcTable = crc32.MakeTable(crc32.Castagnoli)
+
+	// defaultPassphras is the default passphrase that will be used for


typo: defaultPassphrase

jimpo · 2018-03-03T14:54:54Z

aezeed/cipherseed.go

+	// Before we attempt to map the mnemonic back to the original
+	// ciphertext, we'll ensure that all the word are actually a part of
+	// the current default word list.
+	for _, word := range m {


Agree with @cfromknecht's comment to move this check into mnemonicToCipherText.

jimpo · 2018-03-03T15:13:30Z

aezeed/cipherseed.go

+// re-enciphers the plaintext cipher seed into a brand new mnemonic. This can
+// be used to allow users to re-encrypt the same seed with multiple pass
+// phrases, or just change the passphrase on an existing seed.
+func (m *Mnemonic) ChangePass(oldPass, newPass []byte) (Mnemonic, error) {


Would it make sense to roll the salt here as well?

JeremyRubin · 2018-04-09T20:49:09Z

I know this is already merged, but I wanted to propose an alternative for the birthday mechanism which strengthens the 'exclusion proof' property.

If one uses a block hash instead of a clock-time, it makes it cryptographically impossible to pick a future birthdate. Picking a future time undermines the utility of the birthdate for proving that no transactions would be present before a certain time. However, even an honest seed-creator can't preclude themselves from creating a future-timed seed. This is because a big reorg could place transactions created after the creation of the seed to before the creation of the seed.

Using a blockhash instead of clock-time doesn't solve this problem, but it allows us to detect that this has occurred and then revert to a chain scan up to the most-recent-ancestor of the header hash used.

To keep this from adding overhead to the seed, what can be done is to only allow using every 144th (e.g. bitcoin-day) header hash. This can be specified using the same 2 byte index, then the client simply has to fetch the header-hash from the network and include it. One must be careful to ensure that it is indeed the same blockhash, otherwise no addresses will be found. This risk can be mitigated by not using the indexing trick above to save 30 bytes (storing the header with the seed directly) or by making use of the aez checksum.

Jason-123-cyber

OK

Jason-123-cyber · 2026-01-19T06:56:01Z

TK

Jason-123-cyber · 2026-01-19T06:56:07Z

K

Jason-123-cyber · 2026-01-19T06:56:13Z

OK

alexbosworth reviewed Feb 23, 2018

View reviewed changes

Roasbeef added this to the v0.4-beta milestone Feb 23, 2018

wpaulino suggested changes Feb 23, 2018

View reviewed changes

Roasbeef assigned cfromknecht Feb 26, 2018

cfromknecht suggested changes Feb 28, 2018

View reviewed changes

cfromknecht reviewed Feb 28, 2018

View reviewed changes

cfromknecht previously approved these changes Mar 1, 2018

View reviewed changes

halseth reviewed Mar 1, 2018

View reviewed changes

Roasbeef dismissed cfromknecht’s stale review via 5c070f5 March 2, 2018 00:51

Roasbeef force-pushed the aezeed branch from b53872d to 5c070f5 Compare March 2, 2018 00:51

Roasbeef added 4 commits March 1, 2018 17:10

aezeed: add comprehensive, mostly property-based tests

eb3b519

build: add aez and bstream to glide

d65fe83

Roasbeef force-pushed the aezeed branch from 5c070f5 to d65fe83 Compare March 2, 2018 01:11

Roasbeef merged commit 1ba3992 into lightningnetwork:master Mar 2, 2018

jimpo reviewed Mar 3, 2018

View reviewed changes

guggero mentioned this pull request Mar 23, 2018

aezeed: add tests and README #929

Merged

torkelrogstad mentioned this pull request Feb 18, 2019

Get started on implementing seed derivation bitcoin-s/bitcoin-s#342

Closed

Jason-123-cyber reviewed Jan 19, 2026

View reviewed changes

Conversation

Roasbeef commented Feb 23, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Plaintext aezeed encoding

aezeed enciphering/deciperhing

Properties of the aezeed cipher seed

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonathancross commented Feb 23, 2018

Uh oh!

wpaulino left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Roasbeef commented Feb 23, 2018

Uh oh!

cfromknecht left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Roasbeef commented Feb 23, 2018 •

edited

Loading

Plaintext `aezeed` encoding

`aezeed` enciphering/deciperhing