Challenge SSTIC 2016

    X = 0x0065  =>  Pas divisible pas 3
    X = 0x0165  =>  0x165 / 3.0 = 0x77     => 0x200 - 0x77 * 2 = 0x112
                                              0x112 / 2.0 = 0x89

; Chall SSTIC2016 - Level2 - Huge

; nasm -f elf64 -o chall_huge.o  chall_huge.asm
; ld -o chall_huge chall_huge.o
; objdump -D -M intel chall_huge
;


BITS 64

SECTION .data       ; data section

;                                |--------------------|
key:  db 0x00, 0x00, 0x00, 0x00, 0xD4, 0xD6, 0x8C, 0x99, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
      db 0xCB, 0x6D, 0x71, 0x1E, 0x38, 0x78, 0xB8, 0x24, 0xFE, 0x3F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
;        |--------------------|  |--------------------|

table:  db 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07
        db 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
        db 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
        db 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00

endline: db 0x0A, 0x00

SECTION .text       ; code section
global      _start                              ;must be declared for linker (ld)

_start:                                         ;tell linker entry point

    xor rsi, rsi
    jmp check7

check7:
    xor eax, eax
    mov     ebx, [key + 0x04]
    xor     dword [key+0x14], ebx
    fclex
    fld     tword [key + 0x10]
    fld     st0
    fcos
    fcompp
    fstsw   ax
    and     ax, 0x0FFDF
    cmp     ax, 0x4000
    mov     rbx, 1 ; main_end
    mov     r14, 0 ; exit
    cmovnz  rbx, r14

    cmp rbx, 1
    je is_end
    cmp dword [key + 0x04], 0xFFFFFFFF
    je end

next_loop:
    mov dword [key + 0x14], 0x24B87838 ; initial value
    inc dword [key + 0x04]
    jmp check7

printf:

    mov r9, rsp

    sub     rsp, 0x1000
    and     rsp, 0x0FFFFFFFFFFFFFC00

    ; buffer
    xor rax, rax
    mov rax, [key + 0x04]
    mov [rsp], eax

    movdqa xmm0, [rsp]

    ;
    mov rdi, rsp
    add rdi, 0x40

    movdqa  xmm1, xmm0
    psrlw   xmm1, 4
    xor     edx, edx
    xor     ecx, ecx
    mov     dl, 0x0F
    mov     cl, dl
    xchg    dh, cl
    mov     cx, dx
    bswap   ecx
    or      edx, ecx
    movd    xmm2, edx
    pshufd  xmm2, xmm2, 0
    pand    xmm0, xmm2
    pand    xmm1, xmm2
    movdqa  xmm2, xmm1
    punpcklbw xmm1, xmm0
    punpckhbw xmm2, xmm0
    movdqa  [rdi], xmm1
    movdqa  [rdi+0x10], xmm2
    mov     rbx, table
    mov     ecx, 0x8

printfloop:
    mov     al, [rdi]
    xlat
    add     byte [rdi], 0x30
    add     [rdi], al
    inc     rdi
    loop    printfloop

printendloop:

    xor    rax,rax
    inc    rax
    xor    rdi,rdi
    inc    rdi
    mov    rsi, rsp
    add     rsi, 0x40
    mov    edx,0x8
    syscall

    xor    rax,rax
    inc    rax
    xor    rdi,rdi
    inc    rdi
    mov    rsi,endline
    mov    edx,0x1
    syscall


    mov rsp, r9 ; restore old stack
    ret

is_end:

    call printf
    jmp next_loop
end:
    mov     eax, 0x3C
    xor     dil, dil
    syscall          ; sys_exit(0)

yfrancou@panda$ ./chall_huge
    0xD4D68C99

P2
# Un commentaire
WIDTH HEIGH
GREY_SCALE

