AES-XTS VFS

[ben-krieger]

When I was going through a crypto review as part of internal corporate processes, the reviewers found the crypto in Adiantum a bit too new-fangled. Nothing inherently wrong, just not on a pre-vetted list.

As such, it was suggested that I use AES-XTS and key generation via PBKDF2 instead of Argon2id. My XTS VFS implementation is not highly differentiated from the Adiantum VFS, except perhaps that it only imports x/crypto.

Are you interested in an XTS VFS PR (with internal/util.AssertErr added)?

See https://github.com/fido-device-onboard/go-fdo/blob/main/sqlite/xts/xts.go

[ncruces]

Oh a VFS with crypto review, that's exciting!

I'm inclined to say yes, but have a couple of questions.

Would go-fdo use this VFS (possibly vendored), or stay with your fork? Nothing wrong with either option, but I'd rather adopt something that's getting use. Otherwise I might prefer just linking to your repo.

I'd rather keep this repository all under a single license. Since your module is Apache licensed, do you accept relicensing as MIT? I can change the main copyright notice to Copyright (c) 2023 Nuno Cruces and contributors. Other than that I'm satisfied with the CLA implied by GitHub ToS.

Then I have a couple more technical questions which we can leave for later.

An encrypted VFS defines a new file format, which is then set in stone. I'd like to ask how far along are you, if we can still change certain things without breaking your workflow. Things like the pepper, PBKDF2 iterations, and block size.

[ben-krieger]

Oh a VFS with crypto review, that's exciting!

Yes, the review was of the nature of "a dedicated cryptography specialist looked through the code and gave feedback on whether appropriate cryptography was selected and applied correctly." It was very useful, especially in regards to NIST guidance buried deep in documents I've never read. I wish all companies had some sort of standard on this (lower than federal standards) so that it was a transferable stamp of approval.

Would go-fdo use this VFS (possibly vendored), or stay with your fork? Nothing wrong with either option, but I'd rather adopt something that's getting use. Otherwise I might prefer just linking to your repo.

Yes, go-fdo would switch to importing from upstream right away.

I'd rather keep this repository all under a single license. Since your module is Apache licensed, do you accept relicensing as MIT? I can change the main copyright notice to Copyright (c) 2023 Nuno Cruces and contributors. Other than that I'm satisfied with the CLA implied by GitHub ToS.

Let me see if I can just get verbal approval to relicense the contribution. MIT is an approved "outgoing" license for open source contributions and the only reason it was originally licensed Apache was for consistency with the other repos in the fido-device-onboard org (which is controlled by LF Edge).

An encrypted VFS defines a new file format, which is then set in stone. I'd like to ask how far along are you, if we can still change certain things without breaking your workflow. Things like the pepper, PBKDF2 iterations, and block size.

Yes, I expect that the pepper will change if the code is moved. The first services that use this library won't be released until at least the end of the month and likely won't be used in any sort of important scenario before the end of the year, when the library goes through FIDO Alliance conformance testing.

