Tags: crypto

Rating:

I learnt from this writup： https://ctftime.org/writeup/14059

Solve it using my favorite language.


package org.zeroctf.babysponge;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solver {

private static final BigInteger maxValue = new BigInteger("18446744073709551615");

private static BigInteger ROL64(BigInteger a, int n) {
}

private static BigInteger load64(int[] b) {
BigInteger result = new BigInteger("0");
for (int i = 0; i < 8; ++i) {
BigInteger B = new BigInteger(Integer.toString(b[i]));
}
return result;
}

private static int[] store64(BigInteger a) {
int[] result = new int[8];
BigInteger c = new BigInteger("255");
for (int i = 0; i < 8; ++i) {
result[i] = a.shiftRight(8*i).and(c).intValue();
}
return result;
}

private static void KeccakF1600onLanes(BigInteger[][] lanes) {
int R = 1;
for (int round = 0; round < 24; ++round) {
BigInteger[] C = new BigInteger[5];
for (int x = 0; x < 5; ++x) {
BigInteger item = new BigInteger("0");
for (int y = 0; y < 5; ++y) {
item = item.xor(lanes[x][y]);
}
C[x] = item;
}

BigInteger[] D = new BigInteger[5];
for (int x = 0; x < 5; ++x) {
D[x] = C[(x + 4)%5].xor(ROL64(C[(x + 1)%5], 1));
}

for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
lanes[x][y] = lanes[x][y].xor(D[x]);
}
}

//printLanes(lanes);

for (int i = 0; i < 1; ++i) {
int x = 1;
int y = 0;
BigInteger current = lanes[x][y];
for (int t = 0; t < 24; ++t) {
int temp = x;
x = y;
y = (2*temp + 3*y)%5;
BigInteger temp2 = current;
current = lanes[x][y];
lanes[x][y] = ROL64(temp2, (t + 1)*(t + 2)/2);
}
}

//printLanes(lanes);

for (int y = 0; y < 5; ++y) {
BigInteger[] T = new BigInteger[5];
for (int x = 0; x < 5; ++x) {
T[x] = lanes[x][y];
}
for (int x = 0; x < 5; ++x) {
lanes[x][y] = T[x].xor(T[(x + 1)%5].xor(maxValue).and(T[(x + 2)%5]));
}
}

//printLanes(lanes);

for (int j = 0; j < 7; ++j) {
R = ((R << 1) ^ ((R >> 7) * 0x71)) & 0xff;
if ((R & 2) != 0) {
BigInteger B = new BigInteger("1");
BigInteger B2 = new BigInteger("1");
B = B.shiftLeft(j).subtract(new BigInteger("1"));
B = B2.shiftLeft(B.intValue());
lanes[0][0] = lanes[0][0].xor(B);
}
}

//printLanes(lanes);
}
}

private static int[] KeccakF1600(int[] state) {
BigInteger[][] lanes = new BigInteger[5][5];
for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
int[] b = new int[8];
for (int k = 0; k < 8; ++k) {
b[k] = state[8*(x + 5*y) + k];
}
}
}

//printLanes(lanes);
KeccakF1600onLanes(lanes);
//printLanes(lanes);

int[] result = new int[200];
for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
int[] item = store64(lanes[x][y]);
for (int k = 0; k < 8; ++k) {
result[8*(x + 5*y) + k] = item[k];
}
}
}

return result;
}

private static int[] Keccak(int rate, int capacity, int[] inputBytes, int outputByteLen) {
int[] state = new int[200];
int rateInBytes = rate/8;
int blockSize = 0;
int inputOffset = 0;
while (inputOffset < inputBytes.length) {
blockSize = Math.min(inputBytes.length - inputOffset, rateInBytes);
for (int i = 0; i < blockSize; ++i) {
state[i] = state[i] ^ inputBytes[i + inputOffset];
}
inputOffset += blockSize;
if (blockSize == rateInBytes) {
state = KeccakF1600(state);
blockSize = 0;
}
}

int[] result = new int[outputByteLen];
System.arraycopy(state, 0, result, 0, outputByteLen);
return result;
}

private static int[] convert(int num, int outputLen) {
int[] result = new int[outputLen];
for (int i = 0; i < 4; ++i) {
result[outputLen - 1 - i] = num & 0xff;
num = num >> 8;
}

/*
for (int i = 4; i < outputLen; ++i) {
result[outputLen - 1 - i] = 0;
}*/

return result;
}

private static String arrToStr(int[] arr) {
StringBuffer sb = new StringBuffer();
for (int ch : arr) {
String hex = Integer.toHexString(ch);
if (hex.length() == 1) {
sb.append("0");
}
sb.append(Integer.toHexString(ch));
}
return sb.toString();
}

private static int[] arrXor(int[] m, int[] n) {
int[] result = new int[194];
for (int i = 0; i < 194; ++i) {
result[i] = m[i] ^ n[i];
}
return result;
}

private static void printArr(int[] arr) {
System.out.println("====printArr====");
System.out.println(arrToStr(arr));
System.out.println("====printArr====");
}

private static void printLanes(BigInteger[][] lanes) {
System.out.println("====printLanes====");
StringBuffer sb = new StringBuffer();
for (int x = 0; x < 5; ++x) {
for (int y = 0; y < 5; ++y) {
int[] t = store64(lanes[x][y]);
for (int i = 0; i < 8; ++i) {
String hex = Integer.toHexString(t[i]);
if (hex.length() == 1) {
sb.append("0");
}
sb.append(hex);
}
}
}
System.out.println(sb.toString());
System.out.println("====printLanes====");
}

public static void main(String[] args) {

Map<String, Integer> checkMap = new HashMap<String, Integer>();

for (int i = 0; i <= 2147483647; ++i) {
int[] inputBytes = convert(i, 194);
int[] state = Keccak(1552, 48, inputBytes, 200);
int[] capacity = new int[6];

System.arraycopy(state, 194, capacity, 0, 6);
String key = arrToStr(capacity);

if (checkMap.containsKey(key)) {
System.out.println("Found!\n");
int[] m = convert(checkMap.get(key), 194);
int[] n = convert(i, 194);
printArr(m);
printArr(n);

int[] exm1 = Keccak(1552, 48, m, 200);
int[] exm2 = Keccak(1552, 48, n, 200);
printArr(exm1);
printArr(exm2);

int[] ex = arrXor(exm1, exm2);
int[] res1 = new int[194*2];
int[] res2 = new int[194*2];

System.out.println("Result is:\n");
System.arraycopy(m, 0, res1, 0, 194);
System.arraycopy(n, 0, res2, 0, 194);
System.arraycopy(ex, 0, res2, 194, 194);
printArr(res1);
printArr(res2);
} else {
checkMap.put(key, i);
}
if (i % 10000 == 0) {
System.out.println(i);
}
}
}
}