~seirdy/moac

ref: c7e44a97bfc2392ebc5256b8cddc73c89d7ac4b3 moac/givens.go -rw-r--r-- 7.0 KiB
c7e44a97Rohan Kumar Fix: remove ineffective code (from mutesting) 8 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
package moac

import (
	"errors"
	"fmt"
	"log"
	"math"

	"git.sr.ht/~seirdy/moac/v2/entropy"
	"git.sr.ht/~seirdy/moac/v2/internal/bounds"
)

// Givens holds the "given" values used to compute password strength.
// These values are all physical quantities, measured using standard SI units.
type Givens struct {
	Password         string
	Entropy          float64
	Energy           float64
	Mass             float64 // mass used to build a computer or convert to energy
	Time             float64 // Duration of the attack, in seconds.
	Temperature      float64 // Duration of the attack, in seconds.
	EnergyPerGuess   float64
	Power            float64
	GuessesPerSecond float64
}

const (
	// C is the speed of light in a vacuum, m/s.
	C = 299792458
	// G is the gravitation constant, m^3/kg/s^2.
	G = 6.67408e-11
	// Hubble is Hubble's Constant, hertz.
	Hubble = 2.2e-18
	// UTemp is a low estimate for the temperature of cosmic background radiation, kelvin.
	UTemp = 2.7
	// Boltzmann is Boltzmann's constant, J/K.
	Boltzmann = 1.3806503e-23
	// Planck is Planck's Constant, J*s.
	Planck = 6.62607015e-35

	// UMass is the mass of the observable universe.
	UMass = C * C * C / (2 * G * Hubble)
	// Bremermann is Bremermann's limit.
	Bremermann = C * C / Planck

	// DefaultEntropy is the number of bits of entropy to target if no target entropy is provided.
	DefaultEntropy = 256
)

// landauer outputs the Landauer Limit.
// See https://en.wikipedia.org/wiki/Landauer%27s_principle
func landauer(temp float64) float64 {
	return Boltzmann * temp * math.Ln2
}

// populateDefaults fills in default values for entropy calculation if not provided.
func (givens *Givens) populateDefaults() {
	if givens.Energy+givens.Mass == 0 {
		// mass of the observable universe
		givens.Mass = UMass
	}

	if givens.Entropy == 0 {
		if givens.Mass+givens.EnergyPerGuess == 0 {
			givens.Entropy = DefaultEntropy
		}
	}

	if givens.Temperature == 0 {
		givens.Temperature = UTemp
	}

	if givens.EnergyPerGuess == 0 {
		// maybe put something more elaborate here given different constraints
		givens.EnergyPerGuess = landauer(givens.Temperature)
	}
}

func setBottleneck(given *float64, computedValues ...float64) {
	for _, computedValue := range computedValues {
		if *given == 0 || (computedValue > 0 && computedValue < *given) {
			*given = computedValue
		}
	}
}

func (givens *Givens) calculatePower() {
	var (
		powerFromComputationSpeed = givens.GuessesPerSecond * givens.EnergyPerGuess
		powerFromEnergy           = givens.Energy / givens.Time
	)

	setBottleneck(&givens.Power, powerFromComputationSpeed, powerFromEnergy)
}

func (givens *Givens) calculateGPS() {
	var (
		bremermannGPS = Bremermann * givens.Mass
		powerGPS      = givens.Power / givens.EnergyPerGuess
	)

	setBottleneck(&givens.GuessesPerSecond, bremermannGPS, powerGPS)
}

func (givens *Givens) calculateEnergy() {
	var (
		energyFromMass  = givens.Mass * C * C
		energyFromPower = givens.Power * givens.Time
	)

	setBottleneck(&givens.Energy, energyFromMass, energyFromPower)
}

// Errors for missing physical values that are required to compute desired values.
var (
	ErrMissingValue = errors.New("not enough given values")
	ErrMissingEMT   = fmt.Errorf("%w: missing energy, mass, and/or time", ErrMissingValue)
	ErrMissingPE    = fmt.Errorf("%w: missing password and/or entropy", ErrMissingValue)
)

