Trying to work through 12...

2 files changed, 126 insertions, 0 deletions

diff --git a/src/solvers/Challenge12.scala b/src/solvers/Challenge12.scala
new file mode 100644
index 0000000..b37b5e3
--- /dev/null
+++ b/src/solvers/Challenge12.scala
@@ -0,0 +1,39 @@
+package ixee.cryptopals.solvers
+
+import scala.io.Source
+import ixee.cryptopals.utils.ByteUtils._
+import ixee.cryptopals.utils.CryptoUtils._
+import ixee.cryptopals.utils.StreamUtils._
+import ixee.cryptopals.utils.ConversionUtils._
+import ixee.cryptopals.utils.FunctionUtils._
+import ixee.cryptopals.utils._
+import ixee.cryptopals.utils.crypto._
+import io.github.marklister.base64.Base64._
+
+object Challenge12 {
+  val path = "./data/10.txt"
+
+  lazy val mysteryText =
+    """|Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
+       |aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
+       |dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
+       |YnkK""".stripMargin.replace("\n", "").toByteArray
+
+  val key = """|Copy your oracle function to a new function that
+               | encrypts buffers under ECB mode using a consistent
+               | but unknown key (for instance, assign a single
+               | random key, once, to a global variable).""".stripMargin
+            .replace("\n", "")
+            .asBytes
+            .grouped(16)
+            .toSeq
+            .init
+            .reduce(_ xor _)
+
+  def encryptFn(input: Seq[Byte]): Seq[Byte] =
+    SchemeBuilder("AES", key).ecb.encrypt.end(input ++ mysteryText)
+
+  def run = {
+    CryptoUtils.extractUnknownViaEcbOracle(encryptFn _)
+  }
+}
diff --git a/src/utils/CryptoUtils.scala b/src/utils/CryptoUtils.scala
index 7a31002..fc33220 100644
--- a/src/utils/CryptoUtils.scala
+++ b/src/utils/CryptoUtils.scala
@@ -1,8 +1,10 @@
 package ixee.cryptopals.utils
 
 import ixee.cryptopals.utils.crypto._
+import ixee.cryptopals.utils.TupleUtils._
 import ixee.cryptopals.utils.StreamUtils._
 import ixee.cryptopals.utils.FunctionUtils._
+import ixee.cryptopals.utils.ConversionUtils._
 import javax.crypto.Cipher
 import javax.crypto.spec.SecretKeySpec
 
@@ -38,7 +40,92 @@ object CryptoUtils {
                               //.... well very probably.
     if (countDupBlocks(xs) > 0) "ECB"
     else "CBC"
+  }
+
+  def isEcb(xs: Seq[Byte]): Boolean = detectMode(xs) == "ECB"
+
+  def detectEcbBlockSize(encryptor: Seq[Byte] => Seq[Byte]): Int = {
+    val pad = (2 to 512 by 2).map("@" * _).zipWithIndex.map {
+      _.mapAll(_1 = _.asBytes, _2 = _ + 1)
+    }
+
+    val minPadSize = pad
+      .map( { encryptor(_) } <-: _ )
+      .find( { x => isEcb(x._1) })
+      .map(_._2)
+
+    minPadSize.get // if this was a None we have serious possibility of this not being ECB
+  }
+
+  def extractUnknownViaEcbOracle(encrypt: Seq[Byte] => Seq[Byte]) = {
+    val blockSize = detectEcbBlockSize(encrypt)
+
+    def rainbow(prefix: Seq[Byte]): Map[Seq[Byte], Byte] = {
+      (0 to 255)
+        .map(_.toByte)
+        .map(prefix :+ _)
+        .map(encrypt)
+        .map(_.take(16).toSeq)
+        .zipWithIndex
+        .map(_ :-> { _.toByte } )
+        .toMap
+    }
+
+    def probeFirstBlockAndPaddings: (Seq[Byte], Map[Int, Seq[Byte]]) = {
+      def prefix(known: Seq[Byte]) = (" " * (blockSize - 1 - known.length)).asBytes
+      def genRainbow(known: Seq[Byte]) = rainbow(prefix(known) ++ known)
+      def firstCryptedBlock(known: Seq[Byte]) = encrypt(prefix(known)).take(blockSize).toSeq
+      def nextByte(known: Seq[Byte]) = genRainbow(known)(firstCryptedBlock(known))
+      (0 until 16).foldLeft((Seq[Byte](), Map[Int, Seq[Byte]]())) { (ac, idx) =>
+        (ac._1 :+ nextByte(ac._1), ac._2 + (idx -> encrypt(prefix(ac._1))))
+      }
+    }
+
+    def probeLastBlockSize: Int = {
+      val baseBlockCount = encrypt(Seq[Byte]()).length
+      val firstLargerCiphertext = (0 until blockSize)
+        .map(" " * _).map(_.asBytes).map(encrypt)
+        .zipWithIndex
+        .find(_._1.length != baseBlockCount)
+
+        // this will always be Some(_) because
+        // somewhere between 0..blockSize WILL grow the text.
+      firstLargerCiphertext.get._2
+    }
+
+    println("Last block is " + probeLastBlockSize + " bytes")
+
+    val (firstBlock, ciphertexts) = probeFirstBlockAndPaddings
+    /*
+     * zip together cipher blocks so that they look like
+     * rot0b0, rot1b0, rot2b0, rot3b0, rot4b0, rot5b0, rot6b0, rot7b0
+     * rot0b1, rot1b1, rot2b1, ...
+     *
+     */
+    val transposed = ciphertexts.toSeq.sortBy(_._1).map(_ :-> { x =>
+      val y = x.grouped(16).toSeq
+      println(y.length)
+      y
+    })
+
+//    println("Also...")
+//    println(rainbow(firstBlock.tail)(transposed(1)(0)))
+
+    val prefix = firstBlock.tail
+    val currRainbow = rainbow(prefix)
+    println(ciphertexts(0).drop(16).take(16))
+    val next = currRainbow(ciphertexts(0).drop(16).take(16).toSeq)
+    println("Next: " + new String(Array(next.toByte)))
+    val nowPrefix = (prefix.tail :+ next)
+    val r2 = rainbow(nowPrefix)
+    val next2 = r2(ciphertexts(1).drop(16).take(16).toSeq)
+    println("Next: " + new String(Array(next2.toByte)))
+    val pref3 = (nowPrefix.tail :+ next2)
+    val r3 = rainbow(pref3)
+    val next3 = r3(ciphertexts(2).drop(16).take(16).toSeq)
+    println("Next: " + new String(Array(next3.toByte)))
 
+    firstBlock
   }
 
 }