A lot of packages are depending on 0.6 api, which requires a crate
that has OS specific TRNG calls. This patch keeps the 0.5 calls
inside the TRNG crate as direct API calls, and migrates to support
a 0.6 api to a patched version of getrandom that supports Xous.
is_efuse_secured() comes from rootkeys, but we don't want
to expose the full rootkeys API to the world.
PDDB already has an approved capability for accessing rootkeys,
so this single API is passed through via the PDDB object here,
allowing other procesess to query it.
change the notification modal to accept the primary message and an
Option of independent text to display as a qrcode
pub fn show_notification(&self, notification: &str, qrtext:Option<&str>) -> Result<(), xous::Error> {}
Probably nobody is really using secret Bases right now, but it's
probably a good idea to lay out all the infrastructure and start
testing it for when it comes time to do it with data that really
matters.
Previous version was v0.0.1.1
New version is v0.0.2.1 (don't ask me why I skipped v0.0.2.0)
The most significant change is that the key derivation for the basis
is now split into two keys. One key is used for the page table ECB
encoding, and a different key is used for the data AES-GCM-SIV encoding.
This is because someone much smarter than me looked at my scheme
and said it is very dangerous to use the same key for two different
types of ciphers. This person is correct, so it had to be rectified.
For the System Basis, the keys are encrypted using the root keys
wrapper API. In this case, we simply create two random keys, one for
the page table, and one for the data region, and wrap them using
the root keys API.
For user secret Basis, the derived keys are sent through HKDF
with two different "info" strings to derive a pair of keys from
a common password.
In case the cryptographer who looked at this is reading along,
note that the basis name is encoded as a fixed-length, 0-padded
record, so, we don't encode the length of the basis in the hash
used to derive the keys. When I explained the scheme I thought
I was using a variable-length basis name to derive the key, but
when I checked the code, it's always 64 bytes long, and bytes
that are not used are 0-padded, so, I think we don't need the
length encoding field.
This doesn't work because the shutdown call destroys all the servers then terminates
the processes. But, the problem is that the processes are still
running, but servers are disappearing. So what you end up with is a
panic when the first message gets delivered to a server that no longer
exists, and then you end up with the program hanging on that panic
because some servers haven't been destroyed/exited yet and are now
just spinning waiting to be scheduled. so the call works in the tidy
kernel test cases but to get it to work on a full OS you'd need to
have a way to put every server into an eternal blocking state before
making the shutdown call (to prevent new messages from being issued
while servers are going away), which is more work than i'm willing to
put into the problem right now.
An edge case was missed where a page which was allocated out of
the FSCB and then later written to disk was having its journal
number set to 0.
The root cause of the logic issue is that the page table itself
does not store a journal number. It's assumed that the page table
is ground truth, and is unjournaled.
As long as the pages don't exist in the FSCB, that's not a problem,
the journal number doesn't matter.
But, let's say this sequence happens:
1. FSCB allocates some free space
2. process takes that free space allocation and commits it to its own page table
3. FSCB update log gets a note that free space is now allocated
4. system reboots
5. process reads its page table from disk. There are no journals associated
with the page table on disk, so, it assigns a journal number of 0 by default.
6. we now have a conflict between the Process' view of the journal age
of that page table entry, and the FSCB's view.
The fix to this is during the page table scan, to check and see if
any candidate pages happen to already exist inside the FSCB. If it does,
then you adopt the latest journal number for that page in the FSCB.
This keeps the two views consistent.
A second bug was also identified while fixing this where the "Random"
order we were hoping for in visiting the free space cache as an
iterator is less random than we had hoped. So, there is a patch to
extract the free pages and pull one random one from the pool, using
entropy coming from the TRNG. This is less computationally efficient,
but at least it is correct and has more transparent properties
than relying on the indeterminism of the HashSet implementation.
- add a "dangerous debug" command that only exists when the feature
"pddbtest" is enabled. The feature can't work on real hardware, but
still, it enables things like dumping of the database and storing
the keys for inspection, so it's isolated in a feature that prevents
the code from being compiled in the first place when it's not selected.
- fix a bug where keys that have zero length aren't being created
correctly. this is a common use case for reserving some space for
data that isn't yet available.
I did observe some PDDB corruption that happened today that looks
ostensibly linked to a record that didn't sync up with the disk,
so, let's be safer and sync everything. We can work on optimizing
performance after correctness is guaranteed.
The problem with the current is_mounted() call is that it blocks
while the PDDB is requesting a password or actively formatting
(otherwise it doesn't block). It's actually just...partially blocking.
That doesn't cut it for libstd-linked system services that need to run but
before the PDDB comes up. In particular, we need to be able to respond
to time queries *somehow*, even before our timezone and offsets are
loaded from the PDDB.
I considered doing a callback mechanism for mounting, but this
is kind of complex and probably not worth it. Instead, a separate
thread that can return the value of a single boolean revealing
the mount state of the PDDB is created, and you can create an
object that's capable of inspecting that boolean.
This will create a 100MiB file in tools/ppdb-images/hosted.bin
(sorry!!) which is persistent storage for hosted mode.
Delete the file if you want to start over from scratch.
It's...pretty brittle. I expect problems, but maybe it will at
least get things moving.
thanks again to Michael Rosenberg for catching this bug and
teaching about about how to use the Subtle/.ct_eq() traits to
implement constant time equality checks.
So you'd like to think that an authenticating cipher would like,
authenticate stuff on decryption. And AES-GCM-SIV was billed as sort
of AES with the pointy edges taken off.
Well, there's always one more bug, actually this time a salamander:
https://eprint.iacr.org/2020/1456.pdf Apparently one can forge
authentication if the attacker can control keys and ciphertext. In the
case of the PDDB I think the attack is largely theoretical, because
you'd have to forge through both the AES-GCM-SIV and the rather
insufficient nonce/murmur hash check on the PTE that locates the page
to be decrypted.
But it's never good to have cryptographic properties depend upon
something that's known to be insufficient, so let's assume the attacker
can simply forge keys and stick some data on the device.
This wouldn't be a problem for confidentiality but it could lead to
the ability to plant evidence, but more importantly could lead to code
paths that were thought to be protected against fuzzing being fuzzed
as you could conceivably create a Basis root record that "checked out"
and then the larger body of the PDDB code would try to chomp on other
pages that are forged, leading to a bigger attack surface. Plus who
knows what else might exist beyond salamanders...
This patch does a "key commitment" on the Basis root page, so that it
is now cryptographically hard to create a salamander. Basically
instead of using the system root key directly in AES-GCM-SIV, the key
goes through a KDF that expands it with yet another nonce plus a bit
of header data. The KDF is SHA512/256 and it expands it twice,
changing one bit in the header data (as prescribed by the paper cited
above), to create a version of the key that is written to disk (the
commitment), and a version of the key that is used to
decrypt/authenticate the AES-GCM-SIV data. Only if both the commitment
and the authentication check out, do we accept a Basis root page as
valid.
I had some concerns about the slightly different structure of the
Basis Root page being detectable, but I have been assured that the key
commitment form and the MAC in AES-GCM-SIV satisfy a property known as
IND$-CPA ("indistinguishable from uniform randomness by a
chosen-plaintext attacker") by Rogaway[1], and, more strongly, "Secure
nonce misuse-resistant authenticated encryption (mrAE)" by Gueron and
Lindell (see appendix for def)[2]. Still, just out of total paranoia
and nothing else, I organize the basis root page such that the MAC is
in the identical location as the other non-committed pages...just in
case there is some mathematical property of the MAC that could be
leveraged to leak info about the existence of the basis root record.
The commitment nonce and sha512/256 result I understand better and
feel pretty comfortable that they are going to be strongly random and
indistinguishable from AES ciphertext.
Thanks to Michael Rosenberg for taking the time to explain all this to
me and to guide me through the process of making the fixes. It is a
major PDDB API-breaking change and I'm glad it's able to be rolled out
before most users have received a device.
[1] https://web.cs.ucdavis.edu/~rogaway/papers/ad.pdf
[2] https://eprint.iacr.org/2015/102
Spent a couple hours chasing down a "bug" which is acutally just
something about how http works that I don't understand. TCP was
working just fine but there is ... idk some sort of keep alive
thing that occupies a socket so the "web server" blocks waiting
for a read. Anyways, I guess the "right" way to solve that would
be to make a multi-threaded web server
OH GOD STOP
right. it's just a demo to prove that TCP works. done.
Open an issue if you find a problem with TCP kthx!
Was doing disjoint loads and stores on an Atomic, really, should
be using the fetch_add, fetch_sub variants to be proper.
Didn't seem to impact anything but maybe there's a future version
of me that high fives me for doing this.
Really clear up the roles and structures of word wrapping.
Significantly, we have now figured out that the word wrapper
should be the word wrapper, and that the text bounds should
be computed by a text bounds computation.
Conflating flexible text bounds with word wrapping makes
the math really hard.
So, the word wrapper always works with a bounding area starting
at 0,0, and will wrap until it hits a Point designated as its
absolute max bounds.
The returned typeset block is referenced to 0,0, and then it
is shifted to the correct location by the rendering function.
This externalizes the computation of the final location plus
the rendering bounds to the outer functions that need to care
about this, thus simplifying the word wrapper significantly.
- check the password with a double-entry on the first boot
- if we see a blank disk, bypass the usual checks and allow the mount
to fail, then, enter the setup routine.
This is one of the truly redeeming features of Rust is that a
major refactor of a core structure like this doesn't leave me
shaking in my boots -- I feel pretty good that this works
since everything passes the CI tests.
The original FS implementation did the "stupid C thing" which
just creates a fixed lenth field and uses null-terminated C
strings. Which actually restricts PDDB entry names to be ascii
as valid UTF-8 can encode single-byte nulls.
The intention was for names to be fully utf-8 compliant, but in
order to do that we have to burn one byte of potential filename
length and encode an overall length field for the name strings.
This change does that, which both makes the code a bit safer
at the expense of losing a character off of the maximum filename
length.
The rootkey enclave actually doesn't check if your password is
correct -- it has no way of knowing because it doesn't know how
the keys will be used. Password checking is delegated to the
requesting process because also the password retry method and
policy depends upon the application, and is a significant amount
of UX plumbing (in fact the rootkeys should have less UX plumbing
than it has right now - this is something to do in the near future).
Add a mechanism in the PDDB to check if a password was entered
correctly, and retry if it isn't. Without this, an incorrect
password would actually trigger a reformat of the PDDB, since
it can't find the system basis structure with a bad password.
takes about 15 minutes to fully initialize a 100MiB PDDB.
time is dominated by the sector erase time (which is fundamental
to the device) and data write rate (also fundamental to the device).
probably should have split this into two commits. oh well.
first part introduces a check to see if root keys are initialized,
and if so, tries to mount the PDDB. If it can't mount, it asks
the user if they want to format it. It also updates the progress
of the fromatting.
the second part redoes the salt once again. After some discussion
SHA512/256 is also resistant to length extension attacsk so we
don't need to use the HMAC technique suggested. Would prefer to
reduce the number of algos to analyze, so we're going to a simple
SHA512/256 hash of the salt/basis name/plaintext password to generate
the salt that goes into the bcrypt routine that ultimately generates
the final key used by the system.
trying to avoid a situation where inspection of the system basis
can lead to conclusions about how old the system "should" be.
This is of course slightly upset by the fact that we need to track `Age`
numbers within keys to implement LRU caching algorithms (coming real soon
now), but at least this decouples the pages' low-level journal entry
count from the age parameter.
based on feedback that the current mechanism is overly complicated
and doesn't add any real security, and it's better to stick with
something simple e.g. just a tried-and-true hash of the basics
was mixing deletions and updates and because they are in arbitrary
order due to the hashset structure, sometimes i'd delete an entry
after it was updated.
this is now found and fixed.
not converting core structures from HashSet to BTreeSet though --
the idea is that in production the mappings should be fully random,
but we are just trying to get reproducibility in hosted mode so
that we can debug some hairy edge cases more easily.
Trying to find a new approach to making dialog boxes that
are cleaner and don't require as much code repetition. Probably
about to go on a long tangent.
the formatting of the listing output is a bit messed up but
i'm too tired and too late to deal with that. at least the
core logic seems functionally correct!
should be able to get away with "just" regenerating the fast space
log only if that's what we've run out of; however, doing that optimization
we run into out of space errors. maybe we need some tuning of the thresholds
for when to reclaim space
it's one of those bugs where you're like oh...right. it's doing
exactly what i told it to. I just told it to do the wrong thing.
Right. If you're updating data at the end of a file, you kind of
don't want to delete the file entirely then do the update.
Fix the code so that in the case of a file extension of a small
key, you're re-inserting the key in its entirety (not just the
updated portion) on the extension case.
Also handled an issue with large files where key extension
should not lead to overwrite of the neighboring data, and put
a cap of the large file limit of 32GiB. See comments for thoughts
on the trade-off of the large file limit versus the allocation
limit of the number of files and the physically realistic
outcomes for the PDDB. Basically as written the PDDB can handle
32GiB files (big enough to hold a blu-ray movie, but not a 4k/8k
movie, uncompressed movies, and/or large virtual machine images),
and can handle creation of files at an average rate of one per
second for 10 years without stop before running out of virtual
memory space.
This isn't "Web scale" as large servers will
definitely require files bigger than 32GiB these days, and
can easily create files at a rate of thousands per second. But,
the PDDB isn't performant enough nor targeted toward large
scale server applications. It should, however, be adequate for
pretty much any user data on a mobile phone if it were recompiled
for a 64-bit target. And, if you needed to scale up to bigger
files and/or more write cycles, the problem can be solved
with some simple memory allocation tricks on the large pool,
but because Precursor only has 16MiB of its own RAM to play
with, we don't implement that as the RAM overhead is both
detrimental and unnecessary at our scale of operation.
us to have a full 64-bit address space upon expansion of the page
number (turns out this is probably important because of the crappy
increment-only allocator used for the large blocks)
need to figure out how to compute if it passes; it of course, breaks
the checksum attached for CI purposes. Maybe it's just a matter
of reading back the data and patching it again -- works things even harder!
also, ran the manual test case on real hardware tonight, after 389 hours
of simulation-only development. happy to report that it worked as expected,
so there's no huge obvious gaps between simulation and reality.
can create/delete dicts, create/delete/update keys.
basis deletion is...just forgetting the password. that's the point,
at least. could maybe extend the basis AAD to include some small
amount of derived data that could be deleted to facilitate basis
deletion...
anyways. next up is...lots and lots of testing.
trying to allocate key indicies within the dictionary pool in a late-binding
way is hard to do in rust, because of various interior mutability problems.
i guess it could be done but it turned out to be easier to pro-actively
track everything and generate them on demand.
allocations are hard in rust. i guess that's why the alloc thing is
still not stable.
see comments in code for more details, but, the Rust borrow checker
found a problem where the virtual to physical map could be concurrently
modified with additional entries during an allocation, so now the code
works on an "look-before-you-leap" allocation basis (where it's assumed
you either ensured sufficient space or allocated as you ran along previously),
versus a "oops we need memory let's stop the world and redo everything
while in the middle of anything" situation. The latter is obviously
more convevient, but, alas, I have to agree with the borrow checker --
probably not the safest way to do things.
this probably isn't new to most other people but this has been
a very visceral exercise of how tricky it is to use Repr(c)
for data layouts in anything but the most trivial data structures.
Unfortunately the Basis root data structure needs to be fairly rich,
so we're playing around with using rkyv to help with the serialization
to disk but I'm also not convinced this is a good idea yet. This
checkpoints commits a "working" rkyv implementation, but I'm not
entirely happy with the notion that rkyv can shuffle around data
bits based on its particular version or decisions in the serializer
crate. I'd like deterministic, repeatable serialization that will
be solid through lots of revs...
- hosted mode uses an awful, horrific hack to simulate FLASH:
it makes a global singleton that is freely mutable. Oh but wait!
that's actually how the hardware behaves. It's up to the code
around the hardware to create those primitives. So, maybe it makes
sense that the simulation model for the hardware is terribly
unsafe and unprotected.
- the format routine at least doesn't crash and creates some
semblance of a result that looks right-ish. Need to write a
utility that helps to explore the "disk image" so we can
understand what's going on.
- TrngPool is going to be more efficient if I have a single pool that's
shared among all the functions of the PDDB. It's split out into its own
object that is refcell-counted.
- Trying to make the Basis handle encryption and decryption with iterator
traits. Let's see how that works out.
- reworked fast space allocation
- shifted order of events around slightly
- formatting is now using "generic" calls to create
the free space structures instead of bespoke single-use calls
left off at getting the system basis written. need to rework
the data structure to be orthogonal with the page table remap
on a page-by-page basis. have to think about it a bit...