INPUT: 32 caractères sous la forme de blocs de 0x14 * 0x14

 0x00      0x14      0x28      0x3C                                    0x280
 +---------+---------+---------+---------+---------+---------+---------+
 | 0000000 | 1111111 | 2222222 | 3333333 | 4444444 | 5555555 | ....... |
 | 0000000 | 1111111 | 2222222 | 3333333 | 4444444 | 5555555 | ....... |
 | 0000000 | 1111111 | 2222222 | 3333333 | 4444444 | 5555555 | ....... |     etc ..
 | 0000000 | 1111111 | 2222222 | 3333333 | 4444444 | 5555555 | ....... |
 +---------+---------+---------+---------+---------+---------+---------+
    CHAR1     CHAR2     CHAR3      ...


DATA du fichier 196:

            0x00                    0xC80 (1 pixel: 1 double)                         0x80A20
            +-----------------------+-------------------------------------------------+
   SEGMENT0 | 000000000000000000000 |  DATA                                           |
            +-----------------------+-------------------------------------------------+
   SEGMENT1 | 111111111111111111111 |  DATA                                           |
            +-----------------------+-------------------------------------------------+
   SEGMENT2 | 222222222222222222222 |  DATA                                           |
            +-----------------------+-------------------------------------------------+
   SEGMENT3 | 333333333333333333333 |  DATA                                           |
            +-----------------------+-------------------------------------------------+
   SEGMENT4 | 444444444444444444444 |  DATA                                           |
            +-----------------------+-------------------------------------------------+
   SEGMENT5 | etc ...               |                                                 |
            +-----------------------+-------------------------------------------------+

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math
import struct
import random
import numpy as np
np.seterr(all='ignore')


def sigmoid(x):
    return 1 / (1 + np.exp(-x))


# derivative of sigmoid
def dsigmoid(y):
    return y * (1.0 - y)


# using tanh over logistic sigmoid is recommended
def tanh(x):
    return math.tanh(x)


# derivative for tanh sigmoid
def dtanh(y):
    return 1 - y * y


