import error handling, delegation fixes
[sfa.git] / sfa / trust / certificate.py
1 #----------------------------------------------------------------------
2 # Copyright (c) 2008 Board of Trustees, Princeton University
3 #
4 # Permission is hereby granted, free of charge, to any person obtaining
5 # a copy of this software and/or hardware specification (the "Work") to
6 # deal in the Work without restriction, including without limitation the
7 # rights to use, copy, modify, merge, publish, distribute, sublicense,
8 # and/or sell copies of the Work, and to permit persons to whom the Work
9 # is furnished to do so, subject to the following conditions:
10 #
11 # The above copyright notice and this permission notice shall be
12 # included in all copies or substantial portions of the Work.
13 #
14 # THE WORK IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 
15 # OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
16 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
17 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
18 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
19 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
20 # OUT OF OR IN CONNECTION WITH THE WORK OR THE USE OR OTHER DEALINGS 
21 # IN THE WORK.
22 #----------------------------------------------------------------------
23
24 ##
25 # SFA uses two crypto libraries: pyOpenSSL and M2Crypto to implement
26 # the necessary crypto functionality. Ideally just one of these libraries
27 # would be used, but unfortunately each of these libraries is independently
28 # lacking. The pyOpenSSL library is missing many necessary functions, and
29 # the M2Crypto library has crashed inside of some of the functions. The
30 # design decision is to use pyOpenSSL whenever possible as it seems more
31 # stable, and only use M2Crypto for those functions that are not possible
32 # in pyOpenSSL.
33 #
34 # This module exports two classes: Keypair and Certificate.
35 ##
36 #
37
38 import functools
39 import os
40 import tempfile
41 import base64
42 import traceback
43 from tempfile import mkstemp
44
45 from OpenSSL import crypto
46 import M2Crypto
47 from M2Crypto import X509
48
49 from sfa.util.sfalogging import logger
50 from sfa.util.xrn import urn_to_hrn
51 from sfa.util.faults import *
52 from sfa.util.sfalogging import logger
53
54 glo_passphrase_callback = None
55
56 ##
57 # A global callback msy be implemented for requesting passphrases from the
58 # user. The function will be called with three arguments:
59 #
60 #    keypair_obj: the keypair object that is calling the passphrase
61 #    string: the string containing the private key that's being loaded
62 #    x: unknown, appears to be 0, comes from pyOpenSSL and/or m2crypto
63 #
64 # The callback should return a string containing the passphrase.
65
66 def set_passphrase_callback(callback_func):
67     global glo_passphrase_callback
68
69     glo_passphrase_callback = callback_func
70
71 ##
72 # Sets a fixed passphrase.
73
74 def set_passphrase(passphrase):
75     set_passphrase_callback( lambda k,s,x: passphrase )
76
77 ##
78 # Check to see if a passphrase works for a particular private key string.
79 # Intended to be used by passphrase callbacks for input validation.
80
81 def test_passphrase(string, passphrase):
82     try:
83         crypto.load_privatekey(crypto.FILETYPE_PEM, string, (lambda x: passphrase))
84         return True
85     except:
86         return False
87
88 def convert_public_key(key):
89     keyconvert_path = "/usr/bin/keyconvert.py"
90     if not os.path.isfile(keyconvert_path):
91         raise IOError, "Could not find keyconvert in %s" % keyconvert_path
92
93     # we can only convert rsa keys
94     if "ssh-dss" in key:
95         return None
96
97     (ssh_f, ssh_fn) = tempfile.mkstemp()
98     ssl_fn = tempfile.mktemp()
99     os.write(ssh_f, key)
100     os.close(ssh_f)
101
102     cmd = keyconvert_path + " " + ssh_fn + " " + ssl_fn
103     os.system(cmd)
104
105     # this check leaves the temporary file containing the public key so
106     # that it can be expected to see why it failed.
107     # TODO: for production, cleanup the temporary files
108     if not os.path.exists(ssl_fn):
109         return None
110
111     k = Keypair()
112     try:
113         k.load_pubkey_from_file(ssl_fn)
114     except:
115         logger.log_exc("convert_public_key caught exception")
116         k = None
117
118     # remove the temporary files
119     os.remove(ssh_fn)
120     os.remove(ssl_fn)
121
122     return k
123
124 ##
125 # Public-private key pairs are implemented by the Keypair class.
126 # A Keypair object may represent both a public and private key pair, or it
127 # may represent only a public key (this usage is consistent with OpenSSL).
128
129 class Keypair:
130     key = None       # public/private keypair
131     m2key = None     # public key (m2crypto format)
132
133     ##
134     # Creates a Keypair object
135     # @param create If create==True, creates a new public/private key and
136     #     stores it in the object
137     # @param string If string!=None, load the keypair from the string (PEM)
138     # @param filename If filename!=None, load the keypair from the file
139
140     def __init__(self, create=False, string=None, filename=None):
141         if create:
142             self.create()
143         if string:
144             self.load_from_string(string)
145         if filename:
146             self.load_from_file(filename)
147
148     ##
149     # Create a RSA public/private key pair and store it inside the keypair object
150
151     def create(self):
152         self.key = crypto.PKey()
153         self.key.generate_key(crypto.TYPE_RSA, 1024)
154
155     ##
156     # Save the private key to a file
157     # @param filename name of file to store the keypair in
158
159     def save_to_file(self, filename):
160         open(filename, 'w').write(self.as_pem())
161         self.filename=filename
162
163     ##
164     # Load the private key from a file. Implicity the private key includes the public key.
165
166     def load_from_file(self, filename):
167         self.filename=filename
168         buffer = open(filename, 'r').read()
169         self.load_from_string(buffer)
170
171     ##
172     # Load the private key from a string. Implicitly the private key includes the public key.
173
174     def load_from_string(self, string):
175         if glo_passphrase_callback:
176             self.key = crypto.load_privatekey(crypto.FILETYPE_PEM, string, functools.partial(glo_passphrase_callback, self, string) )
177             self.m2key = M2Crypto.EVP.load_key_string(string, functools.partial(glo_passphrase_callback, self, string) )
178         else:
179             self.key = crypto.load_privatekey(crypto.FILETYPE_PEM, string)
180             self.m2key = M2Crypto.EVP.load_key_string(string)
181
182     ##
183     #  Load the public key from a string. No private key is loaded.
184
185     def load_pubkey_from_file(self, filename):
186         # load the m2 public key
187         m2rsakey = M2Crypto.RSA.load_pub_key(filename)
188         self.m2key = M2Crypto.EVP.PKey()
189         self.m2key.assign_rsa(m2rsakey)
190
191         # create an m2 x509 cert
192         m2name = M2Crypto.X509.X509_Name()
193         m2name.add_entry_by_txt(field="CN", type=0x1001, entry="junk", len=-1, loc=-1, set=0)
194         m2x509 = M2Crypto.X509.X509()
195         m2x509.set_pubkey(self.m2key)
196         m2x509.set_serial_number(0)
197         m2x509.set_issuer_name(m2name)
198         m2x509.set_subject_name(m2name)
199         ASN1 = M2Crypto.ASN1.ASN1_UTCTIME()
200         ASN1.set_time(500)
201         m2x509.set_not_before(ASN1)
202         m2x509.set_not_after(ASN1)
203         # x509v3 so it can have extensions
204         # prob not necc since this cert itself is junk but still...
205         m2x509.set_version(2)
206         junk_key = Keypair(create=True)
207         m2x509.sign(pkey=junk_key.get_m2_pkey(), md="sha1")
208
209         # convert the m2 x509 cert to a pyopenssl x509
210         m2pem = m2x509.as_pem()
211         pyx509 = crypto.load_certificate(crypto.FILETYPE_PEM, m2pem)
212
213         # get the pyopenssl pkey from the pyopenssl x509
214         self.key = pyx509.get_pubkey()
215         self.filename=filename
216
217     ##
218     # Load the public key from a string. No private key is loaded.
219
220     def load_pubkey_from_string(self, string):
221         (f, fn) = tempfile.mkstemp()
222         os.write(f, string)
223         os.close(f)
224         self.load_pubkey_from_file(fn)
225         os.remove(fn)
226
227     ##
228     # Return the private key in PEM format.
229
230     def as_pem(self):
231         return crypto.dump_privatekey(crypto.FILETYPE_PEM, self.key)
232
233     ##
234     # Return an M2Crypto key object
235
236     def get_m2_pkey(self):
237         if not self.m2key:
238             self.m2key = M2Crypto.EVP.load_key_string(self.as_pem())
239         return self.m2key
240
241     ##
242     # Returns a string containing the public key represented by this object.
243
244     def get_pubkey_string(self):
245         m2pkey = self.get_m2_pkey()
246         return base64.b64encode(m2pkey.as_der())
247
248     ##
249     # Return an OpenSSL pkey object
250
251     def get_openssl_pkey(self):
252         return self.key
253
254     ##
255     # Given another Keypair object, return TRUE if the two keys are the same.
256
257     def is_same(self, pkey):
258         return self.as_pem() == pkey.as_pem()
259
260     def sign_string(self, data):
261         k = self.get_m2_pkey()
262         k.sign_init()
263         k.sign_update(data)
264         return base64.b64encode(k.sign_final())
265
266     def verify_string(self, data, sig):
267         k = self.get_m2_pkey()
268         k.verify_init()
269         k.verify_update(data)
270         return M2Crypto.m2.verify_final(k.ctx, base64.b64decode(sig), k.pkey)
271
272     def compute_hash(self, value):
273         return self.sign_string(str(value))
274
275     # only informative
276     def get_filename(self):
277         return getattr(self,'filename',None)
278
279     def dump (self, *args, **kwargs):
280         print self.dump_string(*args, **kwargs)
281
282     def dump_string (self):
283         result=""
284         result += "KEYPAIR: pubkey=%40s..."%self.get_pubkey_string()
285         filename=self.get_filename()
286         if filename: result += "Filename %s\n"%filename
287         return result
288     
289 ##
290 # The certificate class implements a general purpose X509 certificate, making
291 # use of the appropriate pyOpenSSL or M2Crypto abstractions. It also adds
292 # several addition features, such as the ability to maintain a chain of
293 # parent certificates, and storage of application-specific data.
294 #
295 # Certificates include the ability to maintain a chain of parents. Each
296 # certificate includes a pointer to it's parent certificate. When loaded
297 # from a file or a string, the parent chain will be automatically loaded.
298 # When saving a certificate to a file or a string, the caller can choose
299 # whether to save the parent certificates as well.
300
301 class Certificate:
302     digest = "md5"
303
304     cert = None
305     issuerKey = None
306     issuerSubject = None
307     parent = None
308
309     separator="-----parent-----"
310
311     ##
312     # Create a certificate object.
313     #
314     # @param create If create==True, then also create a blank X509 certificate.
315     # @param subject If subject!=None, then create a blank certificate and set
316     #     it's subject name.
317     # @param string If string!=None, load the certficate from the string.
318     # @param filename If filename!=None, load the certficiate from the file.
319
320     def __init__(self, create=False, subject=None, string=None, filename=None, intermediate=None):
321         self.data = {}
322         if create or subject:
323             self.create()
324         if subject:
325             self.set_subject(subject)
326         if string:
327             self.load_from_string(string)
328         if filename:
329             self.load_from_file(filename)
330
331         if intermediate:
332             self.set_intermediate_ca(intermediate)
333
334     # Create a blank X509 certificate and store it in this object.
335
336     def create(self):
337         self.cert = crypto.X509()
338         self.cert.set_serial_number(3)
339         self.cert.gmtime_adj_notBefore(0)
340         self.cert.gmtime_adj_notAfter(60*60*24*365*5) # five years
341         self.cert.set_version(2) # x509v3 so it can have extensions        
342
343
344     ##
345     # Given a pyOpenSSL X509 object, store that object inside of this
346     # certificate object.
347
348     def load_from_pyopenssl_x509(self, x509):
349         self.cert = x509
350
351     ##
352     # Load the certificate from a string
353
354     def load_from_string(self, string):
355         # if it is a chain of multiple certs, then split off the first one and
356         # load it (support for the ---parent--- tag as well as normal chained certs)
357
358         string = string.strip()
359         
360         # If it's not in proper PEM format, wrap it
361         if string.count('-----BEGIN CERTIFICATE') == 0:
362             string = '-----BEGIN CERTIFICATE-----\n%s\n-----END CERTIFICATE-----' % string
363
364         # If there is a PEM cert in there, but there is some other text first
365         # such as the text of the certificate, skip the text
366         beg = string.find('-----BEGIN CERTIFICATE')
367         if beg > 0:
368             # skipping over non cert beginning                                                                                                              
369             string = string[beg:]
370
371         parts = []
372
373         if string.count('-----BEGIN CERTIFICATE-----') > 1 and \
374                string.count(Certificate.separator) == 0:
375             parts = string.split('-----END CERTIFICATE-----',1)
376             parts[0] += '-----END CERTIFICATE-----'
377         else:
378             parts = string.split(Certificate.separator, 1)
379
380         self.cert = crypto.load_certificate(crypto.FILETYPE_PEM, parts[0])
381
382         # if there are more certs, then create a parent and let the parent load
383         # itself from the remainder of the string
384         if len(parts) > 1 and parts[1] != '':
385             self.parent = self.__class__()
386             self.parent.load_from_string(parts[1])
387
388     ##
389     # Load the certificate from a file
390
391     def load_from_file(self, filename):
392         file = open(filename)
393         string = file.read()
394         self.load_from_string(string)
395         self.filename=filename
396
397     ##
398     # Save the certificate to a string.
399     #
400     # @param save_parents If save_parents==True, then also save the parent certificates.
401
402     def save_to_string(self, save_parents=True):
403         string = crypto.dump_certificate(crypto.FILETYPE_PEM, self.cert)
404         if save_parents and self.parent:
405             string = string + self.parent.save_to_string(save_parents)
406         return string
407
408     ##
409     # Save the certificate to a file.
410     # @param save_parents If save_parents==True, then also save the parent certificates.
411
412     def save_to_file(self, filename, save_parents=True, filep=None):
413         string = self.save_to_string(save_parents=save_parents)
414         if filep:
415             f = filep
416         else:
417             f = open(filename, 'w')
418         f.write(string)
419         f.close()
420         self.filename=filename
421
422     ##
423     # Save the certificate to a random file in /tmp/
424     # @param save_parents If save_parents==True, then also save the parent certificates.
425     def save_to_random_tmp_file(self, save_parents=True):
426         fp, filename = mkstemp(suffix='cert', text=True)
427         fp = os.fdopen(fp, "w")
428         self.save_to_file(filename, save_parents=True, filep=fp)
429         return filename
430
431     ##
432     # Sets the issuer private key and name
433     # @param key Keypair object containing the private key of the issuer
434     # @param subject String containing the name of the issuer
435     # @param cert (optional) Certificate object containing the name of the issuer
436
437     def set_issuer(self, key, subject=None, cert=None):
438         self.issuerKey = key
439         if subject:
440             # it's a mistake to use subject and cert params at the same time
441             assert(not cert)
442             if isinstance(subject, dict) or isinstance(subject, str):
443                 req = crypto.X509Req()
444                 reqSubject = req.get_subject()
445                 if (isinstance(subject, dict)):
446                     for key in reqSubject.keys():
447                         setattr(reqSubject, key, subject[key])
448                 else:
449                     setattr(reqSubject, "CN", subject)
450                 subject = reqSubject
451                 # subject is not valid once req is out of scope, so save req
452                 self.issuerReq = req
453         if cert:
454             # if a cert was supplied, then get the subject from the cert
455             subject = cert.cert.get_subject()
456         assert(subject)
457         self.issuerSubject = subject
458
459     ##
460     # Get the issuer name
461
462     def get_issuer(self, which="CN"):
463         x = self.cert.get_issuer()
464         return getattr(x, which)
465
466     ##
467     # Set the subject name of the certificate
468
469     def set_subject(self, name):
470         req = crypto.X509Req()
471         subj = req.get_subject()
472         if (isinstance(name, dict)):
473             for key in name.keys():
474                 setattr(subj, key, name[key])
475         else:
476             setattr(subj, "CN", name)
477         self.cert.set_subject(subj)
478     ##
479     # Get the subject name of the certificate
480
481     def get_subject(self, which="CN"):
482         x = self.cert.get_subject()
483         return getattr(x, which)
484
485     ##
486     # Get the public key of the certificate.
487     #
488     # @param key Keypair object containing the public key
489
490     def set_pubkey(self, key):
491         assert(isinstance(key, Keypair))
492         self.cert.set_pubkey(key.get_openssl_pkey())
493
494     ##
495     # Get the public key of the certificate.
496     # It is returned in the form of a Keypair object.
497
498     def get_pubkey(self):
499         m2x509 = X509.load_cert_string(self.save_to_string())
500         pkey = Keypair()
501         pkey.key = self.cert.get_pubkey()
502         pkey.m2key = m2x509.get_pubkey()
503         return pkey
504
505     def set_intermediate_ca(self, val):
506         self.intermediate = val
507         if val:
508             self.add_extension('basicConstraints', 1, 'CA:TRUE')
509
510
511
512     ##
513     # Add an X509 extension to the certificate. Add_extension can only be called
514     # once for a particular extension name, due to limitations in the underlying
515     # library.
516     #
517     # @param name string containing name of extension
518     # @param value string containing value of the extension
519
520     def add_extension(self, name, critical, value):
521         ext = crypto.X509Extension (name, critical, value)
522         self.cert.add_extensions([ext])
523
524     ##
525     # Get an X509 extension from the certificate
526
527     def get_extension(self, name):
528
529         # pyOpenSSL does not have a way to get extensions
530         m2x509 = X509.load_cert_string(self.save_to_string())
531         value = m2x509.get_ext(name).get_value()
532         
533         return value
534
535     ##
536     # Set_data is a wrapper around add_extension. It stores the parameter str in
537     # the X509 subject_alt_name extension. Set_data can only be called once, due
538     # to limitations in the underlying library.
539
540     def set_data(self, str, field='subjectAltName'):
541         # pyOpenSSL only allows us to add extensions, so if we try to set the
542         # same extension more than once, it will not work
543         if self.data.has_key(field):
544             raise "Cannot set ", field, " more than once"
545         self.data[field] = str
546         self.add_extension(field, 0, str)
547
548     ##
549     # Return the data string that was previously set with set_data
550
551     def get_data(self, field='subjectAltName'):
552         if self.data.has_key(field):
553             return self.data[field]
554
555         try:
556             uri = self.get_extension(field)
557             self.data[field] = uri
558         except LookupError:
559             return None
560
561         return self.data[field]
562
563     ##
564     # Sign the certificate using the issuer private key and issuer subject previous set with set_issuer().
565
566     def sign(self):
567         logger.debug('certificate.sign')
568         assert self.cert != None
569         assert self.issuerSubject != None
570         assert self.issuerKey != None
571         self.cert.set_issuer(self.issuerSubject)
572         self.cert.sign(self.issuerKey.get_openssl_pkey(), self.digest)
573
574     ##
575     # Verify the authenticity of a certificate.
576     # @param pkey is a Keypair object representing a public key. If Pkey
577     #     did not sign the certificate, then an exception will be thrown.
578
579     def verify(self, pkey):
580         # pyOpenSSL does not have a way to verify signatures
581         m2x509 = X509.load_cert_string(self.save_to_string())
582         m2pkey = pkey.get_m2_pkey()
583         # verify it
584         return m2x509.verify(m2pkey)
585
586         # XXX alternatively, if openssl has been patched, do the much simpler:
587         # try:
588         #   self.cert.verify(pkey.get_openssl_key())
589         #   return 1
590         # except:
591         #   return 0
592
593     ##
594     # Return True if pkey is identical to the public key that is contained in the certificate.
595     # @param pkey Keypair object
596
597     def is_pubkey(self, pkey):
598         return self.get_pubkey().is_same(pkey)
599
600     ##
601     # Given a certificate cert, verify that this certificate was signed by the
602     # public key contained in cert. Throw an exception otherwise.
603     #
604     # @param cert certificate object
605
606     def is_signed_by_cert(self, cert):
607         k = cert.get_pubkey()
608         result = self.verify(k)
609         return result
610
611     ##
612     # Set the parent certficiate.
613     #
614     # @param p certificate object.
615
616     def set_parent(self, p):
617         self.parent = p
618
619     ##
620     # Return the certificate object of the parent of this certificate.
621
622     def get_parent(self):
623         return self.parent
624
625     ##
626     # Verification examines a chain of certificates to ensure that each parent
627     # signs the child, and that some certificate in the chain is signed by a
628     # trusted certificate.
629     #
630     # Verification is a basic recursion: <pre>
631     #     if this_certificate was signed by trusted_certs:
632     #         return
633     #     else
634     #         return verify_chain(parent, trusted_certs)
635     # </pre>
636     #
637     # At each recursion, the parent is tested to ensure that it did sign the
638     # child. If a parent did not sign a child, then an exception is thrown. If
639     # the bottom of the recursion is reached and the certificate does not match
640     # a trusted root, then an exception is thrown.
641     #
642     # @param Trusted_certs is a list of certificates that are trusted.
643     #
644
645     def verify_chain(self, trusted_certs = None):
646         # Verify a chain of certificates. Each certificate must be signed by
647         # the public key contained in it's parent. The chain is recursed
648         # until a certificate is found that is signed by a trusted root.
649
650         # verify expiration time
651         if self.cert.has_expired():
652             logger.debug("verify_chain: NO our certificate has expired")
653             raise CertExpired(self.get_subject(), "client cert")   
654         
655         # if this cert is signed by a trusted_cert, then we are set
656         for trusted_cert in trusted_certs:
657             if self.is_signed_by_cert(trusted_cert):
658                 # verify expiration of trusted_cert ?
659                 if not trusted_cert.cert.has_expired():
660                     logger.debug("verify_chain: YES cert %s signed by trusted cert %s"%(
661                             self.get_subject(), trusted_cert.get_subject()))
662                     return trusted_cert
663                 else:
664                     logger.debug("verify_chain: NO cert %s is signed by trusted_cert %s, but this is expired..."%(
665                             self.get_subject(),trusted_cert.get_subject()))
666                     raise CertExpired(self.get_subject(),"trusted_cert %s"%trusted_cert.get_subject())
667
668         # if there is no parent, then no way to verify the chain
669         if not self.parent:
670             logger.debug("verify_chain: NO %s has no parent and is not in trusted roots"%self.get_subject())
671             raise CertMissingParent(self.get_subject())
672
673         # if it wasn't signed by the parent...
674         if not self.is_signed_by_cert(self.parent):
675             logger.debug("verify_chain: NO %s is not signed by parent"%self.get_subject())
676             return CertNotSignedByParent(self.get_subject())
677
678         # if the parent isn't verified...
679         logger.debug("verify_chain: .. %s, -> verifying parent %s"%(self.get_subject(),self.parent.get_subject()))
680         self.parent.verify_chain(trusted_certs)
681
682         return
683
684     ### more introspection
685     def get_extensions(self):
686         # pyOpenSSL does not have a way to get extensions
687         triples=[]
688         m2x509 = X509.load_cert_string(self.save_to_string())
689         nb_extensions=m2x509.get_ext_count()
690         logger.debug("X509 had %d extensions"%nb_extensions)
691         for i in range(nb_extensions):
692             ext=m2x509.get_ext_at(i)
693             triples.append( (ext.get_name(), ext.get_value(), ext.get_critical(),) )
694         return triples
695
696     def get_data_names(self):
697         return self.data.keys()
698
699     def get_all_datas (self):
700         triples=self.get_extensions()
701         for name in self.get_data_names(): 
702             triples.append( (name,self.get_data(name),'data',) )
703         return triples
704
705     # only informative
706     def get_filename(self):
707         return getattr(self,'filename',None)
708
709     def dump (self, *args, **kwargs):
710         print self.dump_string(*args, **kwargs)
711
712     def dump_string (self,show_extensions=False):
713         result = ""
714         result += "CERTIFICATE for %s\n"%self.get_subject()
715         result += "Issued by %s\n"%self.get_issuer()
716         filename=self.get_filename()
717         if filename: result += "Filename %s\n"%filename
718         if show_extensions:
719             all_datas=self.get_all_datas()
720             result += " has %d extensions/data attached"%len(all_datas)
721             for (n,v,c) in all_datas:
722                 if c=='data':
723                     result += "   data: %s=%s\n"%(n,v)
724                 else:
725                     result += "    ext: %s (crit=%s)=<<<%s>>>\n"%(n,c,v)
726         return result