Source code: jsdsi/Proof.java
1 /*
2 * Copyright 2002 Massachusetts Institute of Technology
3 *
4 * Permission to use, copy, modify, and distribute this program for any
5 * purpose and without fee is hereby granted, provided that this
6 * copyright and permission notice appear on all copies and supporting
7 * documentation, the name of M.I.T. not be used in advertising or
8 * publicity pertaining to distribution of the program without specific
9 * prior permission, and notice be given in supporting documentation that
10 * copying and distribution is by permission of M.I.T. M.I.T. makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
13 */
14 package jsdsi;
15
16 import jsdsi.sexp.*;
17 import java.security.*;
18 import java.security.cert.*;
19 import java.util.*;
20
21 /**
22 * A statement (a <code>Cert</code>) and a sequence of
23 * <code>Certificates</code> (<code>Certs</code> + <code>validators</code>)
24 * that proves that the statement holds. Proofs are
25 * self-validating and can be composed to create new proofs.
26 *
27 * @see Certificate
28 * @see Cert
29 *
30 * @author Sameer Ajmani
31 * @author michael.jaeger@in-flux.de
32 * @version $Revision: 1.2 $ $Date: 2003/05/07 19:36:40 $
33 */
34 public class Proof extends Obj {
35 /**
36 * New Exception used by methods in this class.
37 *
38 * @author Sameer Ajmani
39 */
40 public static class IncompatibleException extends Exception {
41 /**
42 * @see java.lang.Throwable#Throwable(String)
43 */
44 IncompatibleException(String message) {
45 super(message);
46 }
47 }
48
49 /**
50 * The statement to prove.
51 */
52 private Cert cert;
53
54 /**
55 * The certificates that prove it.
56 */
57 private Certificate[] certs;
58
59 /**
60 * Creates a new proof from a given <code>Certificate</code>.
61 *
62 * @param c <code>Certificate</code> to create the <code>Proof</code>
63 * from.
64 */
65 public Proof(Certificate c) {
66 assert(c != null) : "null certificate";
67 cert = c.getCert();
68 certs = new Certificate[] { c };
69 }
70
71 /**
72 * Creates a new proof from a <code>Cert</code> and an array of
73 * <code>Certificate</code>s.
74 *
75 * @param c <code>Cert</code> to create the proof from.
76 * @param cs array of <code>Certificate</code> to create the proof from.
77 */
78 private Proof(Cert c, Certificate[] cs) {
79 assert(c != null) : "null cert";
80 assert(cs != null) : "null certificates";
81 cert = c;
82 certs = cs;
83 }
84
85 /**
86 * Returns the <code>Cert</code> of this <code>Proof</code>.
87 *
88 * @return the <code>Cert</code> of this <code>Proof</code>.
89 */
90 public Cert getCert() {
91 return cert;
92 }
93
94 /**
95 * Returns the array of <code>Certificate</code>s of this proof.
96 *
97 * @return an array of <code>Certificate</code> of this <code>Proof</code>.
98 */
99 public Certificate[] getCertificates() {
100 return certs;
101 }
102
103 /**
104 * Returns a <code>Sequence</code> of this <code>certs</code>' elements.
105 *
106 * @return a <code>Sequence</code> of this <code>certs</code>' elements.
107 */
108 public Sequence getSequence() {
109 List elems = new ArrayList();
110 for (int i = 0; i < certs.length; i++) {
111 certs[i].toElements(elems);
112 }
113 Element[] es = new Element[elems.size()];
114 return new Sequence((Element[]) elems.toArray(es));
115 }
116
117 /**
118 * @see java.lang.Object#equals(Object)
119 */
120 public boolean equals(Object o) {
121 if (o instanceof Proof) {
122 Proof p = (Proof) o;
123 return cert.equals(p.cert) && Util.equals(certs, p.certs);
124 }
125 return false;
126 }
127
128 /**
129 * @see java.lang.Object#hashCode()
130 */
131 public int hashCode() {
132 return cert.hashCode() ^ Util.hashCode(certs);
133 }
134
135 public SexpList toSexp() {
136 Sexp[] ss = new Sexp[2];
137 ss[0] = getCert().toSexp();
138 ss[1] = getSequence().toSexp();
139 return SexpUtil.toSexp("proof", ss);
140 }
141
142 /**
143 * Verifies this proof.
144 *
145 * @see java.security.cert.Certificate#verify(java.security.PublicKey)
146 *
147 * @throws CertificateException if there are no certificates in this
148 * <code>Proof</code> or they don't match/Compose correctly.
149 * @throws NoSuchAlgorithmException if an unknown crypto algorithm
150 * has been used.
151 * @throws InvalidKeyException if a key in the certificate is not correct.
152 * @throws NoSuchProviderException if there is no security provider for
153 * this algorithm.
154 * @throws SignatureException if an error occured with a signature.
155 */
156 public void verify()
157 throws
158 CertificateException,
159 NoSuchAlgorithmException,
160 InvalidKeyException,
161 NoSuchProviderException,
162 SignatureException {
163 if (certs.length == 0) {
164 throw new CertificateException("no certificates");
165 }
166 certs[0].verify(certs[0].getPublicKey());
167 Proof p = new Proof(certs[0]);
168 try {
169 for (int i = 1; i < certs.length; i++) {
170 certs[i].verify(certs[i].getPublicKey());
171 p = p.compose(new Proof(certs[i]));
172 }
173 } catch (IncompatibleException e) {
174 throw (CertificateException) new CertificateException(
175 "certificates do not compose correctly").initCause(
176 e);
177 }
178 if (!p.getCert().equals(cert)) {
179 throw new CertificateException("composed certificates do not match proof");
180 }
181 }
182
183 /**
184 * Tries to compose a <code>Name</code> with another for a given
185 * <code>Principal</code>, that is it checks if the second name given is
186 * a prefix of the first name and if so it tries to create a new name
187 * from the rest of the name-strings the first name posesses more than
188 * the second one and substitutes this name-strings from the first name
189 * in the second name with the subject given.
190 *
191 * @see Name#prefixOf(Name)
192 *
193 * @param lhName <code>Name</code> to compose with <code>rhName</code>.
194 * @param rhName <code>Name</code> to compose with <code>lhName</code>.
195 * (should be a prefix of <code>lhName</code>)
196 * @param rhSubject <code>Pincipal</code> for
197 * @return a new <code>Name</code> if <code>rhName</code> is a prefix of
198 * <code>lhName</code> and bot hare not equal, or
199 * <code>rhSubject</code> if both names are equal.
200 * @throws IncompatibleException if <code>rhName</code> is not a prefix
201 * of <code>lhName</code> or another problem occurs with both
202 * names.
203 */
204 private Subject composeNames(Name lhName, Name rhName, Subject rhSubject)
205 throws IncompatibleException {
206 if (!rhName.prefixOf(lhName)) {
207 throw new IncompatibleException(
208 "Cannot compose " + lhName + " with " + rhName);
209 }
210 int diff = lhName.getNames().length - rhName.getNames().length;
211 if (diff == 0) {
212 return rhSubject;
213 }
214 assert(diff > 0) : "expected righthand name length <= lefthand";
215 if (!(rhSubject instanceof Principal)) {
216 throw new IncompatibleException("Cannot compose name with non-reducing cert");
217 }
218 // replace rhName with rhSubject in lhName
219 String[] names = new String[diff];
220 int off = lhName.getNames().length - diff;
221 for (int i = 0; i < names.length; i++) {
222 names[i] = lhName.getNames()[off + i];
223 }
224 return new Name((Principal) rhSubject, names);
225 }
226
227 /**
228 * Tries to compose a name certificate with a given <code>NameCert</code>
229 * by composing a new name from both names and the subject of the second
230 * name certificate.
231 *
232 * @param lhs name certificate to compose with <code>rhs</code>.
233 * @param rhs name certificate to compose with <code>lhs</code>.
234 * @return a new name from the composition of both names or the
235 * subject of <code>rhs</code> if both names are equal.
236 * @throws IncompatibleException if <code>lhs</code> is not a
237 * <code>Name</code>.
238 */
239 private Subject composeWithNameCert(Cert lhs, NameCert rhs)
240 throws IncompatibleException {
241 if (!(lhs.getSubject() instanceof Name)) {
242 throw new IncompatibleException("Cannot compose reducing Cert with NameCert");
243 }
244 Name lhName = (Name) lhs.getSubject();
245 // TODO: allow variable-length names on RHS
246 Name rhName = rhs.getFullName();
247 return composeNames(lhName, rhName, rhs.getSubject());
248 }
249
250 /**
251 * Intersects to validities and returns the result.
252 *
253 * @param v1 validity to intersect with the other.
254 * @param v2 validity to intersect with the other.
255 * @return the intersection of <code>v1</code> and <code>v2</code>.
256 */
257 private Validity intersect(Validity v1, Validity v2) {
258 if (v1 == null) {
259 return v2;
260 }
261 if (v2 == null) {
262 return v1;
263 }
264 return v1.intersect(v2);
265 }
266
267 /**
268 * Composes to given names and creates a new <code>NameCert</code> from it.
269 *
270 * @param lhs first name to inersect.
271 * @param rhs second name to intersect.
272 * @return a new <code>NameCert</code> composed of <code>lhs</code> and
273 * <code>rhs</code>.
274 * @throws IncompatibleException if <code>lhs</code> is not a proper name
275 * (should never happen!).
276 */
277 private NameCert composeNameName(NameCert lhs, NameCert rhs)
278 throws IncompatibleException {
279 return new NameCert(
280 lhs.getIssuer(),
281 composeWithNameCert(lhs, rhs),
282 intersect(lhs.getValidity(), rhs.getValidity()),
283 lhs.getDisplay(),
284 lhs.getComment(),
285 lhs.getName());
286 }
287
288 /**
289 * Creates a new <code>AuthCert</code> from a given <code>AuthCert</code>
290 * and <code>NameCert</code>.
291 *
292 * @param lhs <code>AuthCert</code> to compose with <code>rhs</code>.
293 * @param rhs <code>NameCert</code> to compose with <code>lhs</code>.
294 * @return a new <code>AuthCert</code> composed from <code>lhs</code>
295 * and <code>rhs</code>.
296 * @throws IncompatibleException if <code>lhs</code> is not a proper name
297 * (should never happen!).
298 */
299 private AuthCert composeAuthName(AuthCert lhs, NameCert rhs)
300 throws IncompatibleException {
301 return new AuthCert(
302 lhs.getIssuer(),
303 composeWithNameCert(lhs, rhs),
304 intersect(lhs.getValidity(), rhs.getValidity()),
305 lhs.getDisplay(),
306 lhs.getComment(),
307 lhs.getTag(),
308 lhs.getPropagate());
309 }
310
311 /**
312 * Composes one <code>AuthCert</code> with another if the delegation bit
313 * in the first auth certificate is set.
314 *
315 * @param lhs <code>AuthCert</code> to compose with <code>rhs</code>.
316 * @param rhs <code>AuthCert</code> that should be composed with
317 * <code>lhs</code>.
318 * @return a new <code>AuthCert</code> from <code>lhs</code> and
319 * <code>rhs</code>.
320 * @throws IncompatibleException if the delegation bit in <code>lhs</code>
321 * is not set.
322 */
323 private AuthCert composeAuthAuth(AuthCert lhs, AuthCert rhs)
324 throws IncompatibleException {
325 if (!lhs.getPropagate()) {
326 throw new IncompatibleException("cannot propagate this auth");
327 }
328 return new AuthCert(
329 lhs.getIssuer(),
330 rhs.getSubject(),
331 intersect(lhs.getValidity(), rhs.getValidity()),
332 lhs.getDisplay(),
333 lhs.getComment(),
334 lhs.getTag().intersect(rhs.getTag()),
335 rhs.getPropagate());
336 }
337
338 /**
339 * Returns an array of certificates from this <code>Proof</code> and
340 * a given <code>Proof</code>.
341 *
342 * @param p <code>Proof</code> to concat this certificates with.
343 * @return an array of <code>Certificate</code> that contains this
344 * <code>Proof</code>'s certificates and the certificates from
345 * <code>p</code>.
346 */
347 private Certificate[] concat(Proof p) {
348 Certificate[] cs = new Certificate[certs.length + p.certs.length];
349 System.arraycopy(certs, 0, cs, 0, certs.length);
350 System.arraycopy(p.certs, 0, cs, certs.length, p.certs.length);
351 return cs;
352 }
353
354 /**
355 * Composes this proof with another proof.
356 *
357 * @param p the proof to compose this with.
358 * @return a new proof that is the composition of this with <code>p</code>.
359 * @throws IncompatibleException if this cannot be composed with
360 * <code>p</code>.
361 */
362 public Proof compose(Proof p) throws IncompatibleException {
363 if (cert instanceof NameCert) {
364 if (!(p.cert instanceof NameCert)) {
365 throw new IncompatibleException(
366 "Cannot compose NameCert with: "
367 + p.cert.getClass().getName());
368 }
369 return new Proof(
370 composeNameName((NameCert) cert, (NameCert) p.cert),
371 concat(p));
372 }
373 if (cert instanceof AuthCert) {
374 if (p.cert instanceof NameCert) {
375 return new Proof(
376 composeAuthName((AuthCert) cert, (NameCert) p.cert),
377 concat(p));
378 }
379 if (p.cert instanceof AuthCert) {
380 return new Proof(
381 composeAuthAuth((AuthCert) cert, (AuthCert) p.cert),
382 concat(p));
383 }
384 }
385 throw new ClassCastException(
386 "Unrecognized Cert subclass: " + cert.getClass().getName());
387 }
388 }