001// Copyright (c) 2001 Hursh Jain (http://www.mollypages.org) 002// The Molly framework is freely distributable under the terms of an 003// MIT-style license. For details, see the molly pages web site at: 004// http://www.mollypages.org/. Use, modify, have fun ! 005 006package fc.util; 007 008import java.util.*; 009import java.util.regex.*; 010import java.security.*; 011 012/* 013UUID and token utilities 014 015@author hursh jain 016*/ 017public final class UUIDUtil 018{ 019static MessageDigest digester = null; 020 021static { 022 try { 023 digester = MessageDigest.getInstance("SHA-1"); 024 } 025 catch (Exception e) { 026 e.printStackTrace(); 027 } 028 } 029 030/** 031Returns a ID suitable for a session/cookie identifier. 032<pre> 033See: cookies.lcs.mit.edu 034See: www.across.si 035 036There are 2 issues with generating sessionid's. 037 0381) uniqueness - 2 or more sessionid's should not end up being 039 the same. 0402) hard-to-guess - For example, sequential values like 041 1, 2, 3 are unique but easy to guess and therefore easy 042 to session hijack. 043 044Our sessionid's have 2 parts: 045a) a timestamp for guaranteed uniqueness (easy to guess) 046b) random data (hard to guess) 047</pre> 048*/ 049public static String newSessionID() 050 { 051 //although this function has been written for some time, 052 //i recently looked this over with webscarab (around aug 2007) 053 //and it visually appears fairly scattered/random. (9999 sid's) 054 //dunno, maybe hotbits retrieved/cached every minute via a background 055 //thread is good if one wants to be hardcore but it's pretty good 056 //as-is 057 058 //there is also no visual difference between nanos & millis. intuitively 059 //nanos should have more differences in the lower bits but after 060 //all the bits get churned/digested, there is no diff that i can tell, 061 //at least visually via webscarab. so i've left this as millis. 062 063 final long time = System.currentTimeMillis(); 064 065 Random random = new java.util.Random(); 066 final int rand = random.nextInt(); 067 final String cookie = String.valueOf(time) + rand; 068 069 byte[] digestbuf = null; 070 071 //digests always returns 16 bytes 072 synchronized (UUIDUtil.class) { 073 digestbuf = digester.digest(cookie.getBytes()); 074 } 075 076 /* 077 we simply convert bytes toHex. note, we don't use Base64 078 because '/' and '+' are valid Base64 chars and they can 079 mess up url's. 080 */ 081 082 char[] encoded = null; 083 encoded = encode(digestbuf); 084 return new String(encoded); 085 086 //note, we don't ever need to use the decode() method 087 //but it's there for testing foo->encode->decode->foo 088 } 089 090 091//well, i was very...young...when I wrote this... :-] 092// 093//all right, as of 2014, i took out the original string, a bit too risque 094//new lookup string is less embarassing 095// 1..............16 [or 0-15, 16 things] 096// 0123456789ABCDEF 097static final char[] lookup="wInteEMubY2169x0".toCharArray(); 098 099/* 100base16 encoding 101 0 -> some ascii code 102 1 -> some ascii code 103 ... 104 15-> some ascii code 105 106when ascii codes are for 0...F it's called "hex" encoding. 107*/ 108 109//we need a reverse lookup table since are ain't 110//using straight hexadecimal to encode 111//encode: half byte [0-16] -> char value from lookup string 112//decode: char value from lookup string (0-128) -> half byte 113static final int[] reverselookup = new int[128]; 114 115static 116 { 117 for (int n = 0; n < 16; n++) { 118 int x = lookup[n] & 0xFF; //x ='c'('c'&0xff->99), 'n'(110) etc 119 reverselookup[x] = n; //this is why reverselookup[128] above, not 16 120 } 121 } 122 123private static final char[] encode(byte[] buf) 124 { 125 final int len = buf.length; 126 127 char[] tmp = new char[len * 2]; 128 129 for (int n = 0, i = 0; n < len ; n++, i+=2) 130 { 131 int high4 = (buf[n] >> 4) & 0x0F; 132 int low4 = buf[n] & 0x0F; 133 134 tmp[i] = lookup [high4]; 135 tmp[i+1] = lookup [low4]; 136 } 137 return tmp; 138 } 139 140private static final byte[] decode(char[] buf) 141 { 142 final int len = buf.length; 143 144 byte[] tmp = new byte[(len/2) + (len%2)]; 145 146 for (int n = 0, tmp_n = 0; n < len; n+=2, tmp_n++) 147 { 148 //0xFF makes it an int. we could cast to (int) 149 //too but then that would sign extend the char 150 //in the general case [but since all are chars 151 //are < 127], it would be ok to do so in this 152 //case. Used 0xFF because that's the right thing 153 //generally speaking 154 155 int c1 = buf[n] & 0xFF; //'w', 'I', 'n', 't' etc.. 156 int c2 = buf[n+1] & 0xFF; 157 158 if ( c1 > 127 || c2 > 127) 159 throw new IllegalArgumentException("malformed bufing, encoded with characters I don't understand [" + c1 + "] and [" + c2 + "]"); 160 161 int i = (reverselookup[c1] << 4 | reverselookup [c2]); 162 //System.out.println( (reverselookup[c1] << 4) + ", " + reverselookup[c2] + ",->" + i); 163 164 tmp[tmp_n] = (byte) i; 165 } 166 return tmp; 167 } 168 169 170static char[] URL_safe_chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_-.~".toCharArray(); 171 172/** 173Returns a N-char string suitable for tracking, affiliate, short codes, etc. Uses 174characters safe for all URL's. 175 176@param len the length of the returned string 177*/ 178public static String newID(int len) 179 { 180 final Random r = new Random(); 181 final char[] buf = new char[len]; 182 for (int n = 0; n < len; n++) { 183 buf[n] = URL_safe_chars[r.nextInt(URL_safe_chars.length)]; 184 } 185 186 return new String(buf); 187 } 188 189/** 190Returns a 8 character string suitable for tracking, affiliate, short codes, etc. Uses 191characters safe for all URL's. 192*/ 193public static String newID() 194 { 195 return newID(8); 196 } 197 198public static void main (String args[]) 199 { 200 Args myargs = new Args(args); 201 int LOOP = myargs.getInt("loop", 100000); 202 myargs.setUsage("java fc.util.UUIDUtil [-loop <int, default 100,000>]"); 203 204 if (myargs.flagExists("help")) { 205 myargs.showError(); 206 return; 207 } 208 System.out.println("Session ID: " + newSessionID()); 209 System.out.println("Generating " + LOOP + " test session ids..."); 210 211 fc.util.Watch w = new fc.util.Watch(); 212 Map map = null; 213 int count = -1; 214 215 w.start(); 216 for (int n = 0; n < LOOP; n++) { 217 String s = newSessionID(); 218 } 219 System.out.println("Time for " + LOOP + ": " + w.time() + " ms"); 220 221 System.out.println("Now testing for collisions..."); 222 w.restart(); 223 224 map = new HashMap(); 225 count = 0; 226 for (int n = 0; n < LOOP; n++) 227 { 228 String s = newSessionID(); 229 if (map.containsKey(s)) { 230 System.out.println("collision found with key: " + s); 231 count++; 232 } 233 if (n > 0 && n % 20000 == 0) { 234 w.stop(); 235 System.out.println("generated: " + n + " (+ " + w.time() + " ms)"); 236 w.restart(); 237 } 238 map.put(s, null); 239 } 240 if (count == 0) { 241 System.out.println("No collisions found..."); 242 } 243 else{ 244 System.out.println(count + " collisions found..."); 245 } 246 247 System.out.println("------------------------------"); 248 w.restart(); 249 System.out.println("newID (8): " + newID(8)); 250 System.out.println("Generating " + LOOP + " test session ids..."); 251 252 for (int n = 0; n < LOOP; n++) { 253 String s = newID(8); 254 } 255 System.out.println("Time for " + LOOP + ": " + w.time() + " ms"); 256 257 System.out.println("Now testing for collisions..."); 258 w.restart(); 259 260 map = new HashMap(); 261 count = 0; 262 for (int n = 0; n < LOOP; n++) 263 { 264 String s = newID(8); 265 if (map.containsKey(s)) { 266 System.out.println("collision found with key: " + s); 267 count++; 268 } 269 if (n > 0 && n % 20000 == 0) { 270 w.stop(); 271 System.out.println("generated: " + n + " (+ " + w.time() + " ms)"); 272 w.restart(); 273 } 274 map.put(s, null); 275 } 276 if (count == 0) { 277 System.out.println("No collisions found..."); 278 } 279 else{ 280 System.out.println(count + " collisions found..."); 281 } 282 } 283 284 285}