src/org/ibex/net/SSL.java

   1 /*
   2  * org.ibex.net.SSL - By Brian Alliet
   3  * Copyright (C) 2004 Brian Alliet
   4  *
   5  * Based on TinySSL by Adam Megacz
   6  * Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
   7  *
   8  * You may modify, copy, and redistribute this code under the terms of
   9  * the GNU Lesser General Public License version 2.1, with the exception
  10  * of the portion of clause 6a after the semicolon (aka the "obnoxious
  11  * relink clause")
  12  */
  13
  14 package org.ibex.net;
  15
  16 import org.ibex.crypto.*;
  17 import java.security.SecureRandom;
  18
  19 import java.net.Socket;
  20 import java.net.SocketException;
  21
  22 import java.io.*;
  23 import java.util.Enumeration;
  24 import java.util.Hashtable;
  25 import java.util.Random;
  26 import java.util.Vector;
  27
  28 // FEATURE: Server socket
  29
  30 public class SSL extends Socket {
  31     public static final byte TLS_RSA_WITH_AES_256_CBC_SHA = 0x35;
  32     public static final byte TLS_RSA_WITH_AES_128_CBC_SHA = 0x2f;
  33     public static final byte SSL_RSA_WITH_RC4_128_SHA = 0x05;
  34     public static final byte SSL_RSA_WITH_RC4_128_MD5 = 0x04;
  35
  36     private static final byte[] DEFAULT_CIPHER_PREFS = new byte[]{
  37         TLS_RSA_WITH_AES_256_CBC_SHA,TLS_RSA_WITH_AES_128_CBC_SHA,
  38         SSL_RSA_WITH_RC4_128_SHA,SSL_RSA_WITH_RC4_128_MD5
  39     };
  40
  41     private String hostname;
  42
  43     private int negotiated;
  44
  45     private boolean tls = true;
  46     private boolean sha;
  47     private int aes;
  48
  49     private final DataInputStream rawIS;
  50     private final DataOutputStream rawOS;
  51
  52     private final InputStream sslIS;
  53     private final OutputStream sslOS;
  54
  55     private byte[] sessionID;
  56
  57     private Digest clientWriteMACDigest;
  58     private Digest serverWriteMACDigest;
  59     private byte[] masterSecret;
  60
  61     private Cipher writeCipher;
  62     private Cipher readCipher;
  63
  64     private long serverSequenceNumber;
  65     private long clientSequenceNumber;
  66
  67     private int warnings;
  68     private boolean closed;
  69
  70     // These are only used during negotiation
  71     private byte[] serverRandom;
  72     private byte[] clientRandom;
  73     private byte[] preMasterSecret;
  74
  75     // Buffers
  76     private byte[] mac;
  77
  78     private byte[] pending = new byte[16384];
  79     private int pendingStart;
  80     private int pendingLength;
  81
  82     private byte[] sendRecordBuf = new byte[16384];
  83
  84     private int handshakeDataStart;
  85     private int handshakeDataLength;
  86     private byte[] readRecordBuf = new byte[16384+20];   // 20 == sizeof(sha1 hash)
  87     private byte[] readRecordScratch = new byte[16384+20];
  88
  89     // These are only uses for CBCs
  90     private int blockSize; // block size (0 for stream ciphers)
  91     private byte[] padBuf;
  92     private byte[] prevBlock;
  93
  94     private ByteArrayOutputStream handshakesBuffer;
  95
  96     // End Buffers
  97
  98     // Static variables
  99     private final static byte[] pad1 = new byte[48];
 100     private final static byte[] pad2 = new byte[48];
 101     private final static byte[] pad1_sha = new byte[40];
 102     private final static byte[] pad2_sha = new byte[40];
 103
 104     static {
 105         for(int i=0; i<pad1.length; i++) pad1[i] = (byte)0x36;
 106         for(int i=0; i<pad2.length; i++) pad2[i] = (byte)0x5C;
 107         for(int i=0; i<pad1_sha.length; i++) pad1_sha[i] = (byte)0x36;
 108         for(int i=0; i<pad2_sha.length; i++) pad2_sha[i] = (byte)0x5C;
 109     }
 110
 111     private final static Hashtable caKeys = new Hashtable();
 112     private static VerifyCallback verifyCallback;
 113
 114     //
 115     // Constructors
 116     //
 117     public SSL(String host) throws IOException { this(host,443); }
 118     public SSL(String host, int port) throws IOException { this(host,port,true); }
 119     public SSL(String host, int port, boolean negotiate) throws IOException { this(host,port,negotiate,null); }
 120     public SSL(String host, int port, State state) throws IOException { this(host,port,true,state); }
 121     public SSL(String host, int port, boolean negotiate, State state) throws IOException {
 122         super(host,port);
 123         hostname = host;
 124         rawIS = new DataInputStream(new BufferedInputStream(super.getInputStream()));
 125         rawOS = new DataOutputStream(new BufferedOutputStream(super.getOutputStream()));
 126         sslIS = new SSLInputStream();
 127         sslOS = new SSLOutputStream();
 128         if(negotiate) negotiate(state);
 129     }
 130
 131     public synchronized void setTLS(boolean b) { if(negotiated!=0) throw new IllegalStateException("already negotiated"); tls = b; }
 132
 133     public void negotiate() throws IOException { negotiate(null,null); }
 134     public void negotiate(State state) throws IOException { negotiate(state,null); }
 135     public void negotiate(byte[] cipherPrefs) throws IOException { negotiate(null,cipherPrefs); }
 136     private void negotiate(State state, byte[] cipherPrefs) throws IOException {
 137         if(negotiated != 0) throw new IllegalStateException("already negotiated");
 138
 139         handshakesBuffer = new ByteArrayOutputStream();
 140
 141         try {
 142             sendClientHello(state != null ? state.sessionID : null, cipherPrefs);
 143             flush();
 144             debug("sent ClientHello (" + (tls?"TLSv1.0":"SSLv3.0")+")");
 145
 146             receiveServerHello();
 147             debug("got ServerHello (" + (tls?"TLSv1.0":"SSLv3.0")+")");
 148
 149             boolean resume =
 150                 state != null && sessionID.length == state.sessionID.length &&
 151                 eq(state.sessionID,0,sessionID,0,sessionID.length);
 152
 153             if(resume)
 154                 negotiateResume(state);
 155             else
 156                 negotiateNew();
 157
 158             // we're done with these now
 159             clientRandom = serverRandom = preMasterSecret = null;
 160             handshakesBuffer = null;
 161
 162             log("Negotiation with " + hostname + " complete (" + (tls?"TLSv1.0":"SSLv3.0")+")");
 163         } finally {
 164             if((negotiated & 3) != 3) {
 165                 negotiated = 0;
 166                 try { super.close(); } catch(IOException e) { /* ignore */ }
 167                 closed = true;
 168             }
 169         }
 170     }
 171
 172     private void negotiateResume(State state) throws IOException {
 173         masterSecret = state.masterSecret;
 174
 175         initCrypto();
 176         log("initializec crypto");
 177
 178         receiveChangeCipherSpec();
 179         debug("Received ChangeCipherSpec");
 180         negotiated |= 2;
 181         receieveFinished();
 182         debug("Received Finished");
 183
 184         sendChangeCipherSpec();
 185         debug("Sent ChangeCipherSpec");
 186         negotiated |= 1;
 187         sendFinished();
 188         debug("Sent Finished");
 189     }
 190
 191     private void negotiateNew() throws IOException {
 192         X509.Certificate[] certs = receiveServerCertificates();
 193         debug("got Certificate");
 194
 195         boolean gotCertificateRequest = false;
 196         OUTER: for(;;) {
 197             byte[] buf = readHandshake();
 198             switch(buf[0]) {
 199             case 14: // ServerHelloDone
 200                 if(buf.length != 4) throw new Exn("ServerHelloDone contained trailing garbage");
 201                 debug("got ServerHelloDone");
 202                 break OUTER;
 203             case 13: // CertificateRequest
 204                 debug("Got a CertificateRequest message but we don't suport client certificates");
 205                 gotCertificateRequest = true;
 206                 break;
 207             default:
 208                 throw new Exn("unknown handshake type " + buf[0]);
 209             }
 210         }
 211
 212         if(gotCertificateRequest)
 213             sendHandshake((byte)11,new byte[3]); // send empty cert list
 214
 215         try {
 216             if(!hostname.equalsIgnoreCase(certs[0].getCN()))
 217                 throw new Exn("Certificate is for " + certs[0].getCN() + " not " + hostname);
 218             verifyCerts(certs);
 219         } catch(Exn e) {
 220             if(verifyCallback == null) throw e;
 221             synchronized(SSL.class) {
 222                 if(!verifyCallback.checkCerts(certs,hostname,e)) throw e;
 223             }
 224         }
 225
 226         computeMasterSecret();
 227
 228         sendClientKeyExchange(certs[0]);
 229         debug("sent ClientKeyExchange");
 230
 231         initCrypto();
 232
 233         sendChangeCipherSpec();
 234         debug("sent ChangeCipherSpec");
 235         negotiated |= 1;
 236         sendFinished();
 237         debug("sent Finished");
 238         flush();
 239
 240         receiveChangeCipherSpec();
 241         debug("got ChangeCipherSpec");
 242         negotiated |= 2;
 243         receieveFinished();
 244         debug("got Finished");
 245     }
 246
 247     public State getSessionState() {
 248         if((negotiated&3)!=3 || !closed || warnings != 0) return null;
 249         return new State(sessionID,masterSecret);
 250     }
 251     public boolean isActive() { return !closed; }
 252     public boolean isNegotiated() { return (negotiated&3) == 3; }
 253
 254     private void sendClientHello(byte[] sessionID, byte[] cipherPrefs) throws IOException {
 255         if(sessionID != null && sessionID.length > 256) throw new IllegalArgumentException("sessionID");
 256         if(cipherPrefs == null) cipherPrefs = DEFAULT_CIPHER_PREFS;
 257         else if(cipherPrefs.length > 4) throw new IllegalArgumentException("too many cipherPrefs");
 258         // 2 = version, 32 = randomvalue, 1 = sessionID size, 2 = cipher list size, 8 = the four ciphers,
 259         // 2 = compression length/no compression
 260         int p = 0;
 261         byte[] buf = new byte[2+32+1+(sessionID == null ? 0 : sessionID.length)+2+(cipherPrefs.length * 2)+2];
 262         buf[p++] = 0x03; // major version
 263         buf[p++] = tls ? (byte)0x01 : (byte)0x00;
 264
 265         clientRandom = new byte[32];
 266         int now = (int)(System.currentTimeMillis() / 1000L);
 267         new Random().nextBytes(clientRandom);
 268         clientRandom[0] = (byte)(now>>>24);
 269         clientRandom[1] = (byte)(now>>>16);
 270         clientRandom[2] = (byte)(now>>>8);
 271         clientRandom[3] = (byte)(now>>>0);
 272         System.arraycopy(clientRandom,0,buf,p,32);
 273         p += 32;
 274
 275         buf[p++] = sessionID != null ? (byte)sessionID.length : 0;
 276         if(sessionID != null && sessionID.length != 0) System.arraycopy(sessionID,0,buf,p,sessionID.length);
 277         p += sessionID != null ? sessionID.length : 0;
 278
 279         buf[p++] = 0x00; // 8 bytes of ciphers
 280         buf[p++] = (byte)(cipherPrefs.length * 2);
 281
 282         for(int i=0;i<cipherPrefs.length;i++) {
 283             buf[p++] = 0x00;
 284             buf[p++] = cipherPrefs[i];
 285         }
 286
 287         buf[p++] = 0x01; // compression length
 288         buf[p++] = 0x00; // no compression
 289
 290         sendHandshake((byte)1,buf);
 291         flush();
 292     }
 293
 294     private void receiveServerHello() throws IOException {
 295         // ServerHello
 296         byte[] buf = readHandshake();
 297         if(buf[0] != 2) throw new Exn("expected a ServerHello message");
 298
 299         if(buf.length < 6 + 32 + 1) throw new Exn("ServerHello too small");
 300         if(buf.length < 6 + 32 + 1 + buf[6+32] + 3) throw new Exn("ServerHello too small " + buf.length+" "+buf[6+32]);
 301
 302         if(buf[4] != 0x03 || !(buf[5]==0x00 || buf[5]==0x01)) throw new Exn("server wants to use version " + buf[4] + "." + buf[5]);
 303         tls = buf[5] == 0x01;
 304         int p = 6;
 305         serverRandom = new byte[32];
 306         System.arraycopy(buf,p,serverRandom,0,32);
 307         p += 32;
 308         sessionID = new byte[buf[p++]&0xff];
 309         if(sessionID.length != 0) System.arraycopy(buf,p,sessionID,0,sessionID.length);
 310         p += sessionID.length;
 311         int cipher = ((buf[p]&0xff)<<8) | (buf[p+1]&0xff);
 312         p += 2;
 313         if((cipher>>>8)!=0) throw new Exn("Unsupported cipher " + cipher);
 314         switch(cipher&0xff) {
 315             case SSL_RSA_WITH_RC4_128_MD5:     sha = false; aes=0;    debug("Using SSL_RSA_WITH_RC4_128_MD5"); break;
 316             case SSL_RSA_WITH_RC4_128_SHA:     sha = true;  aes=0;    debug("Using SSL_RSA_WITH_RC4_128_SHA"); break;
 317             case TLS_RSA_WITH_AES_128_CBC_SHA: sha = true; aes = 128; debug("Using TLS_RSA_WITH_AES_128_CBC_SHA"); break;
 318             case TLS_RSA_WITH_AES_256_CBC_SHA: sha = true; aes = 256; debug("Using TLS_RSA_WITH_AES_256_CBC_SHA"); break;
 319             default: throw new Exn("Unsupported cipher " + cipher);
 320         }
 321         mac = new byte[sha ? 20 : 16];
 322         if(buf[p++] != 0x0) throw new Exn("unsupported compression " + buf[p-1]);
 323     }
 324
 325     private X509.Certificate[] receiveServerCertificates() throws IOException {
 326         byte[] buf = readHandshake();
 327         if(buf[0] != 11) throw new Exn("expected a Certificate message");
 328         if((((buf[4]&0xff)<<16)|((buf[5]&0xff)<<8)|((buf[6]&0xff)<<0)) != buf.length-7) throw new Exn("size mismatch in Certificate message");
 329         int p;
 330         int len,count;
 331
 332         p = 7;
 333         count = 0;
 334         while(p < buf.length - 2) {
 335             len = ((buf[p+0]&0xff)<<16)|((buf[p+1]&0xff)<<8)|((buf[p+2]&0xff)<<0);
 336             p += 3 + len;
 337             count++;
 338         }
 339         if(count == 0) throw new Exn("server didn't provide any certificates");
 340         X509.Certificate[] certs = new X509.Certificate[count];
 341         p = 7;
 342         count = 0;
 343         while(p < buf.length) {
 344             len = ((buf[p+0]&0xff)<<16)|((buf[p+1]&0xff)<<8)|((buf[p+2]&0xff)<<0);
 345             p += 3;
 346             if(p + len > buf.length) throw new Exn("Certificate message cut short");
 347             certs[count++] = new X509.Certificate(new ByteArrayInputStream(buf,p,len));
 348             p += len;
 349         }
 350         return certs;
 351     }
 352
 353     private void sendClientKeyExchange(X509.Certificate serverCert) throws IOException {
 354         byte[] encryptedPreMasterSecret;
 355         RSA.PublicKey pks = serverCert.getRSAPublicKey();
 356         PKCS1 pkcs1 = new PKCS1(new RSA(pks.modulus,pks.exponent,false),random);
 357         encryptedPreMasterSecret = pkcs1.encode(preMasterSecret);
 358         byte[] buf;
 359         if(tls) {
 360             buf = new byte[encryptedPreMasterSecret.length+2];
 361             buf[0] = (byte) (encryptedPreMasterSecret.length>>>8);
 362             buf[1] = (byte) (encryptedPreMasterSecret.length>>>0);
 363             System.arraycopy(encryptedPreMasterSecret,0,buf,2,encryptedPreMasterSecret.length);
 364         } else {
 365             // ugh... netscape didn't send the length bytes and now every SSLv3 implementation
 366             // must implement this bug
 367             buf = encryptedPreMasterSecret;
 368         }
 369         sendHandshake((byte)16,buf);
 370     }
 371
 372     private void sendChangeCipherSpec() throws IOException {
 373         sendRecord((byte)20,new byte[] { 0x01 });
 374     }
 375
 376     private void computeMasterSecret() {
 377         preMasterSecret = new byte[48];
 378         preMasterSecret[0] = 0x03; // version_high
 379         preMasterSecret[1] = tls ? (byte) 0x01 : (byte) 0x00; // version_low
 380         randomBytes(preMasterSecret,2,46);
 381
 382         if(tls) {
 383             masterSecret = tlsPRF(48,preMasterSecret,getBytes("master secret"),concat(clientRandom,serverRandom));
 384         } else {
 385             masterSecret = concat(new byte[][] {
 386                     md5(new byte[][] { preMasterSecret,
 387                             sha1(new byte[][] { new byte[] { 0x41 }, preMasterSecret, clientRandom, serverRandom })}),
 388                             md5(new byte[][] { preMasterSecret,
 389                                     sha1(new byte[][] { new byte[] { 0x42, 0x42 }, preMasterSecret, clientRandom, serverRandom })}),
 390                                     md5(new byte[][] { preMasterSecret,
 391                                             sha1(new byte[][] { new byte[] { 0x43, 0x43, 0x43 }, preMasterSecret, clientRandom, serverRandom })})
 392             } );
 393         }
 394     }
 395
 396     public void initCrypto() {
 397         byte[] keyMaterial;
 398         byte[] ivBlock;
 399
 400         if(tls) {
 401             keyMaterial = tlsPRF(
 402                     (mac.length + (aes==256 ? 32 : 16) + (aes==0 ? 0 : 16))*2, // MAC len + key len + iv len
 403                     masterSecret,
 404                     getBytes("key expansion"),
 405                     concat(serverRandom,clientRandom)
 406             );
 407         } else {
 408             keyMaterial = new byte[] { };
 409             for(int i=0; keyMaterial.length < 72; i++) {
 410                 byte[] crap = new byte[i + 1];
 411                 for(int j=0; j<crap.length; j++) crap[j] = (byte)(((byte)0x41) + ((byte)i));
 412                 keyMaterial = concat(new byte[][] { keyMaterial,
 413                         md5(new byte[][] { masterSecret,
 414                                 sha1(new byte[][] { crap, masterSecret, serverRandom, clientRandom }) }) });
 415             }
 416             if(aes != 0) throw new Error("should never happen");
 417         }
 418
 419         byte[] clientWriteMACSecret = new byte[mac.length];
 420         byte[] serverWriteMACSecret = new byte[mac.length];
 421         byte[] clientWriteKey = new byte[aes==256 ? 32 : 16];
 422         byte[] serverWriteKey = new byte[aes==256 ? 32 : 16];
 423         byte[] clientWriteIV = aes == 0 ? null : new byte[16];
 424         byte[] serverWriteIV = aes == 0 ? null : new byte[16];
 425
 426         int p = 0;
 427         System.arraycopy(keyMaterial, p, clientWriteMACSecret, 0, mac.length); p += mac.length;
 428         System.arraycopy(keyMaterial, p, serverWriteMACSecret, 0, mac.length); p += mac.length;
 429         System.arraycopy(keyMaterial, p, clientWriteKey, 0, clientWriteKey.length); p += clientWriteKey.length;
 430         System.arraycopy(keyMaterial, p, serverWriteKey, 0, serverWriteKey.length); p += serverWriteKey.length;
 431         if(clientWriteIV != null) System.arraycopy(keyMaterial,p,clientWriteIV,0,16); p += 16;
 432         if(serverWriteIV != null) System.arraycopy(keyMaterial,p,serverWriteIV,0,16); p += 16;
 433
 434         Digest inner;
 435
 436         writeCipher = aes==0 ? (Cipher)new RC4(clientWriteKey) : (Cipher)new CBC(new AES(clientWriteKey,false),16,clientWriteIV,false);
 437         inner = sha ? (Digest)new SHA1() : (Digest)new MD5();
 438         clientWriteMACDigest = tls ? (Digest) new HMAC(inner,clientWriteMACSecret) : (Digest)new SSLv3HMAC(inner,clientWriteMACSecret);
 439
 440         readCipher = aes==0 ? (Cipher)new RC4(serverWriteKey) : (Cipher)new CBC(new AES(serverWriteKey,true),16,serverWriteIV,true);
 441         inner = sha ? (Digest)new SHA1() : (Digest)new MD5();
 442         serverWriteMACDigest = tls ? (Digest)new HMAC(inner,serverWriteMACSecret) : (Digest)new SSLv3HMAC(inner,serverWriteMACSecret);
 443
 444         if(aes != 0) {
 445             blockSize = 16; // aes block size == 16
 446             padBuf = new byte[mac.length+blockSize]; // worse case, 15 bytes of data, mac, and padding byte
 447         }
 448     }
 449
 450     private void sendFinished() throws IOException {
 451         byte[] handshakes = handshakesBuffer.toByteArray();
 452         if(tls) {
 453             sendHandshake((byte)20, tlsPRF(
 454                     12,
 455                     masterSecret,
 456                     getBytes("client finished"),
 457                     concat(md5(handshakes),sha1(handshakes))));
 458
 459         } else {
 460             sendHandshake((byte)20, concat(new byte[][] {
 461                     md5(new byte[][] { masterSecret, pad2,
 462                                        md5(new byte[][] { handshakes, new byte[] { (byte)0x43, (byte)0x4C, (byte)0x4E, (byte)0x54 },
 463                                                           masterSecret, pad1 }) }),
 464                     sha1(new byte[][] { masterSecret, pad2_sha,
 465                                        sha1(new byte[][] { handshakes, new byte[] { (byte)0x43, (byte)0x4C, (byte)0x4E, (byte)0x54 },
 466                                                           masterSecret, pad1_sha } ) })
 467                 }));
 468         }
 469     }
 470
 471     private void receiveChangeCipherSpec() throws IOException {
 472         int size = readRecord((byte)20);
 473         if(size == -1) throw new Exn("got eof when expecting a ChangeCipherSpec message");
 474         if(size != 1 || readRecordBuf[0] != 0x01) throw new Exn("Invalid ChangeCipherSpec message");
 475     }
 476
 477     private void receieveFinished() throws IOException {
 478         byte[] handshakes = handshakesBuffer.toByteArray();
 479         byte[] buf = readHandshake();
 480         if(buf[0] != 20) throw new Exn("expected a Finished message");
 481         byte[] expected;
 482
 483         if(tls) {
 484             if(buf.length != 4 + 12) throw new Exn("Finished message too short");
 485             expected = tlsPRF(
 486                     12,masterSecret,
 487                     getBytes("server finished"),
 488                     concat(md5(handshakes),sha1(handshakes)));
 489         } else {
 490             if(buf.length != 4 + 16 +20) throw new Exn("Finished message too short");
 491             expected = concat(new byte[][] {
 492                     md5(new byte[][] { masterSecret, pad2,
 493                             md5(new byte[][] { handshakes, new byte[] { (byte)0x53, (byte)0x52, (byte)0x56, (byte)0x52 },
 494                                     masterSecret, pad1 }) }),
 495                                     sha1(new byte[][] { masterSecret, pad2_sha,
 496                                             sha1(new byte[][] { handshakes, new byte[] { (byte)0x53, (byte)0x52, (byte)0x56, (byte)0x52 },
 497                                                     masterSecret, pad1_sha } ) } ) } );
 498         }
 499         if(!eq(expected,0,buf,4,expected.length)) throw new Exn("server finished message mismatch");
 500     }
 501
 502     private void flush() throws IOException { rawOS.flush(); }
 503
 504     private void sendHandshake(byte type, byte[] payload) throws IOException {
 505         if(payload.length > (1<<24)) throw new IllegalArgumentException("payload.length");
 506         byte[] buf = new byte[4+payload.length];
 507         buf[0] = type;
 508         buf[1] = (byte)(payload.length>>>16);
 509         buf[2] = (byte)(payload.length>>>8);
 510         buf[3] = (byte)(payload.length>>>0);
 511         System.arraycopy(payload,0,buf,4,payload.length);
 512         handshakesBuffer.write(buf);
 513         sendRecord((byte)22,buf);
 514     }
 515
 516     private void sendRecord(byte proto, byte[] buf) throws IOException { sendRecord(proto,buf,0,buf.length); }
 517     private void sendRecord(byte proto, byte[] payload, int off, int totalLen) throws IOException {
 518         int macLength = (negotiated & 1) != 0 ? mac.length : 0;
 519         while(totalLen > 0) {
 520             int len = min(totalLen,16384-macLength);
 521             rawOS.writeByte(proto);
 522             rawOS.writeShort(tls ? 0x0301 : 0x0300);
 523             if((negotiated & 1) != 0) {
 524                 computeMAC(proto,payload,off,len,clientWriteMACDigest,clientSequenceNumber);
 525                 // FEATURE: Encode in place
 526                 if(blockSize != 0) {
 527                     int firstShot = len & ~(blockSize-1);
 528                     if(firstShot != 0) writeCipher.process(payload,off,sendRecordBuf,0,firstShot);
 529                     int _off = off + firstShot; // offset in sendRecordBuf
 530                     int _len = len - firstShot; // length of data in padBuf
 531                     if(_len != 0) System.arraycopy(payload,_off,padBuf,0,_len);
 532                     System.arraycopy(mac,0,padBuf,_len,macLength);
 533                     _len += macLength;
 534                     int extra = blockSize - (_len&~blockSize);
 535                     if(extra == 0) extra = 16;
 536                     for(int i=0;i<extra;i++) padBuf[_len+i] = (byte)(extra-1);
 537                     _len += extra;
 538                     writeCipher.process(padBuf,0,sendRecordBuf,_off,_len);
 539                     rawOS.writeShort(firstShot+_len);
 540                     rawOS.write(sendRecordBuf,0,firstShot+_len);
 541                 } else {
 542                     writeCipher.process(payload,off,sendRecordBuf,0,len);
 543                     writeCipher.process(mac,0,sendRecordBuf,len,macLength);
 544                     rawOS.writeShort(len + macLength);
 545                     rawOS.write(sendRecordBuf,0, len +macLength);
 546                 }
 547                 clientSequenceNumber++;
 548             } else {
 549                 rawOS.writeShort(len);
 550                 rawOS.write(payload,off,len);
 551             }
 552             totalLen -= len;
 553             off += len;
 554         }
 555     }
 556
 557     private byte[] readHandshake() throws IOException {
 558         if(handshakeDataLength == 0) {
 559             handshakeDataStart = 0;
 560             handshakeDataLength = readRecord((byte)22);
 561             if(handshakeDataLength == -1) throw new Exn("got eof when expecting a handshake packet");
 562         }
 563         byte[] buf = readRecordBuf;
 564         int len = ((buf[handshakeDataStart+1]&0xff)<<16)|((buf[handshakeDataStart+2]&0xff)<<8)|((buf[handshakeDataStart+3]&0xff)<<0);
 565         // Handshake messages can theoretically span multiple records, but in practice this does not occur
 566         if(len > handshakeDataLength) {
 567             sendAlert(true,10); // 10 == unexpected message
 568             throw new Exn("handshake message size too large " + len + " vs " + (handshakeDataLength-handshakeDataStart));
 569         }
 570         byte[] ret = new byte[4+len];
 571         System.arraycopy(buf,handshakeDataStart,ret,0,ret.length);
 572         handshakeDataLength -= ret.length;
 573         handshakeDataStart += ret.length;
 574         handshakesBuffer.write(ret);
 575         return ret;
 576     }
 577
 578     private int readRecord(byte reqProto) throws IOException {
 579         int macLength = (negotiated & 2) != 0 ? mac.length : 0;
 580         for(;;) {
 581             byte proto;
 582             int version, len;
 583
 584             try {
 585                 proto = rawIS.readByte();
 586             } catch(EOFException e) {
 587                 // this may or may not be an error. it is up to the application protocol
 588                 closed = true;
 589                 super.close();
 590                 throw new PrematureCloseExn();
 591             }
 592             try {
 593                 version = rawIS.readShort();
 594                 if(version != 0x0300 && version != 0x0301) throw new Exn("invalid version ");
 595                 len = rawIS.readShort();
 596                 if(len <= 0 || len > 16384+((negotiated&2)!=0 ? macLength : 0)) throw new Exn("invalid length " + len);
 597                 rawIS.readFully((negotiated&2)!=0 ? readRecordScratch : readRecordBuf,0,len);
 598             } catch(EOFException e) {
 599                 // an EOF here is always an error (we don't pass the EOF back on to the app
 600                 // because it isn't a "legitimate" eof)
 601                 throw new Exn("Hit EOF too early");
 602             }
 603
 604             if((negotiated & 2) != 0) {
 605                 // FEATURE: Decode in place
 606                 if(blockSize != 0 && (len % blockSize) != 0) throw new Exn("input not a multiple of the cipher's block size");
 607                 readCipher.process(readRecordScratch,0,readRecordBuf,0,len);
 608
 609                 if(blockSize != 0) {
 610                     if(!tls) throw new Error("should never happen");
 611                     int padding = readRecordBuf[len-1]&0xff;
 612                     if(padding >= blockSize) throw new Exn("invalid padding length: " + padding);
 613                     for(int i=0;i<padding;i++) if(readRecordBuf[len-padding-1] != padding) throw new Exn("bad padding");
 614                     len -= (padding+1);
 615                 }
 616                 if(len < macLength) throw new Exn("packet size < macLength");
 617
 618                 computeMAC(proto,readRecordBuf,0,len-macLength,serverWriteMACDigest,serverSequenceNumber);
 619                 for(int i=0;i<macLength;i++)
 620                     if(mac[i] != readRecordBuf[len-macLength+i])
 621                         throw new Exn("mac mismatch");
 622                 len -= macLength;
 623                 serverSequenceNumber++;
 624             }
 625
 626             if(proto == reqProto) return len;
 627
 628             switch(proto) {
 629                 case 21: { // ALERT
 630                     if(len != 2) throw new Exn("invalid lengh for alert");
 631                     int level = readRecordBuf[0];
 632                     int desc = readRecordBuf[1];
 633                     if(level == 1) {
 634                         if(desc == 0) { // CloseNotify
 635                             debug("Server requested connection closure");
 636                             try {
 637                                 sendCloseNotify();
 638                             } catch(SocketException e) { /* incomplete close, thats ok */ }
 639                             closed = true;
 640                             super.close();
 641                             return -1;
 642                         } else {
 643                             warnings++;
 644                             log("SSL ALERT WARNING: desc: " + desc);
 645                         }
 646                     } else if(level == 2) {
 647                         throw new Exn("SSL ALERT FATAL: desc: " +desc);
 648                     } else {
 649                         throw new Exn("invalid alert level");
 650                     }
 651                     break;
 652                 }
 653                 case 22: { // Handshake
 654                     int type = readRecordBuf[0];
 655                     int hslen = ((readRecordBuf[1]&0xff)<<16)|((readRecordBuf[2]&0xff)<<8)|((readRecordBuf[3]&0xff)<<0);
 656                     if(hslen > len - 4) throw new Exn("Multiple sequential handshake messages received after negotiation");
 657                     if(type == 0) { // HellloRequest
 658                         if(tls) sendAlert(false,100); // politely refuse, 100 == NoRegnegotiation
 659                     } else {
 660                         throw new Exn("Unexpected Handshake type: " + type);
 661                     }
 662                 }
 663                 default: throw new Exn("Unexpected protocol: " + proto);
 664             }
 665         }
 666     }
 667
 668     private static void longToBytes(long l, byte[] buf, int off) {
 669         for(int i=0;i<8;i++) buf[off+i] = (byte)(l>>>(8*(7-i)));
 670     }
 671     private void computeMAC(byte proto, byte[] payload, int off, int len, Digest digest, long sequenceNumber) {
 672         if(tls) {
 673             longToBytes(sequenceNumber,mac,0);
 674             mac[8] = proto;
 675             mac[9] = 0x03; // version
 676             mac[10] = 0x01;
 677             mac[11] = (byte)(len>>>8);
 678             mac[12] = (byte)(len>>>0);
 679
 680             digest.update(mac,0,13);
 681             digest.update(payload,off,len);
 682             digest.doFinal(mac,0);
 683         } else {
 684             longToBytes(sequenceNumber, mac, 0);
 685             mac[8] = proto;
 686             mac[9] = (byte)(len>>>8);
 687             mac[10] = (byte)(len>>>0);
 688
 689             digest.update(mac, 0, 11);
 690             digest.update(payload, off, len);
 691             digest.doFinal(mac, 0);
 692         }
 693     }
 694
 695     private void sendCloseNotify() throws IOException { sendRecord((byte)21, new byte[] { 0x01, 0x00 }); }
 696     private void sendAlert(boolean fatal, int message) throws IOException {
 697         byte[] buf = new byte[] { fatal ? (byte)2 :(byte)1, (byte)message };
 698         sendRecord((byte)21,buf);
 699         flush();
 700     }
 701
 702     //
 703     // Hash functions
 704     //
 705
 706     // Shared digest objects
 707     private MD5 masterMD5 = new MD5();
 708     private SHA1 masterSHA1 = new SHA1();
 709
 710     private byte[] md5(byte[] in) { return md5( new byte[][] { in }); }
 711     private byte[] md5(byte[][] inputs) {
 712         masterMD5.reset();
 713         for(int i=0; i<inputs.length; i++) masterMD5.update(inputs[i], 0, inputs[i].length);
 714         byte[] ret = new byte[masterMD5.getDigestSize()];
 715         masterMD5.doFinal(ret, 0);
 716         return ret;
 717     }
 718
 719     private byte[] sha1(byte[] in)  { return sha1(new byte[][] { in }); }
 720     private byte[] sha1(byte[][] inputs) {
 721         masterSHA1.reset();
 722         for(int i=0; i<inputs.length; i++) masterSHA1.update(inputs[i], 0, inputs[i].length);
 723         byte[] ret = new byte[masterSHA1.getDigestSize()];
 724         masterSHA1.doFinal(ret, 0);
 725         return ret;
 726     }
 727
 728     /*  RFC-2246
 729      PRF(secret, label, seed) = P_MD5(S1, label + seed) XOR P_SHA-1(S2, label + seed);
 730      L_S = length in bytes of secret;
 731      L_S1 = L_S2 = ceil(L_S / 2);
 732
 733      The secret is partitioned into two halves (with the possibility of
 734      one shared byte) as described above, S1 taking the first L_S1 bytes
 735      and S2 the last L_S2 bytes.
 736
 737      P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
 738      HMAC_hash(secret, A(2) + seed) +
 739      HMAC_hash(secret, A(3) + seed) + ...
 740
 741      A(0) = seed
 742      A(i) = HMAC_hash(secret, A(i-1))
 743      */
 744     private byte[] tlsPRF(int size,byte[] secret, byte[] label, byte[] seed) {
 745         if(size > 140) throw new IllegalArgumentException("size > 140: " + size);
 746         seed = concat(label,seed);
 747
 748         int half_length = (secret.length + 1) / 2;
 749         byte[] s1 = new byte[half_length];
 750         System.arraycopy(secret,0,s1,0,half_length);
 751         byte[] s2 = new byte[half_length];
 752         System.arraycopy(secret,secret.length - half_length, s2, 0, half_length);
 753
 754         Digest hmac_md5 = new HMAC(new MD5(),s1);
 755         Digest hmac_sha = new HMAC(new SHA1(),s2);
 756
 757         byte[] md5out = new byte[144];
 758         byte[] shaout = new byte[140];
 759         byte[] digest = new byte[20];
 760         int n;
 761
 762         n = 0;
 763         hmac_md5.update(seed,0,seed.length);
 764         hmac_md5.doFinal(digest,0);
 765
 766         // digest == md5_a_1
 767         while(n < size) {
 768             hmac_md5.update(digest,0,16);
 769             hmac_md5.update(seed,0,seed.length);
 770             hmac_md5.doFinal(md5out,n);
 771             hmac_md5.update(digest,0,16);
 772             hmac_md5.doFinal(digest,0);
 773             n += 16;
 774         }
 775
 776         n = 0;
 777         hmac_sha.update(seed,0,seed.length);
 778         hmac_sha.doFinal(digest,0);
 779
 780         while(n < size) {
 781             hmac_sha.update(digest,0,20);
 782             hmac_sha.update(seed,0,seed.length);
 783             hmac_sha.doFinal(shaout,n);
 784             hmac_sha.update(digest,0,20);
 785             hmac_sha.doFinal(digest,0);
 786             n += 20;
 787          }
 788
 789         byte[] ret = new byte[size];
 790         for(int i=0;i<size;i++) ret[i] = (byte)(md5out[i] ^ shaout[i]);
 791         return ret;
 792     }
 793
 794     public static class CBC implements Cipher {
 795         private final Cipher c;
 796         private final byte[] iv;
 797         private final int blockSize;
 798         private final boolean reverse;
 799         public CBC(Cipher c, int blockSize, byte[] iv, boolean reverse) {
 800             this.c = c;
 801             this.blockSize = blockSize;
 802             this.iv = iv;
 803             this.reverse = reverse;
 804             if(iv.length != blockSize) throw new IllegalArgumentException("iv.length != blockSize");
 805         }
 806
 807         public void process(byte[] in, int inp, byte[] out, int outp, int len) {
 808             if((len % blockSize) != 0) throw new IllegalArgumentException("buffer must be a multiple of block size");
 809             while(len != 0) {
 810                 if(!reverse) {
 811                     for(int i=0;i<blockSize;i++) iv[i] ^= in[inp+i]; // mangle the cleartext
 812                     c.process(iv,0,out,outp,blockSize); // process it
 813                     System.arraycopy(out,outp,iv,0,blockSize); // copy the block to iv
 814                 } else {
 815                     c.process(in,inp,out,outp,blockSize); // process the ciphertext
 816                     for(int i=0;i<blockSize;i++) out[outp+i] ^= iv[i]; // mangle the cleartext
 817                     System.arraycopy(in,inp,iv,0,blockSize); // copy the ciphertext to iv
 818                 }
 819                 inp+=16; outp+=16; len-=16;
 820             }
 821         }
 822     }
 823
 824     public static class SSLv3HMAC extends Digest {
 825         private final Digest h;
 826         private final byte[] digest;
 827         private final byte[] key;
 828         private final int padSize;
 829
 830         public int getDigestSize() { return h.getDigestSize(); }
 831
 832         public SSLv3HMAC(Digest h, byte[] key) {
 833             this.h = h;
 834             this.key = key;
 835             switch(h.getDigestSize()) {
 836                 case 16: padSize = 48; break;
 837                 case 20: padSize = 40; break;
 838                 default: throw new IllegalArgumentException("unsupported digest size");
 839             }
 840             digest = new byte[h.getDigestSize()];
 841             reset();
 842         }
 843         public void reset() {
 844             h.reset();
 845             h.update(key,0,key.length);
 846             h.update(pad1,0,padSize);
 847         }
 848         public void update(byte[] b, int off, int len) { h.update(b,off,len); }
 849         public void doFinal(byte[] out, int off){
 850             h.doFinal(digest,0);
 851             h.update(key,0,key.length);
 852             h.update(pad2,0,padSize);
 853             h.update(digest,0,digest.length);
 854             h.doFinal(out,off);
 855             reset();
 856         }
 857         protected void processWord(byte[] in, int inOff) {}
 858         protected void processLength(long bitLength) {}
 859         protected void processBlock() {}
 860     }
 861
 862     //
 863     // Static Methods
 864     //
 865
 866     private static SecureRandom random = new SecureRandom();
 867     public static synchronized void randomBytes(byte[] buf, int off, int len) {
 868         byte[] bytes =  new byte[len];
 869         random.nextBytes(bytes);
 870         System.arraycopy(bytes,0,buf,off,len);
 871     }
 872
 873     public static byte[] concat(byte[] a, byte[] b) { return concat(new byte[][] { a, b }); }
 874     public static byte[] concat(byte[] a, byte[] b, byte[] c) { return concat(new byte[][] { a, b, c }); }
 875     public static byte[] concat(byte[][] inputs) {
 876         int total = 0;
 877         for(int i=0; i<inputs.length; i++) total += inputs[i].length;
 878         byte[] ret = new byte[total];
 879         for(int i=0,pos=0; i<inputs.length;pos+=inputs[i].length,i++)
 880             System.arraycopy(inputs[i], 0, ret, pos, inputs[i].length);
 881         return ret;
 882     }
 883
 884     public static byte[] getBytes(String s) {
 885         try {
 886             return s.getBytes("US-ASCII");
 887         } catch (UnsupportedEncodingException e) {
 888             return null; // will never happen
 889         }
 890     }
 891
 892     public static boolean eq(byte[] a, int aoff, byte[] b, int boff, int len){
 893         for(int i=0;i<len;i++) if(a[aoff+i] != b[boff+i]) return false;
 894         return true;
 895     }
 896
 897     //
 898     // InputStream/OutputStream/Socket interfaces
 899     //
 900     public OutputStream getOutputStream() { return sslOS; }
 901     public InputStream getInputStream() { return sslIS; }
 902     public synchronized void close() throws IOException {
 903         if(!closed) {
 904             if(negotiated != 0) {
 905                 sendCloseNotify();
 906                 flush();
 907                 // don't bother sending a close_notify back to the server
 908                 // this is an incomplete close which is allowed by the spec
 909             }
 910             super.close();
 911             closed = true;
 912         }
 913     }
 914
 915     private int read(byte[] buf, int off, int len) throws IOException {
 916         if(pendingLength == 0) {
 917             if(closed) return -1;
 918             int readLen = readRecord((byte)23);
 919             if(readLen == -1) return -1; // EOF
 920             len = min(len,readLen);
 921             System.arraycopy(readRecordBuf,0,buf,off,len);
 922             if(readLen > len) System.arraycopy(readRecordBuf,len,pending,0,readLen-len);
 923             pendingStart = 0;
 924             pendingLength = readLen - len;
 925             return len;
 926         } else {
 927             len = min(len,pendingLength);
 928             System.arraycopy(pending,pendingStart,buf,off,len);
 929             pendingLength -= len;
 930             pendingStart += len;
 931             return len;
 932         }
 933     }
 934
 935     private void write(byte[] buf, int off, int len) throws IOException {
 936         if(closed) throw new SocketException("Socket closed");
 937         sendRecord((byte)23,buf,off,len);
 938         flush();
 939     }
 940
 941     private class SSLInputStream extends InputStream {
 942         public int available() throws IOException {
 943             synchronized(SSL.this) {
 944                 return negotiated != 0 ? pendingLength : rawIS.available();
 945             }
 946         }
 947         public int read() throws IOException {
 948             synchronized(SSL.this) {
 949                 if(negotiated==0) return rawIS.read();
 950                 if(pendingLength > 0) {
 951                     pendingLength--;
 952                     return pending[pendingStart++]&0xff;
 953                 } else {
 954                     byte[] buf = new byte[1];
 955                     int n = read(buf);
 956                     return n == -1 ? -1 : buf[0]&0xff;
 957                 }
 958             }
 959         }
 960         public int read(byte[] buf, int off, int len) throws IOException {
 961             synchronized(SSL.this) {
 962                 return negotiated!=0 ? SSL.this.read(buf,off,len) : rawIS.read(buf,off,len);
 963             }
 964         }
 965         public long skip(long n) throws IOException {
 966             synchronized(SSL.this) {
 967                 if(negotiated==0) return rawIS.skip(n);
 968                 if(pendingLength > 0) {
 969                     n = min((int)n,pendingLength);
 970                     pendingLength -= n;
 971                     pendingStart += n;
 972                     return n;
 973                 }
 974                 return super.skip(n);
 975             }
 976         }
 977     }
 978
 979     private class SSLOutputStream extends OutputStream {
 980         public void flush() throws IOException { rawOS.flush(); }
 981         public void write(int b) throws IOException { write(new byte[] { (byte)b }); }
 982         public void write(byte[] buf, int off, int len) throws IOException {
 983             synchronized(SSL.this) {
 984                 if(negotiated!=0)
 985                     SSL.this.write(buf,off,len);
 986                 else
 987                     rawOS.write(buf,off,len);
 988             }
 989         }
 990     }
 991
 992     public static class Exn extends IOException { public Exn(String s) { super(s); } }
 993     public static class PrematureCloseExn extends Exn {
 994         public PrematureCloseExn() { super("Connection was closed by the remote WITHOUT a close_noify"); }
 995     }
 996
 997     public static boolean debugOn = false;
 998     private static void debug(Object o) { if(debugOn) System.err.println("[IbexSSL-Debug] " + o.toString()); }
 999     private static void log(Object o) { System.err.println("[IbexSSL] " + o.toString()); }
1000
1001     public static void verifyCerts(X509.Certificate[] certs) throws DER.Exception, Exn {
1002         try {
1003             verifyCerts_(certs);
1004         } catch(RuntimeException e) {
1005             e.printStackTrace();
1006             throw new Exn("Error while verifying certificates: " + e);
1007         }
1008     }
1009
1010     private static void verifyCerts_(X509.Certificate[] certs) throws DER.Exception, Exn {
1011         int last = certs.length-1;
1012         for(int i=0;i<certs.length;i++) {
1013             debug("Cert " + i + ": " + certs[i].subject + " ok");
1014             if(!certs[i].isValid())
1015                 throw new Exn("Certificate " + i + " in certificate chain is not valid (" + certs[i].startDate + " - " + certs[i].endDate + ")");
1016             if(i != 0) {
1017                 X509.Certificate.BC bc = certs[i].basicContraints;
1018                 if(bc == null) {
1019                     last = i;
1020                     break;
1021                 } else {
1022                     if(!bc.isCA) throw new Exn("non-CA certificate used for signing");
1023                     if(bc.pathLenConstraint != null && bc.pathLenConstraint.longValue() < i-1) throw new Exn("CA cert can't be used this deep");
1024                 }
1025             }
1026             if(i != certs.length - 1) {
1027                 if(!certs[i].issuer.equals(certs[i+1].subject))
1028                     throw new Exn("Issuer for certificate " + i + " does not match next in chain");
1029                 if(!certs[i].isSignedBy(certs[i+1]))
1030                     throw new Exn("Certificate " + i + " in chain is not signed by the next certificate");
1031             }
1032         }
1033
1034         X509.Certificate cert = certs[last];
1035
1036         RSA.PublicKey pks = (RSA.PublicKey) caKeys.get(cert.issuer);
1037         if(pks == null) throw new Exn("Certificate is signed by an unknown CA (" + cert.issuer + ")");
1038         if(!cert.isSignedWith(pks)) throw new Exn("Certificate is not signed by its CA");
1039         log("" + cert.subject + " is signed by " + cert.issuer);
1040     }
1041
1042     public static void addCACert(byte[] b) throws IOException { addCACert(new ByteArrayInputStream(b)); }
1043     public static void addCACert(InputStream is) throws IOException { addCACert(new X509.Certificate(is)); }
1044     public static void addCACert(X509.Certificate cert) throws DER.Exception { addCAKey(cert.subject,cert.getRSAPublicKey()); }
1045     public static void addCAKey(X509.Name subject, RSA.PublicKey pks)  {
1046         synchronized(caKeys) {
1047             if(caKeys.get(subject) != null)
1048                 throw new IllegalArgumentException(subject.toString() + " already exists!");
1049             caKeys.put(subject,pks);
1050         }
1051     }
1052
1053     static {
1054         try {
1055             // This will force a <clinit> which'll load the certs
1056             Class.forName("org.ibex.net.ssl.RootCerts");
1057             log("Loaded root keys from org.ibex.net.ssl.RootCerts");
1058         } catch(ClassNotFoundException e) {
1059             InputStream is = SSL.class.getClassLoader().getResourceAsStream("org.ibex/net/ssl/rootcerts.dat");
1060             if(is != null) {
1061                 try {
1062                     addCompactCAKeys(is);
1063                     log("Loaded root certs from rootcerts.dat");
1064                 } catch(IOException e2) {
1065                     log("Error loading certs from rootcerts.dat: " + e2.getMessage());
1066                 }
1067             }
1068         }
1069     }
1070
1071     public static int addCompactCAKeys(InputStream is) throws IOException {
1072         synchronized(caKeys) {
1073             try {
1074                 Vector seq = (Vector) new DER.InputStream(is).readObject();
1075                 for(Enumeration e = seq.elements(); e.hasMoreElements();) {
1076                     Vector seq2 = (Vector) e.nextElement();
1077                     X509.Name subject = new X509.Name(seq2.elementAt(0));
1078                     RSA.PublicKey pks = new RSA.PublicKey(seq2.elementAt(1));
1079                     addCAKey(subject,pks);
1080                 }
1081                 return seq.size();
1082             } catch(RuntimeException e) {
1083                 e.printStackTrace();
1084                 throw new IOException("error while reading stream: " + e);
1085             }
1086         }
1087     }
1088
1089     public static synchronized void setVerifyCallback(VerifyCallback cb) { verifyCallback = cb; }
1090
1091     // State Info
1092     public static class State {
1093         byte[] sessionID;
1094         byte[] masterSecret;
1095         State(byte[] sessionID, byte[] masterSecret) {
1096             this.sessionID = sessionID;
1097             this.masterSecret = masterSecret;
1098         }
1099     }
1100
1101     public interface VerifyCallback {
1102         public boolean checkCerts(X509.Certificate[] certs, String hostname, Exn exn);
1103     }
1104
1105     // Helper methods
1106     private static final int min(int a, int b) { return a < b ? a : b; }
1107 }