Module: Baseh::Feistel

Defined in:
lib/baseh/feistel.rb

Overview

Balanced Feistel network with cycle walking, spec section 7.3. HMAC-SHA-256 comes from OpenSSL; HMAC and SHA-256 are never implemented by hand (section 7.5).

Constant Summary collapse

TAG = 
"BASEH-FEISTEL-V1".b
MAX_WALKS = 
1000

Class Method Summary collapse

Class Method Details

.bit_length(capacity) ⇒ Object

ceil(log2(capacity)); capacity >= 2 so bits >= 1.



16
17
18
 
# File 'lib/baseh/feistel.rb', line 16

def bit_length(capacity)
  (capacity - 1).bit_length
end

.hmac(key_bytes, message) ⇒ Object 



51
52
53
 
# File 'lib/baseh/feistel.rb', line 51

def hmac(key_bytes, message)
  OpenSSL::HMAC.digest(OpenSSL::Digest.new("sha256"), key_bytes, message)
end

.inverse_permute(value, capacity, profile_id:, key_bytes:, rounds:) ⇒ Object

Inverse permutation with cycle walking.



91
92
93
94
95
 
# File 'lib/baseh/feistel.rb', line 91

def inverse_permute(value, capacity, profile_id:, key_bytes:, rounds:)
  walk(value, capacity, profile_id, key_bytes, rounds) do |left, right, w0, w1|
    run_inverse(left, right, profile_id, key_bytes, rounds, w0, w1)
  end
end

.low_bits(digest, n) ⇒ Object

Low n bits of the HMAC-SHA-256 digest: first ceil(n / 8) bytes read as a big-endian integer and masked with 2^n - 1.



22
23
24
25
26
 
# File 'lib/baseh/feistel.rb', line 22

def low_bits(digest, n)
  byte_count = (n + 7) / 8
  v = digest.byteslice(0, byte_count).unpack("C*").inject(0) { |acc, b| (acc << 8) | b }
  v & ((1 << n) - 1)
end

.permute(value, capacity, profile_id:, key_bytes:, rounds:) ⇒ Object

Forward permutation with cycle walking.



84
85
86
87
88
 
# File 'lib/baseh/feistel.rb', line 84

def permute(value, capacity, profile_id:, key_bytes:, rounds:)
  walk(value, capacity, profile_id, key_bytes, rounds) do |left, right, w0, w1|
    run_rounds(left, right, profile_id, key_bytes, rounds, w0, w1)
  end
end

.round_message(profile_id, round, right, wr) ⇒ Object

Normative round message, spec 7.3 step 4.



41
42
43
44
45
46
47
48
49
 
# File 'lib/baseh/feistel.rb', line 41

def round_message(profile_id, round, right, wr)
  "".b
    .concat(TAG)
    .concat(0.chr(Encoding::BINARY))
    .concat(profile_id)
    .concat(0.chr(Encoding::BINARY))
    .concat(round.chr(Encoding::BINARY))
    .concat(to_be(right, (wr + 7) / 8))
end

.run_inverse(left, right, profile_id, key_bytes, rounds, w0, w1) ⇒ Object 



69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/baseh/feistel.rb', line 69

def run_inverse(left, right, profile_id, key_bytes, rounds, w0, w1)
  (rounds - 1).downto(0) do |i|
    even = i.even?
    wr = even ? w1 : w0
    wl = even ? w0 : w1
    f = low_bits(hmac(key_bytes, round_message(profile_id, i, left, wr)), wl)
    prev_right = left
    prev_left = right ^ f
    left = prev_left
    right = prev_right
  end
  [left, right]
end

.run_rounds(left, right, profile_id, key_bytes, rounds, w0, w1) ⇒ Object 



55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/baseh/feistel.rb', line 55

def run_rounds(left, right, profile_id, key_bytes, rounds, w0, w1)
  rounds.times do |i|
    even = i.even?
    wr = even ? w1 : w0
    wl = even ? w0 : w1
    f = low_bits(hmac(key_bytes, round_message(profile_id, i, right, wr)), wl)
    new_left = right
    new_right = left ^ f
    left = new_left
    right = new_right
  end
  [left, right]
end

.to_be(value, byte_count) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/baseh/feistel.rb', line 28

def to_be(value, byte_count)
  return "".b if byte_count.zero?

  bytes = Array.new(byte_count)
  v = value
  (byte_count - 1).downto(0) do |i|
    bytes[i] = v & 0xff
    v >>= 8
  end
  bytes.pack("C*")
end

.walk(value, capacity, profile_id, key_bytes, rounds) ⇒ Object

Raises:



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/baseh/feistel.rb', line 97

def walk(value, capacity, profile_id, key_bytes, rounds)
  bits = bit_length(capacity)
  w1 = bits / 2
  w0 = bits - w1
  v = value
  MAX_WALKS.times do
    left = v >> w1
    right = v & ((1 << w1) - 1)
    out_left, out_right = yield(left, right, w0, w1)
    combined = (out_left << w1) | out_right
    return combined if combined < capacity

    v = combined
  end
  raise BasehError.new(
    "PERMUTATION_FAILURE",
    "Feistel cycle walking exceeded 1000 iterations",
    safe_for_customer: false
  )
end