class MLP_NeuralNetwork(object):
    """
    Basic MultiLayer Perceptron (MLP) network, adapted and from the book 'Programming Collective Intelligence'
    (http://shop.oreilly.com/product/9780596529321.do)
    Consists of three layers: input, hidden and output. The sizes of input and output must match data
    the size of hidden is user defined when initializing the network.
    The algorithm has been generalized to be used on any dataset.
    As long as the data is in this format: [[[x1, x2, x3, ..., xn], [y1, y2, ..., yn]],
                                           [[[x1, x2, x3, ..., xn], [y1, y2, ..., yn]],
                                           ...
                                           [[[x1, x2, x3, ..., xn], [y1, y2, ..., yn]]]
    An example is provided below with the digit recognition dataset provided by sklearn
    Fully pypy compatible.
    """
    def __init__(self, input, hidden, output, iterations, learning_rate, momentum, rate_decay, wi=None, wo=None):
        """
        :param input: number of input neurons
        :param hidden: number of hidden neurons
        :param output: number of output neurons
        """
        # initialize parameters
        self.iterations = iterations
        self.learning_rate = learning_rate
        self.momentum = momentum
        self.rate_decay = rate_decay

        # initialize arrays
        self.input = input + 1  # add 1 for bias node
        self.hidden = hidden
        self.output = output

        # set up array of 1s for activations
        self.ai = [1.0] * self.input
        self.ah = [1.0] * self.hidden
        self.ao = [1.0] * self.output

        # create randomized weights
        # use scheme from 'efficient backprop to initialize weights
        if wi is not None and wo is not None:
            self.wi = wi
            self.wo = wo
        else:
            input_range = 1.0 / self.input ** (1 / 2)
            output_range = 1.0 / self.hidden ** (1 / 2)
            self.wi = np.random.normal(loc=0, scale=input_range, size=(self.input, self.hidden))
            self.wo = np.random.normal(loc=0, scale=output_range, size=(self.hidden, self.output))

        # create arrays of 0 for changes
        # this is essentially an array of temporary values that gets updated at each iteration
        # based on how much the weights need to change in the following iteration
        self.ci = np.zeros((self.input, self.hidden))
        self.co = np.zeros((self.hidden, self.output))

    def feedForward(self, inputs):
        """
        The feedforward algorithm loops over all the nodes in the hidden layer and
        adds together all the outputs from the input layer * their weights
        the output of each node is the sigmoid function of the sum of all inputs
        which is then passed on to the next layer.
        :param inputs: input data
        :return: updated activation output vector
        """
        if len(inputs) != self.input - 1:
            raise ValueError('Wrong number of inputs you silly goose!')

        # input activations
        for i in range(self.input - 1):  # -1 is to avoid the bias
            self.ai[i] = inputs[i]

        # hidden activations
        for j in range(self.hidden):
            sum = 0.0
            for i in range(self.input):
                # print i, j, len(self.wi)
                sum += self.ai[i] * self.wi[i][j]
            # self.ah[j] = tanh(sum)
            self.ah[j] = sigmoid(sum)

        # output activations
        for k in range(self.output):
            sum = 0.0
            for j in range(self.hidden):
                sum += self.ah[j] * self.wo[j][k]
            self.ao[k] = sigmoid(sum)

        return self.ao[:]

    def backPropagate(self, targets):
        """
        For the output layer
        1. Calculates the difference between output value and target value
        2. Get the derivative (slope) of the sigmoid function in order to determine how much the weights need to change
        3. update the weights for every node based on the learning rate and sig derivative

        For the hidden layer
        1. calculate the sum of the strength of each output link multiplied by how much the target node has to change
        2. get derivative to determine how much weights need to change
        3. change the weights based on learning rate and derivative
        :param targets: y values
        :param N: learning rate
        :return: updated weights
        """
        if len(targets) != self.output:
            raise ValueError('Wrong number of targets you silly goose!')

        # calculate error terms for output
        # the delta tell you which direction to change the weights
        output_deltas = [0.0] * self.output
        for k in range(self.output):
            error = -(targets[k] - self.ao[k])
            output_deltas[k] = dsigmoid(self.ao[k]) * error

        # calculate error terms for hidden
        # delta tells you which direction to change the weights
        hidden_deltas = [0.0] * self.hidden
        for j in range(self.hidden):
            error = 0.0
            for k in range(self.output):
                error += output_deltas[k] * self.wo[j][k]
            hidden_deltas[j] = dtanh(self.ah[j]) * error

        # update the weights connecting hidden to output
        for j in range(self.hidden):
            for k in range(self.output):
                change = output_deltas[k] * self.ah[j]
                self.wo[j][k] -= self.learning_rate * change + self.co[j][k] * self.momentum
                self.co[j][k] = change

        # update the weights connecting input to hidden
        for i in range(self.input):
            for j in range(self.hidden):
                change = hidden_deltas[j] * self.ai[i]
                self.wi[i][j] -= self.learning_rate * change + self.ci[i][j] * self.momentum
                self.ci[i][j] = change

        # calculate error
        error = 0.0
        for k in range(len(targets)):
            error += 0.5 * (targets[k] - self.ao[k]) ** 2
        return error

    def test(self, patterns):
        """
        Currently this will print out the targets next to the predictions.
        Not useful for actual ML, just for visual inspection.
        """
        for p in patterns:
            print(p[1], '->', self.feedForward(p[0]))

    def train(self, patterns):
        # N: learning rate
        for i in range(self.iterations):
            error = 0.0
            random.shuffle(patterns)
            for p in patterns:
                inputs = p[0]
                targets = p[1]
                self.feedForward(inputs)
                error += self.backPropagate(targets)
            with open('error.txt', 'a') as errorfile:
                errorfile.write(str(error) + '\n')
                errorfile.close()
            if i % 10 == 0:
                print('error %-.5f' % error)
            # learning rate decay
            self.learning_rate = (self.learning_rate * (self.learning_rate /
                                  (self.learning_rate + (self.learning_rate * self.rate_decay))))

    def predict(self, x):
        """
        return list of predictions after training algorithm
        """
        predictions = []
        for p in x:
            predictions.append(self.feedForward(p))
        return predictions


def key_str_to_list(s):
    l = list()

    for line in s.split("\n"):
        if line == "":
            continue
        for c in line.split(" "):
            if c == "":
                continue
            if c == "00":
                l.append(1)
            elif c == "01" or c == "FF":
                l.append(0)
            else:
                raise Exception()
    return l