The PBKDF2 parameters were chosen to be above Intel's current requirements so that hopefully they won't need to change for at least 5 years, barring any quantum breakthroughs (and even then, it's a matter of your threat model).

[ncruces]

Excelent!

The PBKDF2 parameters were chosen to be above Intel's current requirements so that hopefully they won't need to change for at least 5 years, barring any quantum breakthroughs (and even then, it's a matter of your threat model).

Params seem fine. The only way I'd want to change PBKDF2 would be if there existed a "standard form" to specify the no. of iters and/or algo within the text key itself (like textkey=pbkdf2:sha512:10000:blarh). Then we'd have a way to evolve as requirements change. If there's none, it can be added later as an additional parameter (like textkeyalgo).

Still, you always have the escape hatch of specifying hexkey and doing PBKDF2 yourself, so ultimately, the format isn't prey to choice of PBKDF2 params, we just need decent defaults.

---

About block size, for Adiantum, I selected 4096 as larger blocks allow NH to amortize the per-block cost of AES and Poly1305, and most databases these days use 4096 byte pages. All else equal, we should always have page size ≥ block size; smaller pages work, but waste work. So I settled on 4096.

If the performance is about the same for 4096+ byte pages using XTS, a 512 block size would make 512 and 1024 pages work better. That said, I'm not sure if smaller pages are super interesting to you. See https://www.sqlite.org/pgszchng2016.html.

I'm just bringing this up as whatever decision sets it in stone, and I haven't studied XTS to know better. 4096 is a safe default, we don't need a thesis to make the call.

Or maybe I'm misunderstanding, and because XTS is narrow block, block size isn't even relevant. I definitely need to read up on this a bit.

[ncruces]

Having read a bit more, yeah, block size (in XTS parlance, sector size) will be an influence, because sectorNum is supposed to be in units of sector size.

OTOH, looking at the construction, having more, smaller sectors should have negligible performance impact: there's one additional AES per sector, but for a 4096-byte SQLite page that's 260 AES ops (with 512 sectors) vs 257 AES ops (with 4096 sectors), which should be negligible.

The standard also doesn't seem to mention any negatives to using a smaller sector size. In particular, if I'm reading it correctly, the bounds in Annex D.4.3 don't seem to depend on sector size (i.e. going with larger sectors won't make larger databases safer).

If so, I think I'd err on the side of 512-byte sectors.

PS: I hope in making these decisions I'm not hopelessly invalidating your crypto review. Or at least, I'd hope the end product would be reviewed, and then I don't make further frivolous changes to it.

[ben-krieger]

The only way I'd want to change PBKDF2 would be if there existed a "standard form" to specify the no. of iters and/or algo within the text key itself (like textkey=pbkdf2:sha512:10000:blarh). Then we'd have a way to evolve as requirements change. If there's none, it can be added later as an additional parameter (like textkeyalgo).

I really like putting the (overriding) kdf parameters in the connection string, because then you don't need to futz with registering a driver under an alternative name and remembering to use that string in sql.Open.

If the performance is about the same for 4096+ byte pages using XTS, a 512 block size would make 512 and 1024 pages work better. That said, I'm not sure if smaller pages are super interesting to you.

I actually selected 4096 because I (mistakenly) thought it had to be for XTS. In the case of go-fdo, the databases are unlikely to ever get extremely large. They're always limited either by "how many non-retired devices does an org own" or "how many (short expiration) entries are currently in this centralized nameserver-like service."

The standard also doesn't seem to mention any negatives to using a smaller sector size. In particular, if I'm reading it correctly, the bounds in Annex D.4.3 don't seem to depend on sector size (i.e. going with larger sectors won't make larger databases safer).

I'll point this out to my reviewer and ask for an opinion in the release at the end of October.

PS: I hope in making these decisions I'm not hopelessly invalidating your crypto review. Or at least, I'd hope the end product would be reviewed, and then I don't make further frivolous changes to it.

Nope! It really shouldn't be an issue. I doubt the block size affects the strength of the security and it shouldn't be a long process in either case.

[ncruces]

Feel free to submit as is, and then we iterate a bit on this. I already have some infra in place to both benchmark and test this (mptest is a decent torture test, and speedtest1 a good benchmark).

[ncruces]

I was looking into this, and I'm considering something more similar to the adiantum package where any HBSH is possible and Adiantum is just the default construction.

So here, any XTS construction would work, and XTS-AES and PBKDF2-HMAC-SHA512 are just the default constructions.

Also, preliminary testing puts this as twice slower than Adiantum ¹, with sector size making little difference (so, acceptable to go with 512).

Footnotes

1. Actually this was measured using boringcrypto, which may or may not be the point. Without boringcrypto, XTS-AES is only about 50% slower than Adiantum. ↩

[ncruces]

See: main...xts
I'd still like to base off a PR from you, if for nothing else to acknowledge the contribution.

I also notice that I need more tests to ensure consistency of the file format (for Adiantum too). The exiting golden test is way too frail, not adequately capturing changes to the block/sector size.

[ben-krieger]

See: main...xts
I'd still like to base off a PR from you, if for nothing else to acknowledge the contribution.

I also notice that I need more tests to ensure consistency of the file format (for Adiantum too). The exiting golden test is way too frail, not adequately capturing changes to the block/sector size.

It definitely makes sense to try to generalize, since there's so much overlap. I'm just waiting on an answer (on my side) to the re-licensing question before I open the PR.

[ncruces]

See: golang/crypto#302

[ben-krieger]

I'll have an answer on the relicensing question tomorrow morning. But, honestly, feel free to go ahead on making a general VFS that can be configured for any KDF and encryption scheme. No acknowledgement needed. I'll be happy to use it.

[ncruces]

I'd still appreciate a code review!

The only functional changes are 512 byte sectors, and the pepper. Everything else stays the same.

The API allows changing the KDF, and use any block cipher that golang.org/x/crypto/xts finds acceptable.