From fd80d48f5085032839aa5ddabe32eb4e7c06a1c6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Dominik=20Sch=C3=BCrmann?= Date: Thu, 24 Sep 2015 14:11:20 +0200 Subject: phrase confirmation --- .../keychain/experimental/BitInputStream.java | 125 +++++++++++++ .../keychain/experimental/SentenceConfirm.java | 206 +++++++++++++++++++++ .../keychain/experimental/WordConfirm.java | 127 +++++++++++++ 3 files changed, 458 insertions(+) create mode 100644 OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/BitInputStream.java create mode 100644 OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/SentenceConfirm.java create mode 100644 OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/WordConfirm.java (limited to 'OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental') diff --git a/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/BitInputStream.java b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/BitInputStream.java new file mode 100644 index 000000000..b6ec7234e --- /dev/null +++ b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/BitInputStream.java @@ -0,0 +1,125 @@ +/* + * Copyright (C) Andreas Jakl + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +package org.sufficientlysecure.keychain.experimental; + +import java.io.EOFException; +import java.io.IOException; +import java.io.InputStream; + +/** + * The BitInputStream allows reading individual bits from a + * general Java InputStream. + * Like the various Stream-classes from Java, the BitInputStream + * has to be created based on another Input stream. It provides + * a function to read the next bit from the sream, as well as to read multiple + * bits at once and write the resulting data into an integer value. + *

+ * source: http://developer.nokia.com/Community/Wiki/Bit_Input/Output_Stream_utility_classes_for_efficient_data_transfer + */ +public class BitInputStream { + /** + * The Java InputStream this class is working on. + */ + private InputStream iIs; + + /** + * The buffer containing the currently processed + * byte of the input stream. + */ + private int iBuffer; + + /** + * Next bit of the current byte value that the user will + * get. If it's 8, the next bit will be read from the + * next byte of the InputStream. + */ + private int iNextBit = 8; + + /** + * Create a new bit input stream based on an existing Java InputStream. + * + * @param aIs the input stream this class should read the bits from. + */ + public BitInputStream(InputStream aIs) { + iIs = aIs; + } + + /** + * Read a specified number of bits and return them combined as + * an integer value. The bits are written to the integer + * starting at the highest bit ( << aNumberOfBits ), going down + * to the lowest bit ( << 0 ) + * + * @param aNumberOfBits defines how many bits to read from the stream. + * @return integer value containing the bits read from the stream. + * @throws IOException + */ + synchronized public int readBits(final int aNumberOfBits) + throws IOException { + int value = 0; + for (int i = aNumberOfBits - 1; i >= 0; i--) { + value |= (readBit() << i); + } + return value; + } + + synchronized public int available() { + try { + return (8 - iNextBit) + iIs.available() * 8; // bytestream to bitstream available + } catch (Exception e) { + return 0; + } + } + + /** + * Read the next bit from the stream. + * + * @return 0 if the bit is 0, 1 if the bit is 1. + * @throws IOException + */ + synchronized public int readBit() throws IOException { + if (iIs == null) + throw new IOException("Already closed"); + + if (iNextBit == 8) { + iBuffer = iIs.read(); + + if (iBuffer == -1) + throw new EOFException(); + + iNextBit = 0; + } + + int bit = iBuffer & (1 << iNextBit); + iNextBit++; + + bit = (bit == 0) ? 0 : 1; + + return bit; + } + + /** + * Close the underlying input stream. + * + * @throws IOException + */ + public void close() throws IOException { + iIs.close(); + iIs = null; + } +} \ No newline at end of file diff --git a/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/SentenceConfirm.java b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/SentenceConfirm.java new file mode 100644 index 000000000..ead70b8f6 --- /dev/null +++ b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/SentenceConfirm.java @@ -0,0 +1,206 @@ +/* + * Copyright (C) 2015 Dominik Schürmann + * Copyright (C) 2014 Jake McGinty (Open Whisper Systems) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +package org.sufficientlysecure.keychain.experimental; + +import android.content.Context; + +import org.sufficientlysecure.keychain.Constants; +import org.sufficientlysecure.keychain.R; +import org.sufficientlysecure.keychain.util.Log; + +import java.io.BufferedReader; +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStreamReader; +import java.util.ArrayList; +import java.util.List; + +/** + * From https://github.com/mcginty/TextSecure/tree/mnemonic-poem + */ +public class SentenceConfirm { + Context context; + List n, vi, vt, adj, adv, p, art; + + public SentenceConfirm(Context context) { + this.context = context; + try { + n = readFile(R.raw.fp_sentence_nouns); + vi = readFile(R.raw.fp_sentence_verbs_i); + vt = readFile(R.raw.fp_sentence_verbs_t); + adj = readFile(R.raw.fp_sentence_adjectives); + adv = readFile(R.raw.fp_sentence_adverbs); + p = readFile(R.raw.fp_sentence_prepositions); + art = readFile(R.raw.fp_sentence_articles); + } catch (IOException e) { + Log.e(Constants.TAG, "Reading sentence files failed", e); + } + } + + List readFile(int resId) throws IOException { + if (context.getApplicationContext() == null) { + throw new AssertionError("app context can't be null"); + } + + BufferedReader in = new BufferedReader(new InputStreamReader( + context.getApplicationContext() + .getResources() + .openRawResource(resId))); + List words = new ArrayList<>(); + String word = in.readLine(); + while (word != null) { + words.add(word); + word = in.readLine(); + } + in.close(); + return words; + } + + public String fromBytes(final byte[] bytes, int desiredBytes) throws IOException { + BitInputStream bin = new BitInputStream(new ByteArrayInputStream(bytes)); + EntropyString fingerprint = new EntropyString(); + + while (fingerprint.getBits() < (desiredBytes * 8)) { + if (!fingerprint.isEmpty()) { + fingerprint.append("\n\n"); + } + try { + fingerprint.append(getSentence(bin)); + } catch (IOException e) { + Log.e(Constants.TAG, "IOException when creating the sentence"); + throw e; + } + } + return fingerprint.toString(); + } + + /** + * Grab a word for a list of them using the necessary bits to choose from a BitInputStream + * + * @param words the list of words to select from + * @param bin the bit input stream to encode from + * @return A Pair of the word and the number of bits consumed from the stream + */ + private EntropyString getWord(List words, BitInputStream bin) throws IOException { + final int neededBits = log(words.size(), 2); + Log.d(Constants.TAG, "need " + neededBits + " bits of entropy"); + int bits = bin.readBits(neededBits); + Log.d(Constants.TAG, "got word " + words.get(bits) + " with " + neededBits + " bits of entropy"); + return new EntropyString(words.get(bits), neededBits); + } + + private EntropyString getNounPhrase(BitInputStream bits) throws IOException { + final EntropyString phrase = new EntropyString(); + phrase.append(getWord(art, bits)).append(" "); + if (bits.readBit() != 0) { + phrase.append(getWord(adj, bits)).append(" "); + } + phrase.incBits(); + + phrase.append(getWord(n, bits)); + Log.d(Constants.TAG, "got phrase " + phrase + " with " + phrase.getBits() + " bits of entropy"); + return phrase; + } + + EntropyString getSentence(BitInputStream bits) throws IOException { + final EntropyString sentence = new EntropyString(); + sentence.append(getNounPhrase(bits)); // Subject + if (bits.readBit() != 0) { + sentence.append(" ").append(getWord(vt, bits)); // Transitive verb + sentence.append(" ").append(getNounPhrase(bits)); // Object of transitive verb + } else { + sentence.append(" ").append(getWord(vi, bits)); // Intransitive verb + } + sentence.incBits(); + + if (bits.readBit() != 0) { + sentence.append(" ").append(getWord(adv, bits)); // Adverb + } + + sentence.incBits(); + if (bits.readBit() != 0) { + sentence.append(" ").append(getWord(p, bits)); // Preposition + sentence.append(" ").append(getNounPhrase(bits)); // Object of preposition + } + sentence.incBits(); + Log.d(Constants.TAG, "got sentence " + sentence + " with " + sentence.getBits() + " bits of entropy"); + + // uppercase first character, end with dot (without increasing the bits) + sentence.getBuilder().replace(0, 1, + Character.toString(Character.toUpperCase(sentence.getBuilder().charAt(0)))); + sentence.getBuilder().append("."); + + return sentence; + } + + public static class EntropyString { + private StringBuilder builder; + private int bits; + + public EntropyString(String phrase, int bits) { + this.builder = new StringBuilder(phrase); + this.bits = bits; + } + + public EntropyString() { + this("", 0); + } + + public StringBuilder getBuilder() { + return builder; + } + + public boolean isEmpty() { + return builder.length() == 0; + } + + public EntropyString append(EntropyString phrase) { + builder.append(phrase); + bits += phrase.getBits(); + return this; + } + + public EntropyString append(String string) { + builder.append(string); + return this; + } + + public int getBits() { + return bits; + } + + public void setBits(int bits) { + this.bits = bits; + } + + public void incBits() { + bits += 1; + } + + @Override + public String toString() { + return builder.toString(); + } + } + + private static int log(int x, int base) { + return (int) (Math.log(x) / Math.log(base)); + } + +} \ No newline at end of file diff --git a/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/WordConfirm.java b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/WordConfirm.java new file mode 100644 index 000000000..daf63ea9e --- /dev/null +++ b/OpenKeychain/src/main/java/org/sufficientlysecure/keychain/experimental/WordConfirm.java @@ -0,0 +1,127 @@ +/* + * Copyright (C) 2015 Dominik Schürmann + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +package org.sufficientlysecure.keychain.experimental; + +import android.content.Context; + +import org.spongycastle.util.Arrays; +import org.sufficientlysecure.keychain.Constants; +import org.sufficientlysecure.keychain.R; +import org.sufficientlysecure.keychain.util.Log; + +import java.io.BufferedReader; +import java.io.IOException; +import java.io.InputStreamReader; +import java.util.ArrayList; +import java.util.BitSet; + +public class WordConfirm { + + public static String getWords(Context context, byte[] fingerprintBlob) { + ArrayList words = new ArrayList<>(); + + BufferedReader reader = null; + try { + reader = new BufferedReader(new InputStreamReader( + context.getResources().openRawResource(R.raw.fp_word_list), + "UTF-8" + )); + + String line = reader.readLine(); + while (line != null) { + words.add(line); + + line = reader.readLine(); + } + } catch (IOException e) { + throw new RuntimeException("IOException", e); + } finally { + if (reader != null) { + try { + reader.close(); + } catch (IOException ignored) { + } + } + } + + String fingerprint = ""; + + // NOTE: 160 bit SHA-1 truncated to 156 bit + byte[] fingerprintBlobTruncated = Arrays.copyOfRange(fingerprintBlob, 0, 156 / 8); + + // TODO: implement key stretching to minimize fp length? + + // BitSet bits = BitSet.valueOf(fingerprintBlob); // min API 19 and little endian! + BitSet bits = bitSetToByteArray(fingerprintBlobTruncated); + Log.d(Constants.TAG, "bits: " + bits.toString()); + + final int CHUNK_SIZE = 13; + final int LAST_CHUNK_INDEX = fingerprintBlobTruncated.length * 8 / CHUNK_SIZE; // 12 + Log.d(Constants.TAG, "LAST_CHUNK_INDEX: " + LAST_CHUNK_INDEX); + + int from = 0; + int to = CHUNK_SIZE; + for (int i = 0; i < (LAST_CHUNK_INDEX + 1); i++) { + Log.d(Constants.TAG, "from: " + from + " to: " + to); + + BitSet setIndex = bits.get(from, to); + int wordIndex = (int) bitSetToLong(setIndex); + // int wordIndex = (int) setIndex.toLongArray()[0]; // min API 19 + + fingerprint += words.get(wordIndex); + + if (i != LAST_CHUNK_INDEX) { + // line break every 3 words + if (to % (CHUNK_SIZE * 3) == 0) { + fingerprint += "\n"; + } else { + fingerprint += " "; + } + } + + from = to; + to += CHUNK_SIZE; + } + + return fingerprint; + } + + /** + * Returns a BitSet containing the values in bytes. + * BIG ENDIAN! + */ + private static BitSet bitSetToByteArray(byte[] bytes) { + int arrayLength = bytes.length * 8; + BitSet bits = new BitSet(); + + for (int i = 0; i < arrayLength; i++) { + if ((bytes[bytes.length - i / 8 - 1] & (1 << (i % 8))) > 0) { + bits.set(i); + } + } + return bits; + } + + private static long bitSetToLong(BitSet bits) { + long value = 0L; + for (int i = 0; i < bits.length(); ++i) { + value += bits.get(i) ? (1L << i) : 0L; + } + return value; + } +} -- cgit v1.2.3