def key_list_to_str(l):

    m = ""
    n = ""
    for (i, c) in enumerate(l):
        if i % 0x14 == 0 and i != 0:
            m += n + "\n"
            n = ""

        if c == 0x00:
            n += "FF "
        elif c == 0x01:
            n += "00 "
        else:
            raise Exception()
    m += n
    return m


def get_coefs(i_seg=0):

    payload = open("196", "r").read()
    seg_len = 0x80A20
    segment = payload[i_seg * seg_len: (i_seg + 1) * seg_len]

    c1_coefs = list()
    start = 0xC90

    for i in range(0xA0):
        coefs = list()
        offset = start + (i * 0xCA8)
        bias = struct.unpack("<d", segment[offset:][:8])[0]

        for j in range(0x190):
            offset = start + (i * 0xCA8) + 8 + (j * 8)
            coef = struct.unpack("<d", segment[offset:][:8])[0]
            coefs.append(coef)
        coefs.append(bias)
        c1_coefs.append(coefs)

    c2_coefs = list()
    start = 0x7F590

    for i in range(0x4):
        coefs = list()
        offset = start + (i * 0x528)
        bias = struct.unpack("<d", segment[offset:][:8])[0]

        for j in range(0xA0):
            offset = start + (i * 0x528) + 8 + (j * 8)
            coef = struct.unpack("<d", segment[offset:][:8])[0]
            coefs.append(coef)
        coefs.append(bias)
        c2_coefs.append(coefs)

    def invert_matrix(m):
        width = len(m[0])
        height = len(m)

        matrix = list()
        for x in range(width):
            matrix.append([0] * height)

        for i in range(height):
            for j in range(width):
                matrix[j][i] = m[i][j]
        return matrix

    c1_coefs = invert_matrix(c1_coefs)
    c2_coefs = invert_matrix(c2_coefs)

    return (c1_coefs, c2_coefs)


def get_keys_from_segments():
    payload = open("196", "r").read()
    seg_len = 0x80A20

    keys = list()

    keys_name = [
        "key_1",
        "key_2",
        "key_3",
        "key_4",
        "key_5",
        "key_6",
        "key_7",
        "key_8",
        "key_9",
        "key_0",
        "key_1",
        "key_2",
        "key_3",
        "key_4",
        "key_5",
        "key_6",
        "key_7",
        "key_8",
        "key_9",
        "key_0",
        "key_1",
        "key_2",
        "key_3",
        "key_4",
        "key_5",
        "key_6",
        "key_7",
        "key_8",
        "key_9",
        "key_0",
        "key_1",
        "key_2",
    ]

    for i_seg in range(0x20):
        segment = payload[i_seg * seg_len: (i_seg + 1) * seg_len]
        img = list()

        for j in range(0x190):

            offset = j * 8
            pixel = struct.unpack("<d", segment[offset: offset + 8])[0]
            img.append(int(pixel))

        keys.append([keys_name[i_seg], key_list_to_str(img)])
    return keys


def crack():

    keys = get_keys_from_segments()
    for i_seg in range(0x20):
        print "[SEGMENT %02X]" % i_seg
        (c1_coefs, c2_coefs) = get_coefs(i_seg)

        all_results = list()

        for (i, key_t) in enumerate(keys):
            nn = MLP_NeuralNetwork(
                400, 160, 4, iterations=1, learning_rate=0.5, momentum=0.5, rate_decay=0.01,
                wi=c1_coefs, wo=c2_coefs
            )
            key = key_str_to_list(key_t[1])
            predict = nn.predict([key])[0]
            all_results.append((key_t[0], predict))

        sorted_results = dict()
        for (name, (a, b, c, d)) in all_results:
            if a < 0.15 and b < 0.15 and c < 0.15 and d < 0.15:

                if a + b + c + d in sorted_results:
                    # sorted_results[a + b + c + d].append((name, a, b, c, d))
                    pass
                else:
                    sorted_results[a + b + c + d] = [(name, a, b, c, d)]

        for k in sorted(sorted_results.keys()):

            for (name, a, b, c, d) in sorted_results[k]:
                print "\t\t[%s] %-18s %-18s %-18s %-18s" % (name, a, b, c, d)


