Author: bdonlan
Date: 2005-06-22 23:49:50 -0400 (Wed, 22 Jun 2005)
New Revision: 801
Added:
trunk/java/src/org/haverdev/graphauth/
trunk/java/src/org/haverdev/graphauth/Challenger.java
trunk/java/src/org/haverdev/graphauth/Graph.java
trunk/java/src/org/haverdev/graphauth/GraphIsomorphism.java
trunk/java/src/org/haverdev/graphauth/KeyGenerator.java
trunk/java/src/org/haverdev/graphauth/Keypair.java
trunk/java/src/org/haverdev/graphauth/PrivateKey.java
trunk/java/src/org/haverdev/graphauth/PublicKey.java
trunk/java/src/org/haverdev/graphauth/Responder.java
Log:
This is an evil proof-of-concept thingy. Or will be, once I tie it into the
server and client.
Added: trunk/java/src/org/haverdev/graphauth/Challenger.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/Challenger.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/Challenger.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,96 @@
+/*
+ * ChallengerProcess.java
+ *
+ * Created on June 22, 2005, 11:04 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+import java.util.Random;
+import java.security.MessageDigest;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class Challenger {
+
+ PublicKey pub;
+ MessageDigest md;
+ Random rng;
+
+ Graph g3 = null;
+ byte[] commit = null;
+ boolean useG1 = false;
+
+ static final MessageDigest getSHA1() {
+ try {
+ return MessageDigest.getInstance("SHA-1");
+ } catch (java.security.NoSuchAlgorithmException e) {
+ throw new RuntimeException("SHA-1 algo not found", e);
+ }
+ }
+
+ /** Creates a new instance of ChallengerProcess */
+ public Challenger(PublicKey pub, MessageDigest md, Random rng) {
+ md.reset();
+
+ this.pub = pub;
+ this.md = md;
+ this.rng = rng;
+ }
+
+ public Challenger(PublicKey pub) {
+ this(pub, getSHA1(), new java.security.SecureRandom());
+ }
+
+ public boolean cycleInit(Graph g3, byte[] g1g3_commit, byte[] g2g3_commit)
{
+ if (g3 != null)
+ throw new IllegalStateException("Still awaiting response to last
challenge");
+ boolean b = rng.nextBoolean();
+ this.g3 = g3;
+ if (b)
+ commit = g1g3_commit;
+ else
+ commit = g2g3_commit;
+ useG1 = b;
+ return b;
+ }
+
+ final boolean compareByteArray(byte[] a, byte[] b) {
+ if (a.length != b.length)
+ return false;
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i])
+ return false;
+ }
+ return true;
+ }
+
+ public boolean cycleResponse(byte[] isomorphism) {
+ try {
+ byte[] hash = md.digest(isomorphism);
+ if (!compareByteArray(hash, commit))
+ return false; //throw new IllegalArgumentException("Given
isomorphism does not match committed hash");
+ GraphIsomorphism gi;
+ try {
+ gi = new GraphIsomorphism(isomorphism);
+ } catch (Exception e) {
+ return false; // malformed isomorphism
+ }
+ Graph c = useG1 ? pub.getG1() : pub.getG2();
+
+ if (!gi.check(g3, c))
+ return false; //throw new
IllegalArgumentException("Isomorphism is wrong");
+
+ return true;
+ } finally {
+ g3 = null;
+ commit = null;
+ }
+ }
+
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/Challenger.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/Graph.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/Graph.java 2005-06-23 03:48:58 UTC
(rev 800)
+++ trunk/java/src/org/haverdev/graphauth/Graph.java 2005-06-23 03:49:50 UTC
(rev 801)
@@ -0,0 +1,112 @@
+/*
+ * Graph.java
+ *
+ * Created on June 22, 2005, 10:31 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+import java.util.*;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class Graph {
+
+ byte[][] nodes;
+ byte nodeCount;
+ byte edgeCount;
+
+ static final byte[] byteArray = {};
+
+ Graph(byte[][] nodes) {
+ this.nodes = nodes;
+ nodeCount = (byte) nodes.length;
+ edgeCount = (byte) nodes[0].length;
+ }
+
+ /** Creates a new instance of Graph */
+ public Graph(byte[] data) {
+ // Currently we have the same number of edges on each node.
+ // This probably makes brute-forcing isomorhpism a bit harder.
+
+ nodeCount = data[0];
+ edgeCount = data[1];
+
+ for (int n = 0; n < nodeCount; n++) {
+ ArrayList al = new ArrayList(edgeCount);
+ for (int e = 0; e < edgeCount; e++) {
+ byte peer = data[2 + e + n * edgeCount];
+ if (peer >= nodeCount)
+ throw new IllegalArgumentException("Node " + peer + " out
of range");
+ al.add(new Byte(peer));
+ }
+ Collections.sort(al);
+
+ int e = 0;
+ Iterator i = al.iterator();
+ nodes[n] = new byte[edgeCount];
+ while (i.hasNext()) {
+ nodes[n][e++] = ((Byte)i.next()).byteValue();
+ }
+ }
+ }
+
+ public Graph(byte nodeC, byte edgeC, java.util.Random r) {
+ nodeCount = nodeC;
+ edgeCount = edgeC;
+
+ nodes = new byte[nodeCount][];
+
+ for (int n = 0; n < nodeC; n++) {
+ ArrayList l = new ArrayList(edgeC);
+ for (int e = 0; e < edgeC; e++) {
+ l.add(new Byte((byte) r.nextInt(edgeC)));
+ }
+ Collections.sort(l);
+
+ int e = 0;
+ Iterator i = l.iterator();
+ nodes[n] = new byte[edgeCount];
+ while (i.hasNext()) {
+ nodes[n][e++] = ((Byte)i.next()).byteValue();
+ }
+ }
+ }
+
+ public Graph(byte nodeC, byte edgeC) {
+ this(nodeC, edgeC, new java.security.SecureRandom());
+ }
+
+ public boolean equals(Object o) {
+ if (o == null)
+ return false;
+ if (o == this)
+ return true;
+ if (!(o instanceof Graph))
+ return false;
+
+ Graph that = (Graph)o;
+
+ if (that.nodeCount != nodeCount)
+ return false;
+ if (that.edgeCount != edgeCount)
+ return false;
+
+ for (int n = 0; n < nodeCount; n++) {
+ for (int e = 0; e < edgeCount; e++) {
+ if (that.nodes[n][e] != nodes[n][e])
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ int hashCode = 0; // TODO hashCode()
+
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/Graph.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/GraphIsomorphism.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/GraphIsomorphism.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/GraphIsomorphism.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,101 @@
+/*
+ * GraphIsomorphism.java
+ *
+ * Created on June 22, 2005, 10:46 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+import java.util.*;
+
+/**
+ * Represents a proof of isomorphism between two graphs.
+ *
+ * @author bdonlan
+ */
+public class GraphIsomorphism {
+
+ byte[] mapping;
+
+ public static GraphIsomorphism newRandom(byte nodeC, Random rng) {
+ ArrayList l = new ArrayList(nodeC);
+ for (int i = 0; i < nodeC; i++)
+ l.add(new Byte((byte) i));
+ Collections.shuffle(l, rng);
+
+ byte[] iso = new byte[nodeC];
+ int n = 0;
+ Iterator i = l.iterator();
+ while (i.hasNext()) {
+ iso[n++] = ((Byte) i.next()).byteValue();
+ }
+
+ return new GraphIsomorphism(iso, false);
+ }
+
+ /** Creates a new instance of GraphIsomorphism */
+ public GraphIsomorphism(byte[] mapping) {
+ this(mapping, true);
+ }
+
+ GraphIsomorphism(byte[] mapping, boolean validate) {
+ this.mapping = mapping;
+
+ if (!validate)
+ return;
+
+ this.mapping = (byte[]) mapping.clone();
+
+ boolean[] visited = new boolean[mapping.length];
+ for (int i = 0; i < mapping.length; i++) {
+ if (mapping[i] < 0 || mapping[i] >= mapping.length)
+ throw new IllegalArgumentException("Target out of range: " +
mapping[i]);
+ if (visited[mapping[i]])
+ throw new IllegalArgumentException("Mapping target reuse: " +
mapping[i] + " at index " + i);
+ visited[mapping[i]] = true;
+ }
+ }
+
+ public Graph apply(Graph src) {
+ if (src.nodeCount != mapping.length)
+ throw new IllegalArgumentException("Graph has the wrong number of
nodes");
+ byte[][] out = new byte[src.nodeCount][src.edgeCount];
+ for (int n = 0; n < src.nodeCount; n++) {
+ for (int e = 0; e < src.edgeCount; e++) {
+ out[n][e] = mapping[src.nodes[n][e]];
+ }
+ }
+ return new Graph(out);
+ }
+
+ public GraphIsomorphism reverse() {
+ byte[] out = new byte[mapping.length];
+ for (int i = 0; i < mapping.length; i++) {
+ out[mapping[i]] = (byte) i;
+ }
+ return new GraphIsomorphism(out, false);
+ }
+
+ public boolean check(Graph g1, Graph g2) {
+ return apply(g1).equals(g2);
+ }
+
+ public GraphIsomorphism compose(GraphIsomorphism after) {
+ if (after.mapping.length != mapping.length)
+ throw new IllegalArgumentException("Cannot compose isomorphisms
for graphs of non-equal length");
+ byte[] arr = new byte[mapping.length];
+
+ for (int i = 0; i < mapping.length; i++) {
+ arr[i] = after.mapping[mapping[i]];
+ }
+
+ return new GraphIsomorphism(arr, false);
+ }
+
+ public byte[] toArray() {
+ return (byte[]) mapping.clone();
+ }
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/GraphIsomorphism.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/KeyGenerator.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/KeyGenerator.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/KeyGenerator.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,70 @@
+/*
+ * KeyGenerator.java
+ *
+ * Created on June 22, 2005, 10:56 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+import java.util.*;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class KeyGenerator {
+
+ byte nodeC = 16;
+ byte edgeC = 3;
+ Random rng = new java.security.SecureRandom();
+
+ /** Creates a new instance of KeyGenerator */
+ public KeyGenerator() {
+ try {
+ nodeC = (byte) Integer.getInteger("graphauth.nodeC",
16).intValue();
+ } catch (Exception e) {}
+ try {
+ edgeC = (byte) Integer.getInteger("graphauth.edgeC",
16).intValue();
+ } catch (Exception e) {}
+ }
+
+ public void setNodeC(byte v) {
+ nodeC = v;
+ }
+
+ public void setEdgeC(byte v) {
+ edgeC = v;
+ }
+
+ public void setRng(Random r) {
+ rng = r;
+ }
+
+ public byte getNodeC() {
+ return nodeC;
+ }
+
+ public byte getEdgeC() {
+ return edgeC;
+ }
+
+ public Random getRnd() {
+ return rng;
+ }
+
+ public Keypair generate() {
+ Graph g1 = new Graph(nodeC, edgeC, rng);
+
+ GraphIsomorphism gi = GraphIsomorphism.newRandom(nodeC, rng);
+ Graph g2 = gi.apply(g1);
+
+ PublicKey pub = new PublicKey(g1, g2);
+ PrivateKey priv = new PrivateKey(gi);
+
+ return new Keypair(pub, priv);
+ }
+
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/KeyGenerator.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/Keypair.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/Keypair.java 2005-06-23 03:48:58 UTC
(rev 800)
+++ trunk/java/src/org/haverdev/graphauth/Keypair.java 2005-06-23 03:49:50 UTC
(rev 801)
@@ -0,0 +1,35 @@
+/*
+ * Keypair.java
+ *
+ * Created on June 22, 2005, 10:59 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class Keypair {
+
+ PublicKey pub;
+ PrivateKey priv;
+
+ /** Creates a new instance of Keypair */
+ public Keypair(PublicKey pub, PrivateKey priv) {
+ this.pub = pub;
+ this.priv = priv;
+ }
+
+ public PublicKey getPublicKey() {
+ return pub;
+ }
+
+ public PrivateKey getPrivateKey() {
+ return priv;
+ }
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/Keypair.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/PrivateKey.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/PrivateKey.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/PrivateKey.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,29 @@
+/*
+ * PrivateKey.java
+ *
+ * Created on June 22, 2005, 10:55 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class PrivateKey {
+
+ GraphIsomorphism i;
+
+ /** Creates a new instance of PrivateKey */
+ public PrivateKey(GraphIsomorphism i) {
+ this.i = i;
+ }
+
+ public GraphIsomorphism getI() {
+ return i;
+ }
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/PrivateKey.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/PublicKey.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/PublicKey.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/PublicKey.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,35 @@
+/*
+ * PublicKey.java
+ *
+ * Created on June 22, 2005, 10:54 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class PublicKey {
+
+ Graph g1, g2;
+
+ /** Creates a new instance of PublicKey */
+ public PublicKey(Graph g1, Graph g2) {
+ this.g1 = g1;
+ this.g2 = g2;
+ }
+
+ public Graph getG1() {
+ return g1;
+ }
+
+ public Graph getG2() {
+ return g2;
+ }
+
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/PublicKey.java
___________________________________________________________________
Name: svn:eol-style
+ native
Added: trunk/java/src/org/haverdev/graphauth/Responder.java
===================================================================
--- trunk/java/src/org/haverdev/graphauth/Responder.java 2005-06-23
03:48:58 UTC (rev 800)
+++ trunk/java/src/org/haverdev/graphauth/Responder.java 2005-06-23
03:49:50 UTC (rev 801)
@@ -0,0 +1,114 @@
+/*
+ * Responder.java
+ *
+ * Created on June 22, 2005, 11:15 PM
+ *
+ * To change this template, choose Tools | Options and locate the template
under
+ * the Source Creation and Management node. Right-click the template and choose
+ * Open. You can then make changes to the template in the Source Editor.
+ */
+
+package org.haverdev.graphauth;
+import java.util.Random;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+
+/**
+ *
+ * @author bdonlan
+ */
+public class Responder {
+
+ public static class CommitStruct {
+ public Graph g3;
+ public byte[] g3g1_commit;
+ public byte[] g3g2_commit;
+
+ CommitStruct (Graph g3_, byte[] g3g1, byte[] g3g2) {
+ g3 = g3_;
+ g3g1_commit = g3g1;
+ g3g2_commit = g3g1;
+ }
+
+ public byte[] serialize() {
+ byte[] buf = new byte[g3.nodeCount * g3.edgeCount +
(g3g1_commit.length * 2) + 2];
+ buf[0] = g3.nodeCount;
+ buf[1] = g3.edgeCount;
+ for (int n = 0; n < g3.nodeCount; n++) {
+ for (int e = 0; e < g3.edgeCount; e++) {
+ buf[2 + g3.edgeCount * n + e] = g3.nodes[n][e];
+ }
+ }
+ int base = 2 + g3.edgeCount * g3.nodeCount;
+ System.arraycopy(g3g1_commit, 0, buf, base, g3g1_commit.length);
+ base += g3g1_commit.length;
+ System.arraycopy(g3g2_commit, 0, buf, base, g3g1_commit.length);
+
+ return buf;
+ }
+
+ }
+
+ public static CommitStruct deserializeCommit(byte[] in) {
+ Graph g3 = new Graph(in);
+ int base = 2 + g3.edgeCount * g3.nodeCount;
+ int digest_len = (in.length - base) / 2;
+ byte[] g3g1 = new byte[digest_len];
+ byte[] g3g2 = new byte[digest_len];
+ System.arraycopy(in, base, g3g1, 0, digest_len);
+ System.arraycopy(in, base + digest_len, g3g1, 0, digest_len);
+
+ return new CommitStruct(g3, g3g1, g3g2);
+ }
+
+ PublicKey pub;
+ PrivateKey priv;
+ MessageDigest md;
+ Random rng;
+
+ GraphIsomorphism g3g1 = null;
+ GraphIsomorphism g3g2 = null;
+
+ /** Creates a new instance of Responder */
+ public Responder(PublicKey pub, PrivateKey priv, MessageDigest md, Random
rng) {
+ md.reset();
+
+ this.pub = pub;
+ this.priv = priv;
+ this.md = md;
+ this.rng = rng;
+ }
+
+ public Responder(PublicKey pub, PrivateKey priv) {
+ this(pub, priv, Challenger.getSHA1(), new SecureRandom());
+ }
+
+ public CommitStruct commit() {
+ GraphIsomorphism g1g3 =
GraphIsomorphism.newRandom(pub.getG1().nodeCount, rng);
+ g3g1 = g1g3.reverse();
+ g3g2 = g3g1.compose(priv.getI());
+
+ byte[] g3g1_c = md.digest(g3g1.toArray());
+ byte[] g3g2_c = md.digest(g3g2.toArray());
+
+ Graph g3 = g1g3.apply(pub.getG1());
+
+ CommitStruct cs = new CommitStruct(g3, g3g1_c, g3g2_c);
+ return cs;
+ }
+
+ public GraphIsomorphism respond(boolean useG1) {
+ try {
+ if (useG1)
+ return g3g1;
+ else
+ return g3g2;
+ }
+ finally {
+ g3g1 = null;
+ g3g2 = null;
+ }
+ }
+
+}
Property changes on: trunk/java/src/org/haverdev/graphauth/Responder.java
___________________________________________________________________
Name: svn:eol-style
+ native
