| 1 | package crypto |
| 2 | |
| 3 | import ( |
| 4 | "crypto/sha256" |
| 5 | "errors" |
| 6 | "strings" |
| 7 | ) |
| 8 | |
| 9 | // Alphabet is Crockford's Base32 set: no I, L, O or U. |
| 10 | // |
| 11 | // Case-insensitive, and decoding maps O to 0 and I and L to 1 — the exact |
| 12 | // confusions humans and OCR make reading aged paper, which is what these codes |
| 13 | // are printed on. |
| 14 | const Alphabet = "0123456789ABCDEFGHJKMNPQRSTVWXYZ" |
| 15 | |
| 16 | // The printed credential form: tag(2) || data(26) || checksum(4). |
| 17 | const ( |
| 18 | TagAccountKey = "A1" |
| 19 | TagRecovery = "C1" |
| 20 | dataSymbols = 26 |
| 21 | checkSymbols = 4 |
| 22 | codeSymbols = 2 + dataSymbols + checkSymbols |
| 23 | ) |
| 24 | |
| 25 | var ( |
| 26 | ErrAlphabet = errors.New("crypto: character outside the Crockford alphabet") |
| 27 | ErrLength = errors.New("crypto: wrong number of symbols") |
| 28 | ErrPadding = errors.New("crypto: non-zero pad bits in the final symbol") |
| 29 | ErrChecksum = errors.New("crypto: checksum does not match") |
| 30 | ErrTag = errors.New("crypto: wrong tag") |
| 31 | ) |
| 32 | |
| 33 | // symbolValue applies the case folding and the O/I/L substitutions, returning |
| 34 | // -1 for anything outside the alphabet. |
| 35 | func symbolValue(c byte) int { |
| 36 | if c >= 'a' && c <= 'z' { |
| 37 | c -= 'a' - 'A' |
| 38 | } |
| 39 | switch c { |
| 40 | case 'O': |
| 41 | c = '0' |
| 42 | case 'I', 'L': |
| 43 | c = '1' |
| 44 | } |
| 45 | if i := strings.IndexByte(Alphabet, c); i >= 0 { |
| 46 | return i |
| 47 | } |
| 48 | return -1 |
| 49 | } |
| 50 | |
| 51 | // Normalize strips hyphens and whitespace, uppercases, and applies the O/I/L |
| 52 | // mappings. The two-character tag survives it unchanged, so callers normalise |
| 53 | // first and match the tag afterwards. |
| 54 | func Normalize(s string) (string, error) { |
| 55 | var b strings.Builder |
| 56 | for i := 0; i < len(s); i++ { |
| 57 | c := s[i] |
| 58 | if c == '-' || c == ' ' || c == '\t' || c == '\n' || c == '\r' { |
| 59 | continue |
| 60 | } |
| 61 | v := symbolValue(c) |
| 62 | if v < 0 { |
| 63 | return "", ErrAlphabet |
| 64 | } |
| 65 | b.WriteByte(Alphabet[v]) |
| 66 | } |
| 67 | return b.String(), nil |
| 68 | } |
| 69 | |
| 70 | // Base32Encode packs bytes MSB-first and left-aligned, so 16 bytes become 26 |
| 71 | // symbols whose last one carries two zero pad bits. |
| 72 | // |
| 73 | // Byte packing rather than Crockford's big-integer form: no language needs a |
| 74 | // bignum to read a recovery code, which matters most in the browser, where the |
| 75 | // JS modules are capped at 300 lines by test. |
| 76 | func Base32Encode(in []byte) string { |
| 77 | n := (len(in)*8 + 4) / 5 |
| 78 | out := make([]byte, n) |
| 79 | for i := 0; i < n; i++ { |
| 80 | bit := i * 5 |
| 81 | by, off := bit/8, bit%8 |
| 82 | v := uint32(in[by]) << 8 |
| 83 | if by+1 < len(in) { |
| 84 | v |= uint32(in[by+1]) |
| 85 | } |
| 86 | out[i] = Alphabet[(v>>(11-off))&0x1f] |
| 87 | } |
| 88 | return string(out) |
| 89 | } |
| 90 | |
| 91 | // Base32Decode is strict: it rejects a non-zero pad in the final symbol, so |
| 92 | // every value has exactly one encoding. Without that two different strings |
| 93 | // decode to one key, and the checksum stops meaning what it says. |
| 94 | func Base32Decode(sym string, nbytes int) ([]byte, error) { |
| 95 | if len(sym) != (nbytes*8+4)/5 { |
| 96 | return nil, ErrLength |
| 97 | } |
| 98 | out := make([]byte, 0, nbytes) |
| 99 | var acc uint32 |
| 100 | var bits int |
| 101 | for i := 0; i < len(sym); i++ { |
| 102 | v := symbolValue(sym[i]) |
| 103 | if v < 0 { |
| 104 | return nil, ErrAlphabet |
| 105 | } |
| 106 | acc = acc<<5 | uint32(v) |
| 107 | bits += 5 |
| 108 | if bits >= 8 { |
| 109 | bits -= 8 |
| 110 | out = append(out, byte(acc>>bits)) |
| 111 | } |
| 112 | } |
| 113 | if acc&((1<<bits)-1) != 0 { |
| 114 | return nil, ErrPadding |
| 115 | } |
| 116 | return out, nil |
| 117 | } |
| 118 | |
| 119 | // Checksum20 is the first 20 bits, MSB-first, of SHA-256 over the raw payload |
| 120 | // bytes — not over the string. Twenty bits is enough to catch a mistyped |
| 121 | // character and small enough to fit four symbols on a printed line. |
| 122 | func Checksum20(payload []byte) uint32 { |
| 123 | d := sha256.Sum256(payload) |
| 124 | return uint32(d[0])<<12 | uint32(d[1])<<4 | uint32(d[2])>>4 |
| 125 | } |
| 126 | |
| 127 | func checksumSymbols(c uint32) string { |
| 128 | out := make([]byte, checkSymbols) |
| 129 | for i := 0; i < checkSymbols; i++ { |
| 130 | out[i] = Alphabet[(c>>(15-5*i))&0x1f] |
| 131 | } |
| 132 | return string(out) |
| 133 | } |
| 134 | |
| 135 | // NormalizedCode renders the 32-character canonical form: tag, data, checksum. |
| 136 | func NormalizedCode(tag string, payload []byte) string { |
| 137 | return tag + Base32Encode(payload) + checksumSymbols(Checksum20(payload)) |
| 138 | } |
| 139 | |
| 140 | // FormatCode renders what actually goes on the paper: |
| 141 | // TAG-XXXXX-XXXXX-XXXXX-XXXXX-XXXXX-XXXXX. |
| 142 | func FormatCode(tag string, payload []byte) string { |
| 143 | norm := NormalizedCode(tag, payload) |
| 144 | var b strings.Builder |
| 145 | b.WriteString(tag) |
| 146 | for i := 2; i < len(norm); i++ { |
| 147 | if (i-2)%5 == 0 { |
| 148 | b.WriteByte('-') |
| 149 | } |
| 150 | b.WriteByte(norm[i]) |
| 151 | } |
| 152 | return b.String() |
| 153 | } |
| 154 | |
| 155 | // ParseCode normalises, checks the tag and the checksum, and returns the |
| 156 | // payload. A checksum failure is where the caller reaches for RepairCode. |
| 157 | func ParseCode(tag, s string) ([]byte, error) { |
| 158 | norm, err := Normalize(s) |
| 159 | if err != nil { |
| 160 | return nil, err |
| 161 | } |
| 162 | return parseNormalized(tag, norm) |
| 163 | } |
| 164 | |
| 165 | func parseNormalized(tag, norm string) ([]byte, error) { |
| 166 | if len(norm) != codeSymbols { |
| 167 | return nil, ErrLength |
| 168 | } |
| 169 | if norm[:2] != tag { |
| 170 | return nil, ErrTag |
| 171 | } |
| 172 | payload, err := Base32Decode(norm[2:2+dataSymbols], 16) |
| 173 | if err != nil { |
| 174 | return nil, err |
| 175 | } |
| 176 | if checksumSymbols(Checksum20(payload)) != norm[2+dataSymbols:] { |
| 177 | return nil, ErrChecksum |
| 178 | } |
| 179 | return payload, nil |
| 180 | } |
| 181 | |
| 182 | // RepairCode brute-forces every single-character substitution over the 30 |
| 183 | // payload positions — about a thousand candidates — and returns every one |
| 184 | // whose checksum passes, in position-then-alphabet order. |
| 185 | // |
| 186 | // It deliberately does not pick a winner. Twenty bits collides roughly once in |
| 187 | // eleven hundred attempts, so the caller tries each candidate against the KCV, |
| 188 | // which does not collide. Choosing here would sometimes choose wrong and |
| 189 | // silently hand back the wrong key. |
| 190 | func RepairCode(tag, s string) ([]string, error) { |
| 191 | norm, err := Normalize(s) |
| 192 | if err != nil { |
| 193 | return nil, err |
| 194 | } |
| 195 | if len(norm) != codeSymbols { |
| 196 | return nil, ErrLength |
| 197 | } |
| 198 | |
| 199 | var out []string |
| 200 | buf := []byte(norm) |
| 201 | for pos := 2; pos < codeSymbols; pos++ { |
| 202 | orig := buf[pos] |
| 203 | for i := 0; i < len(Alphabet); i++ { |
| 204 | if Alphabet[i] == orig { |
| 205 | continue |
| 206 | } |
| 207 | buf[pos] = Alphabet[i] |
| 208 | if _, err := parseNormalized(tag, string(buf)); err == nil { |
| 209 | out = append(out, string(buf)) |
| 210 | } |
| 211 | } |
| 212 | buf[pos] = orig |
| 213 | } |
| 214 | return out, nil |
| 215 | } |
| 216 | |
amadan