if __name__ == '__main__':
    crack()

[SEGMENT 00]    [key_2]   0.00397893338914   9.07235902734e-05  0.0107712598283    0.000232385338803
[SEGMENT 01]    [key_3]   0.000150258845603  0.00114426186293   0.000433806215538  0.002511883198
[SEGMENT 02]    [key_4]   0.108925819944     0.00115368702028   0.00129610047726   0.0147632379909
[SEGMENT 03]    [key_2]   0.00065248920998   0.00256627434545   0.0202907449627    0.0401688858947
[SEGMENT 04]    [key_5]   0.000285190456697  6.55283249582e-06  0.0321615691355    0.0015937999122
[SEGMENT 05]    [key_0]   0.0190255676432    0.0196549852386    0.00652014658993   0.0476222710845
[SEGMENT 06]    [key_3]   0.000474280459947  0.00272898099755   0.00651642879153   0.000534862879727
[SEGMENT 07]    [key_8]   0.00107047285023   0.0131861677783    0.00337426300349   0.000104422901887
[SEGMENT 08]    [key_4]   0.0346358091297    0.00930722886713   0.00242711216706   0.011591411228
[SEGMENT 09]    [key_7]   0.000393501107416  7.98020429957e-05  0.0357698452026    0.00136188206515
[SEGMENT 0A]    [key_2]   0.00576687209341   0.00949866623292   0.0989526545005    0.0567218408648
[SEGMENT 0B]    [key_5]   0.000155003778542  0.00131494723523   0.00839285962663   0.00335151235461
[SEGMENT 0C]    [key_0]   0.00224962920516   0.00489149726988   0.000433849175192  0.000329701371296
[SEGMENT 0D]    [key_8]   0.00173092573784   0.0173238728053    0.0127146052958    0.00489559697394
[SEGMENT 0E]    [key_2]   0.00350636399461   0.00638949555104   0.0634907320975    0.0471890435774
[SEGMENT 0F]    [key_8]   0.000278742716932  0.00532683301239   0.0242360245219    0.0358726261742
[SEGMENT 10]    [key_7]   0.000209201047605  0.00029882487981   0.034428313666     0.00349307557916
[SEGMENT 11]    [key_3]   3.73974302239e-05  0.000642477692785  0.00775703231443   0.000918657566987
[SEGMENT 12]    [key_3]   3.76019766248e-05  0.0712536752451    0.0147318138922    9.69598837011e-05
[SEGMENT 13]    [key_5]   0.000380348322377  9.99852640963e-06  0.0126060266585    0.000794662599401
[SEGMENT 14]    [key_7]   0.00569940933423   6.89805165781e-05  0.0579083006042    0.00139462956296
[SEGMENT 15]    [key_7]   0.000277163691104  0.0215380161339    0.00712988966144   0.00191881284308
[SEGMENT 16]    [key_2]   3.69492309925e-05  0.00873378608598   0.00458676123513   0.0435942672486
[SEGMENT 17]    [key_0]   0.00836409404569   0.038251037843     0.000714150023095  0.00697239126548
[SEGMENT 18]    [key_8]   0.0042862025067    0.0529439318063    0.0683031295941    0.00181514514501
[SEGMENT 19]    [key_5]   0.000243845251903  2.48170433659e-06  0.00637746499481   0.00154341735812
[SEGMENT 1A]    [key_5]   0.0187191509367    0.000112259715837  0.00577404118398   0.0420927528949
[SEGMENT 1B]    [key_4]   0.0310279272703    0.0287967340397    0.000263293275743  0.00977839831836
[SEGMENT 1C]    [key_4]   0.0913491223826    0.00510462882831   0.000901543952428  0.0291667409991
[SEGMENT 1D]    [key_0]   7.17584533219e-05  0.0128361970354    0.00444086344897   0.00124566527801
[SEGMENT 1E]    [key_3]   0.000499119736394  3.56956322264e-05  0.00407884000424   0.00216085973974
[SEGMENT 1F]    [key_5]   0.000860633194031  0.00108052584886   0.0148795661128    0.0324703351717