---
title: "Hashing, keyed digests, key derivation and Merkle trees"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Hashing, keyed digests, key derivation and Merkle trees}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
# the vignette runs in full in GitHub CI and for the package tarball (NOT_CRAN), on r-universe
# (MY_UNIVERSE), on the package website (IN_PKGDOWN) and in an interactive session; when CRAN
# re-builds it in its check, none of these is set and only this chunk runs
if (!interactive() && !any(nzchar(Sys.getenv(c("NOT_CRAN", "MY_UNIVERSE", "IN_PKGDOWN"))))) {
  knitr::knit_exit()
}
# the one-time index record of this vignette stays out of the reader's configuration directory
options(rmoriebricklayer.xmssidxfile = tempfile())
knitr::opts_chunk$set(collapse = TRUE, comment = "#>")
library(rmoriebricklayer)
```

Everything a capsule pins is pinned by a digest. This vignette covers the hashing
primitives, how to compare digests safely, how to derive a key from a passphrase, how to
get randomness, and how a Merkle tree lets a large file be pinned and partially verified.

## Digests of text and files

```{r hashing-and-integrity-digests}
csha256("hello capsule")
csha512("hello capsule")
cblake2b("hello capsule")
ccrc32("hello capsule")
```

Files are hashed in blocks, so a multi-gigabyte file does not need to fit in memory:

```{r hashing-and-integrity-files}
f <- tempfile()
writeLines("hello capsule", f)
sha256file(f)
sha512file(f)
crc32file(f)

before <- sha256file(f)
writeLines("hello capsule (edited)", f)
sha256file(f) == before
```

CRC-32 is a checksum, not a cryptographic hash: it detects accidental corruption and
nothing more. SHA-256 and SHA-512 (FIPS 180-4) and BLAKE2b are collision-resistant;
`vrfsha256()` checks a file against a pinned digest.

## Digests of R objects

`dgstobj()` serialises an object canonically and hashes the bytes, so attributes,
names and types are part of the identity:

```{r hashing-and-integrity-objects}
dgstobj(list(a = 1L, b = "x"))
identical(dgstobj(1:10), dgstobj(1:10))
dgstobj(1:10) == dgstobj(1:11)
dgstobj(matrix(1:6, nrow = 2)) == dgstobj(1:6)   # dimensions count
dgstobj(data.frame(x = 1:3))
```

## Keyed digests and constant-time comparison

An HMAC (RFC 2104) is a digest that only the holder of the key can produce, so a manifest
cannot be re-signed without the key:

```{r hashing-and-integrity-hmac}
chmac("Jefe", "what do ya want for nothing?")   # RFC 4231 test case 2
chmac("key-a", "manifest")
chmac("key-b", "manifest")
```

**Never compare a tag with `==`.** A string comparison stops at the first differing
character, so its running time tells an attacker how many leading characters were right.
`cdgsteq()` compares every byte regardless and returns `FALSE` for a length
mismatch without erroring:

```{r hashing-and-integrity-ct}
tag <- chmac("k", "m")
cdgsteq(tag, chmac("k", "m"))
cdgsteq(tag, chmac("k", "tampered"))
cdgsteq(tag, "too-short")
```

## Deriving a key from a passphrase

A passphrase is not a key: it is short, low-entropy and chosen by a person. PBKDF2 (RFC
8018) stretches it with a salt and an iteration count that makes each guess expensive:

```{r hashing-and-integrity-pbkdf2}
drvkey("password", "salt", iter = 1)     # the published test vector
identical(drvkey("pw", "s", 1000), drvkey("pw", "s", 1000))
drvkey("pw", "salt-a", 1000) == drvkey("pw", "salt-b", 1000)
```

The salt must be random and stored beside the ciphertext or signature; the default of
100,000 iterations is the floor for interactive use. A derived key signs a manifest
symmetrically:

```{r hashing-and-integrity-pbkdf2-sign}
salt <- paste(format(rndbytes(16)), collapse = "")
key <- drvkey("correct horse battery staple", salt)
sig <- cpssign("manifest-digest", key, scheme = "hmac")
cpsvrf("manifest-digest", sig, key)
```

## Randomness

`rndbytes()` draws from the operating system (`getrandom` or `/dev/urandom` on Unix,
`RtlGenRandom` on Windows) and does
**not** consume R's seeded stream, so a reproducible analysis is unaffected by key
generation happening beside it:

```{r hashing-and-integrity-random}
set.seed(1)
a <- stats::runif(1)
set.seed(1)
invisible(rndbytes(32))
identical(stats::runif(1), a)
```

For tests that need reproducible "random" bytes, the package's AES-256 CTR_DRBG (SP
800-90A) gives the same bytes from the same seed, exactly as NIST's known-answer files use
it; a personalization string separates streams:

```{r hashing-and-integrity-drbg}
d <- drbgnew(as.raw(0:47))
drbggen(d, 16)
a <- drbgnew(as.raw(1:48), person = charToRaw("session 1"))
b <- drbgnew(as.raw(1:48), person = charToRaw("session 2"))
identical(drbggen(a, 16), drbggen(b, 16))
```

## Merkle trees: pin a large file, verify a piece

A Merkle tree hashes a file in chunks, then hashes pairs of digests up to one root. The root
pins the whole file; a *proof* of `log2(n)` digests shows that one chunk belongs without
holding the others, and a diff of the leaves names exactly which chunk changed.

```{r hashing-and-integrity-merkle}
chunks <- c("row1,row2", "row3,row4", "row5,row6", "row7,row8")
root <- mrkroot(chunks)
root

