Spiral Ratchet
Backwards-secret deterministic versioning
Every node in the private tree is encrypted with a different key. This is done randomly for child nodes (along the y-axis), and deterministically with a cryptographic ratchet for increasing versions (along the z-axis).
The basic idea for cryptographic ratchets is that repeatedly hashing a value creates a kind of backwards-secret clock. When you start watching the clock, you can generate the hash for any arbitrary future steps, but not steps from prior to observation since that requires computing the SHA3 preimage.
Source: https://www.quora.com/What-is-exactly-backward-secrecy-property-in-cryptography-attribute-based-encryption
SHA3-256 is native to the WebCypto API, is a very fast operation, and commonly hardware accelerated. Anecdotally, Firefox on an Apple M1 completes each SHA3 ~3μs (100k/300ms). The problem with a single hash counter is threefold:
1. The root of the unencrypted tree updates with with every atomic operation, and thus accrues a lot of changes
2. An actor may be many months since their last sync, and need to fast forward their clock by some huge number of elements
3. Seeking ahead by 100ks or millions takes very noticeable time
4. It should be cheaper to fast forward than for an attacker to build a large history
We still want small step changes to be very fast, but also be able to deterministically tune how quickly we jump ahead, without revealing previous counter hashes, while maintaining the same security properties as a single ratchet counter.
Positional counting does exactly this in the most common numeral systems. Our design involves three positions, two of which are bounded. We call these the large (or epoch), medium, and small numbers.
Positionally this looks like:
large medium small
l*2^16 m*2^8 s*2^0
l = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
m = 0x5d58264a09dce1f2676e729d0ea1db4bf90b9be463d7fc1aa9b43b358e514599
s = 0xc8633540cabdf591e07918a2595964cc1b692d0f9392f079f2f110c08b67c6f4
The large and small are bounded at 256 elements. We achieve this by keeping a record of the max bound of these numbers. This is found by hashing that number 255 times (0 is the unchanged value). As we increment each number by taking its SHA3-256, we check if it matches the max bound. If it does, we increment the next-highest value, and reset the smaller values.
The metaphor is a spiral. You can ratchet one at a time, or deterministically skip to the start of the next ring in the spiral.
https://commons.wikimedia.org/wiki/File:Ulam_spiral_howto_all_numbers.svg
data SpiralRatchet = SpiralRatchet
{ large :: Digest SHA3_256
, medium :: Digest SHA3_256
, mediumMax :: Digest SHA3_256
, small :: Digest SHA3_256
, smallMax :: Digest SHA3_256
}
exampleSR = SpiralRatchet
{ large = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
, medium = 0x5d58264a09dce1f2676e729d0ea1db4bf90b9be463d7fc1aa9b43b358e514599
, mediumMax = 0x5aae7b2b881d21863292a1556eafd2a3b21527f64f33c6fcc2beaa9d9cf1fe5f
, small = 0xc8633540cabdf591e07918a2595964cc1b692d0f9392f079f2f110c08b67c6f4
, smallMax = 0xb95c5d8851daff6204eb227f56d8c6af1c11a80d46d17eb0aa219a9d2ec109af
}
Incrementing a larger value resets all smaller values. This is done by taking the SHA3-256 of the (one's) complement. This cascades from larger to all smaller positions.
Please note that JavaScript's basic inverse function behaves unexpectedly. The
~ operator casts values to their one's compliment integer. This means that ~0b11 !== 0b00, but rather ~0b11 === -4. -4 can not be directly expressed in JS binary, since it interprets binary notation as being a natural number only (rather than its two's compliment). To keep this from happening, use a toggle mask of equal length: val ^ b1111....The small and medium values are base-256. This means that the first position increments in ones (2^0), the second position increments in 256s (2^8), and the third position by 65,536s (2^16). Looking at a triple does not admit which number it is, only which number relative to the max bounds of the medium and small numbers. It is not possible to determine which of epoch (large number) you are in. Here is an example of a spiral ratchet being constructed from a seed value.
seed = 0x600b56e66b7d12e08fd58544d7c811db0063d7aa467a1f6be39990fed0ca5b33
large = sha3_256 seed -- e.g. 0x8e2023cc8b9b279c5f6eb03938abf935dde93be9bfdc006a0f570535fda82ef8
mediumSeed = sha3_256 $ Binary.complement seed
medium = sha3_256 mediumSeed
mediumMax = iterate sha3_256 medium !! 255
smallSeed = sha3_256 $ Binary.complement mediumSeed
small = sha3_256 smallSeed
smallMax = iterate sha3_256 small !! 256
Here is how to increment the ratchet by one:
-- large (0..), medium (0-255), small (0-255)
toVersionHash :: SHA3_256
toVersionHash SpiralRatchet {..} = sha3_256 (large `xor` medium `xor` small)
advance :: SpiralRatchet -> SpiralRatchet
advance SpiralRatchet {..} =
case (nextSmall == smallCeiling, nextMedium == mediumCeiling) of
(False, _) -> advanceSmall
(True, False) -> advanceMedium
(_, True) -> advanceLarge
(False, True) -> error "Not possible"
where
nextSmall = sha3_256 small
nextMedium = sha3_256 medium
advanceSmall :: SpiralRatchet
advanceSmall = SpiralRatchet {small = nextSmall, ..}
advanceMedium :: SpiralRatchet
advanceMedium =
let
resetSmall = sha3_256 $ compliment nextMedium
resetMedium = sha3_256 $ compliment nextLarge
in
SpiralRatchet
{ large = large
, medium = nextMedium
, mediumCeil = recursiveSHA 256 nextMedium
, small = resetSmall
, smallCeil = recursiveSHA 256 resetSmall
}
advanceLarge :: SpiralRatchet
advanceLarge =
let
nextLarge = sha3_256 large
resetMedium = sha3_256 $ compliment nextLarge
resetSmall = sha3_256 $ compliment resetMedium
in
SpiralRatchet
{ large = nextLarge
, medium = resetMedium
, mediumCeil = recursiveSHA 256 resetMedium
, small = resetSmall
, smallCeil = recursiveSHA 256 resetSmall
}
Many files will have few revisions. To prevent leaking this information, we take advantage of the fact that the setup starts at a random point in the ratchet:
setup :: SpiralRatchet
setup = do
largePre <- random -- ratchet seed
mediumSkip <- randomBetween 0 254
smallSkip <- randomBetween 0 254
let
large = sha3_256 largePre
mediumPre = sha3_256 $ compliment largePre
medium = recursiveSHA mediumSkip mediumPre
mediumMax = recursiveSHA 255 mediumPre
smallPre = sha3_256 $ compliment mediumPre
small = recursiveSHA smallSkip smallPre
smallMax = recursiveSHA 255 smallPre
return SpiralRatchet {..}
The spiral ratchet is byte aligned, which makes for straightforward binary serialization. The usual case is to increment the smallest digit, followed by the next largest, and so on. As such, it is more efficient to encode as little-endian:
serialize SpiralRatchet {..} =
[small, smallMax, medium, mediumMax, large] -- [Digest AES256]
|> fmap toByteString -- [ByteString]
|> concat -- ByteString
We then flag the encoding. The default encoding is base64URL-unpadded (signified with
u) and SHA-256 (0x16), so:uFuGha07m3EEs2-3_oP14Sy4aJPztz0bBdnPFUqQw9Y2lsqQoKhJ2BAjcXrxSTFLmbb2lICSq12ac14hIV6rI43byk2vrXaM6eW4K8ucJWLJeSz-EObY3VF7Nbat_rDY5tz4Xt-J--WPF_o3LSf85kpdL8PsNmDNlpYXk2Bzte2tcL_DdgV4bhUNSA20PKLKisazdR-Bq2YaxWPhb85RgzFs
There is nothing special about a 3xAES256 spiral ratchet. The digits don't even need to be the same length or hashing algorithm (though this is strongly recommended to lower cognitive overhead). It is "merely" a positional number system implemented with hashing to avoid unary counting overhead. To provide some consistency, here is the formula for constructing a spiral ratchet up to
n digits:- An unbounded hash to represent the largest digit (or "epoch")
- Each digit is accompanied by its ceiling, to indicate how much room is left
- This may also be implemented as the number of remaining increments
- A hashing algorithm
data SpiralDigit algo = SpiralDigit
{ current :: Digest algo
, max :: Digest algo
}
data GeneralSpiralRatchet algo = GSR
{ epoch :: Digest algo
, digits :: [SpiralDigit]
}
Here, the
digits field correlates the index with the digit exponent. In the familiar base 10, index 0 = 10^0 = 1s-digit, index 5 = 10^5 = 100,000s-digit.Last modified 1yr ago