Repository navigation
Expand file tree
/
Copy pathbase.frg
More file actions
314 lines (265 loc) · 11.6 KB
/
Copy pathbase.frg
File metadata and controls
314 lines (265 loc) · 11.6 KB
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
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#lang forge
/*
Base domain model of strand space style crypto (2021)
Abby Siegel
Mia Santomauro
Tim Nelson
We say "strand space style" above because this model approximates the strand-space
formalism. See the "Prototyping Formal Methods Tools" paper for more information.
Design notes:
- We opted to build this in Relational Forge, not Temporal Forge; at the time,
Temporal Forge was very new and still being tested.
- Forge has a somewhat more restricted syntax than Alloy. E.g., Forge doesn't
have `facts` (which are always true); instead, predicates must be asserted.
- CPSA has some idiosyncratic terminology, which we echo here somewhat. For
example, the "strand" is not the same as the "agent" for that strand; it
may be best to think of the agent as a knowledge database and the strand
as the protocol role execution.
- This model embraces Dolev-Yao in a very concrete way: there is an explicit
attacker, who is also the medium of communication between participants.
*/
-- NOTE WELL: `mesg` is what CPSA calls terms; we echo that here, do not confuse
-- `mesg` with just messages being sent or received.
abstract sig mesg {}
abstract sig Key extends mesg {}
abstract sig akey extends Key {} -- asymmetric key
sig skey extends Key {} -- symmetric key
sig PrivateKey extends akey {}
sig PublicKey extends akey {}
-- Helper to hold relations that match key pairs
one sig KeyPairs {
pairs: set PrivateKey -> PublicKey,
owners: func PrivateKey -> name,
ltks: set name -> name -> skey
}
/** Get a long-term key associated with a pair of agents */
fun getLTK[name_a: name, name_b: name]: lone skey {
(KeyPairs.ltks)[name_a][name_b]
}
/** Get the inverse key for a given key (if any). The structure of this predicate
is due to Forge's typechecking as of January 2025. The (none & Key) is a workaround
to give Key type to none, which has univ type by default. */
fun getInv[k: Key]: one Key {
(k in PublicKey => ((KeyPairs.pairs).k) else (k.(KeyPairs.pairs)))
+
(k in skey => k else (none & Key))
}
-- Time indexes (t=0, t=1, ...). These are also used as micro-tick indexes, so the
-- bound on `Timeslot` will also affect how many microticks are available between ticks.
sig Timeslot {
-- structure of time (must be rendered linear in every run via `next is linear`)
next: lone Timeslot,
-- <=1 actual "message tuple" sent/received per timeslot
sender: one strand,
receiver: one strand,
data: set mesg,
-- relation is: Tick x Microtick x learned-mesg
-- Only one agent per tick is receiving, so always know which agent's workspace it is
workspace: set Timeslot -> mesg
}
-- As names process received messages, they learn pieces of data
-- (they may also generate new values on their own)
sig name extends mesg {
learned_times: set mesg -> Timeslot,
generated_times: set mesg -> Timeslot
}
-- every strand will be either a protocol role or the attacker/medium
abstract sig strand {
-- the name associated with this strand
agent: one name
}
one sig AttackerStrand extends strand {}
one sig Attacker extends name {}
sig Ciphertext extends mesg {
-- encrypted with this key
encryptionKey: one Key,
-- result in concating plaintexts
plaintext: set mesg
}
-- Non-name base value (e.g., nonces)
sig text extends mesg {}
/** The starting knowledge base for all agents */
fun baseKnown[a: name]: set mesg {
-- name knows all public keys
PublicKey
+
-- name knows the private keys it owns
(KeyPairs.owners).a
+
-- name knows long-term keys they are party to
{d : skey | some a2 : name - a | d in getLTK[a, a2] + getLTK[a2, a] }
+
-- names know their own names
a
}
/** This (large) predicate contains the vast majority of domain axioms */
pred wellformed {
-- Design choice: only one message event per timeslot;
-- assume we have a shared notion of time
-- You cannot send a message with no data
all m: Timeslot | some m.data
-- someone cannot send a message to themselves
all m: Timeslot | m.sender not in m.receiver
-- workspace: workaround to avoid cyclic justification within just deconstructions
-- AGENT -> TICK -> MICRO-TICK LEARNED_SUBTERM
all d: mesg | all t, microt: Timeslot | let a = t.receiver.agent | d in (workspace[t])[microt] iff {
-- Base case:
-- received the data in the clear just now
{d in t.data and no microt.~next}
or
-- Inductive case:
-- breaking down a ciphertext we learned *previously*, or that we've produced from
-- something larger this timeslot via a key we learned *previously*, or that we've
-- produced from something larger in this timeslot Note use of "previously" by
-- subtracting the *reflexive* transitive closure is crucial in preventing cyclic justification.
-- Note: the baseKnown function includes an agent's private key, otherwise "prior
-- knowledge" is empty (even of their private key!)
{
--d not in ((a.workspace)[t])[Timeslot - microt.^next] and -- first time appearing
{some superterm : Ciphertext | {
d in superterm.plaintext and
superterm in (a.learned_times).(Timeslot - t.*next) + workspace[t][Timeslot - microt.*next] + baseKnown[a] and
getInv[superterm.encryptionKey] in (a.learned_times).(Timeslot - t.*next) + workspace[t][Timeslot - microt.*next] + baseKnown[a]
}}}
}
-- names only learn information that associated strands are explicitly sent
-- (start big disjunction for learned_times)
all d: mesg | all t: Timeslot | all a: name | d->t in a.learned_times iff {
-- they have not already learned this value
{d not in (a.learned_times).(Timeslot - t.*next)} and
-- This base-case is handled in the workspace now, hence commented out:
-- They received a message directly containing d (may be a ciphertext)
{ --{some m: Message | {d in m.data and t = m.sendTime and m.receiver.agent = a}}
--or
-- deconstruct encrypted term
-- constrain time to reception to avoid cyclic justification of knowledge. e.g.,
-- "I know enc(other-agent's-private-key, pubk(me)) [from below via construct]"
-- "I know other-agent's-private-key [from above via deconstruct]""
-- instead: separate the two temporally: deconstruct on recv, construct on non-reception
-- in that case, the cycle can't exist in the same timeslot
-- might think to write an accessibleSubterms function as below, except:
-- consider: (k1, enc(k2, enc(n1, invk(k2)), invk(k1)))
-- or, worse: (k1, enc(x, invk(k3)), enc(k2, enc(k3, invk(k2)), invk(k1)))
{ t.receiver.agent = a
d in workspace[t][Timeslot] -- derived in any micro-tick in this (reception) timeslot
}
or
-- construct encrypted terms (only allow at NON-reception time; see above)
-- NOTE WELL: if ever allow an agent to send/receive at same time, need rewrite
{d in Ciphertext and
d.encryptionKey in (a.learned_times).(Timeslot - t.^next) and
d.plaintext in (a.learned_times).(Timeslot - t.^next)
{a not in t.receiver.agent} -- non-reception
}
or
{d in baseKnown[a]}
or
-- This was a value generated by the name in this timeslot
{d in (a.generated_times).t}
}} -- (end big disjunction for learned_times)
-- If you generate something, you do it once only
all a: name | all d: text | lone t: Timeslot | d in (a.generated_times).t
-- Messages comprise only values known by the sender
all m: Timeslot | m.data in (((m.sender).agent).learned_times).(Timeslot - m.^next)
-- Always send or receive to the adversary
all m: Timeslot | m.sender = AttackerStrand or m.receiver = AttackerStrand
-- plaintext relation is acyclic
-- NOTE WELL: if ever add another type of mesg that contains data, add with + inside ^.
all d: mesg | d not in d.^(plaintext)
-- Disallow empty ciphertexts
all c: Ciphertext | some c.plaintext
(KeyPairs.pairs).PublicKey = PrivateKey -- total
PrivateKey.(KeyPairs.pairs) = PublicKey -- total
all privKey: PrivateKey | {one pubKey: PublicKey | privKey->pubKey in KeyPairs.pairs} -- uniqueness re: pairing
all priv1: PrivateKey | all priv2: PrivateKey - priv1 | all pub: PublicKey | priv1->pub in KeyPairs.pairs implies priv2->pub not in KeyPairs.pairs
-- Private keys are disjoint with respect to ownership
all a1, a2: name | {
(some KeyPairs.owners.a1 and a1 != a2) implies
(KeyPairs.owners.a1 != KeyPairs.owners.a2)
}
-- at most one long-term key per (ordered) pair of names
all a:name, b:name | lone getLTK[a,b]
-- assume long-term keys are used for only one agent pair (or unused)
all k: skey | lone (KeyPairs.ltks).k
-- The Attacker agent is represented by the attacker strand
AttackerStrand.agent = Attacker
/*
-- If one agent has a key, it is different from any other agent's key
all a1, a2: name | {
(some KeyPairs.owners.a1 and a1 != a2) implies
(KeyPairs.owners.a1 != KeyPairs.owners.a2)
}
-- private key ownership is unique
all p: PrivateKey | one p.(KeyPairs.owners)
*/
-- generation only of text and keys, not complex terms
-- furthermore, only generate if unknown
all n: name | {
n.generated_times.Timeslot in text+Key
all t: Timeslot, d: mesg | {
d in n.generated_times.t implies {
all t2: t.~(^next) | { d not in n.learned_times.t2 }
d not in baseKnown[n]
}
}
}
}
/** Definition of subterms for some set of terms */
fun subterm[supers: set mesg]: set mesg {
-- VITAL: if you add a new subterm relation, needs to be added here, too!
supers +
supers.^(plaintext) -- union on new subterm relations inside parens
}
/** When does a strand 'originate' some term?
(Note: it's vital this definition is about strands, not names.)
*/
pred originates[s: strand, d: mesg] {
-- unsigned term t originates on n in N iff
-- term(n) is positive and
-- t subterm of term(n) and
-- whenever n' precedes n on the same strand, t is not subterm of n'
some m: sender.s | { -- messages sent by strand s (positive term)
d in subterm[m.data] -- d is a sub-term of m
all m2: (sender.s + receiver.s) - m | { -- everything else on the strand
-- ASSUME: messages are sent/received in same timeslot
{m2 in m.^(~(next))}
implies
{d not in subterm[m2.data]}
}
}
}
-- the agent generates this term
pred generates[s: strand, d: mesg] {
some ((s.agent).generated_times)[d]
}
-- the attacker eventually learns this field value
pred attacker_learns[s: strand, d: mesg] {
s.d in Attacker.learned_times.Timeslot
}
-- the agent for this strand eventually learns this value
pred strand_agent_learns[learner: strand, s: strand, d: mesg] {
s.d in (learner.agent).learned_times.Timeslot
}
------------------------------------------------------
-- Keeping notes on what didn't work in modeling;
-- everything after this point is not part of the model.
------------------------------------------------------
-- Problem: (k1, enc(k2, enc(n1, invk(k2)), invk(k1)))
-- Problem: (k1, enc(x, invk(k3)), enc(k2, enc(k3, invk(k2)), invk(k1)))
-- needs knowledge to grow on the way through the tree, possibly sideways
-- so this approach won't work
/*fun accessibleSubterms[supers: set mesg, known: set mesg]: set mesg {
let openable = {c: Ciphertext | getInv[c.encryptionKey] in known} |
supers +
supers.^(plaintext & (openable -> mesg))
}*/
/*
-- This is the example of where narrowing would be useful; it currently causes
-- an error in last-checker (necessarily empty join on a side of an ITE that isn't
-- really used). January 2024
run {
some pub: PublicKey | {
some getInv[pub]
}
}
*/