before <- mrklvs(chunks)
after <- mrklvs(c(chunks[1:2], "row5,row6-EDITED", chunks[4]))
which(before != after)

pr <- mrkprf(chunks, 3)
mrkvrf(chunks[3], pr, root)
mrkvrf("row5,row6-EDITED", pr, root)
```

`chnkfile()` splits a real file into fixed-size chunks that concatenate back to its bytes:

```{r hashing-and-integrity-chunkfile}
p <- tempfile()
writeLines(rep("some capsule content", 50), p)
ch <- chnkfile(p, chnkbytes = 128)
length(ch)
mrkroot(ch)
identical(unlist(ch), readBin(p, "raw", file.size(p)))
```

`cpsbndl()` pins each data file by one whole-file digest (`sha256file()`); the
Merkle tree is for pinning the parts of a large file, so a mismatch identifies which part of it
changed rather than only that something did.

## How these implementations are checked

The digests are compared with OpenSSL at every block boundary, run against the NIST ACVP
sets for SHA-3, SHAKE, HMAC and PBKDF2, and fuzzed differentially against OpenSSL 3.5. The
keyed-digest comparison and PBKDF2 run under valgrind with the key marked undefined to prove
their timing does not depend on it, and dudect measures the comparison and PBKDF2 on real
CPUs.


## Pinning a community's copy of a table

Ownership and control of data, in the sense of the First Nations principles of OCAP,
include knowing that a copy has not been altered. A digest of the table and a Merkle root
over its rows let a community check its copy, and check single rows without the rest:

```{r hashing-and-integrity-indigenous-hash}
d <- indiex("suicide")
dgstobj(d)
rows <- apply(d, 1, paste, collapse = ",")
root <- mrkroot(rows)
proof <- mrkprf(rows, 3)
mrkvrf(rows[3], proof, root)
```

## The pinned table in a picture

The digests above pin this table. Its estimates and intervals for the first measure are drawn
here: a reader who verifies the digest is looking at exactly these numbers.

```{r hashing-and-integrity-hashed-table-plot, fig.width = 7, fig.height = 4.5}
ci_plot <- function(t, lab, main) {
  o <- order(t$estimate)
  t <- t[o, ]
  y <- seq_len(nrow(t))
  op <- par(mar = c(4, 10, 3, 1))
  on.exit(par(op))
  plot(t$estimate, y, xlim = range(t$lower, t$upper, na.rm = TRUE), yaxt = "n", pch = 19,
       col = blpal()[1], xlab = "estimate and 95% interval", ylab = "", main = main)
  segments(t$lower, y, t$upper, y, col = blpal()[1])
  axis(2, y, lab[o], las = 1, cex.axis = 0.7)
}
t1 <- d[d$measure == d$measure[1], ]
ci_plot(t1, paste(t1$group, t1$age), t1$measure[1])
```