// validate ensures that the values in Givens aren't physically impossible.
func (givens *Givens) validate() error {
	if err := bounds.ValidateTemperature(givens.Temperature); err != nil {
		return fmt.Errorf("invalid temperature: %w", err)
	}

	if err := bounds.NonNegative(
		givens.Energy, givens.Mass, givens.Power, givens.Time); err != nil {
		return fmt.Errorf("physical values can't be negative: %w", err)
	}

	return nil
}

// Populate will solve for entropy, guesses per second, and energy if they aren't given.
// If they are given, it updates them if the computed value is a greater bottleneck than the given value.
func (givens *Givens) Populate() error {
	givens.populateDefaults()

	if err := givens.validate(); err != nil {
		return fmt.Errorf("invalid givens: %w", err)
	}

	if givens.Password != "" {
		setBottleneck(&givens.Entropy, entropy.Entropy(givens.Password))
	}

	givens.calculatePower()

	givens.calculateGPS()

	givens.calculateEnergy()

	if givens.Energy == 0 && givens.Time == 0 {
		log.Panic("populating givens: failed to populate energy and time")
	}

	return nil
}

// BruteForceability computes the liklihood that a password will be
// brute-forced given the contstraints in givens.
// if 0 < BruteForceability <= 1, it represents the probability that the
// password can be brute-forced.
// if BruteForceability > 1, it represents the number of times a password
// can be brute-forced with certainty.
func (givens *Givens) BruteForceability() (float64, error) {
	if err := givens.Populate(); err != nil {
		return 0, fmt.Errorf("can't compute BruteForceability: %w", err)
	}

	if givens.Entropy+givens.Time == 0 {
		return 0, fmt.Errorf("missing entropy: %w", ErrMissingPE)
	}

	computedBruteForceability := computeBruteForceability(givens)

	// if bruteforceability isn't valid, we have a bug.
	if computedBruteForceability == 0 || math.IsNaN(computedBruteForceability) {
		log.Panicf("failed to compute BruteForceability: got %v", computedBruteForceability)
	}

	return computedBruteForceability, nil
}

// BruteForceabilityQuantum is equivalent to BruteForceability, but accounts for
// quantum computers that use Grover's Algorithm.
func (givens *Givens) BruteForceabilityQuantum() (float64, error) {
	if err := givens.Populate(); err != nil {
		return 0, fmt.Errorf("can't calculate BruteForceabilityQuantum: %w", err)
	}

	givensQuantum := givens

	// Grover's Algo makes quantum computers as efficient as classical computers at double the entropy.
	givensQuantum.Entropy /= 2

	return givensQuantum.BruteForceability()
}

func computeBruteForceability(givens *Givens) float64 {
	var (
		guessesRequired = math.Exp2(givens.Entropy)
		energyBound     = givens.Energy / (guessesRequired * givens.EnergyPerGuess)
	)

	if givens.Time > 0 {
		timeBound := givens.Time * givens.GuessesPerSecond / guessesRequired

		return math.Min(energyBound, timeBound)
	}

	return energyBound
}

// MinEntropy calculates the maximum password entropy that the MOAC can certainly brute-force.
// Passwords need an entropy greater than this to have a chance of not being guessed.
func (givens *Givens) MinEntropy() (entropyNeeded float64, err error) {
	if err := givens.Populate(); err != nil {
		return 0, fmt.Errorf("can't compute MinEntropy: %w", err)
	}

	energyBound := math.Log2(givens.Energy / givens.EnergyPerGuess)

	if givens.Time > 0 {
		timeBound := math.Log2(givens.Time * givens.GuessesPerSecond)

		return math.Min(energyBound, timeBound), nil
	}

	return energyBound, nil
}

// MinEntropyQuantum is equivalent to MinEntropy, but accounts for
// quantum computers that use Grover's Algorithm.
func (givens *Givens) MinEntropyQuantum() (entropyNeeded float64, err error) {
	minEntropyNonQuantum, err := givens.MinEntropy()

	return minEntropyNonQuantum * 2, err
}