3
$\begingroup$

This is a garage made encryption scheme provided as cryptanalysis practice during 34C3 CTF.

The challenge is done under the following assumptions

  1. All Mersenne twister instances are MT19937 64bit version
  2. All calculations are mod $2^{64}$
  3. Vector here means a Matrix of dimentions $N\times1$ not to be confused with vector data structure.

Psuedocode for helper function used for key generation and the encryption routine:

function secure_word(mersenne_twister mt):
    random: 64 bit integer
    for (i = 0; i < 64; i = i + 1)
        random |= (mt.next_random_number() & 1) << i;
    return random;

function encrypt(string Message):
    M = vector where each character in Message is element in M
    L = length of the vector M
    constant_mt = mersenne twister with seed (0)
    A = 64xL matrix
    for row in A.rows:
        for column in A.columns:
            A[row][column] = constant_mt.next_random_number()
    K = vector of length 64
    secure_mt = mersenne twister with secret random 64bit seed
    for (i = 0; i < K.length; i = i+1)
        K[i] = secure_word(secure_mt)
    CipherText = A*M+k
    return length of M the CipherText

EDITS Our goal is to recover Message M given Cipher text C and constant Array A

Here is my analysis:

  1. CipherText will always be of fixed length (64 Integers) regardless of the length of the message, so it doesn't sound like encryption algorithm. Due to pigeonhole principle problems will when length of Message is greater than or equal to 64. For the sake of this problem we knew in advance that length of M was 37 so we should be safe from collisions due to pigeonhole principle.
  2. The seed space here is $2^{64}$, so it can be brute forced, but I was hoping a reduced search space or much better eliminating the need for brute force at all then solve it as Closest vector problem.
  3. Mersenne twister is cryptographically insecure algorithm, we use 4096 bits generated by 4096 rounds of MT for K, If one can reduce the number of independent variables required to form these bits (since we are only dealing with 1 bit) to be less than 27. The equation CipherText = A*M+k can be solved as system of multivariate linear equations mod N with relatively small solutions, it could be possible to transform it into Closest Vector Problem and solving it using LLL, one can guarantee that there exist small solution since each element of M has an upper limit of 255 (or can be squeezed to little less number). The problem here is that I failed at finding less than 27 independent variables where all the 4096 bits can be calculated from.

The question is the following: Is brute force attack described in (2) the only possible attack on this scheme ? If it is not is the approach described in (3) the right way to attack truncated Mersenne Twister when being used in cryptographic schemes like this one.

Also any comments on my analysis is appreciated.

EDITS Here is what are we given:

  1. The encryption algorithm implemented in C++, The peusdocode above represents its essence. However here is the full code, should you need to check it.

    #include <bits/stdc++.h>
    using namespace std;
    
    struct RNG {
        random_device dev;
        mt19937_64 rng;
        RNG() : dev(), rng(dev()) {}
        RNG(uint64_t seed) : rng(seed) {}
    
        bool next_bit() { return rng() & 1; }
    
        // For when we want to hide the RNG state
        uint64_t next_qword_safe() {
            uint64_t res = 0;
            for (int i = 0; i < 64; ++i)
                res |= next_bit() << i;
            return res;
        }
    
        // For when we don't care about security
        uint64_t next_qword_fast() {
            return rng();
        }
    };
    
    using Vector = valarray<uint64_t>;
    
    struct Matrix {
        vector<Vector> elements;
        Matrix(int rows, int cols)
            : elements(rows, Vector(cols)) {}
    
        auto rows() const { return elements.size(); }
        auto cols() const { return elements[0].size(); }
    
        auto operator*(const Vector& v) const {
            assert(v.size() == cols());
            Vector res(rows());
            for (size_t i = 0; i < rows(); ++i) {
                Vector mul = elements[i] * v;
                res[i] = accumulate(begin(mul), end(mul), uint64_t{0});
            }
            return res;
        }
    
        void fill(RNG* rng) {
            for (auto& row : elements)
                for (auto& x : row)
                    x = rng->next_qword_fast();
        }
    };
    
    constexpr int key_size = 64;
    
    void write64(ofstream& o, uint64_t x) {
        o.write(reinterpret_cast<const char*>(&x), sizeof x);
    }
    
    int main(int argc, const char **argv) {
        if (argc != 2) {
            cerr << "Usage: " << argv[0] << " filename" << endl;
            return EXIT_FAILURE;
        }
    
        string filename(argv[1]);
        ifstream in(filename, ios::binary);
    
        string input;
        in >> input;
        Vector plaintext(input.size());
        copy(input.begin(), input.end(), begin(plaintext));
    
        // Generate deterministic helper matrix A
        Matrix A(key_size, plaintext.size());
        {
            RNG rng(0);
            A.fill(&rng);
        }
    
        // Generate random key
        Vector key(key_size);
        {
            RNG rng;
            for (auto& x : key)
                x = rng.next_qword_safe();
        }
    
        Vector cipher = A * plaintext + key;
    
        // Write ciphertext
        ofstream out(filename + ".enc", ios::binary);
        write64(out, plaintext.size());
        for (auto x : cipher)
            write64(out, x);
    
        // TODO Store key somewhere
    }
    
  2. File encrypted with the above cipher, I uploaded the base64 encoded version of it so it can be placed here

    JQAAAAAAAAD/MAQmuQzqGXFX/eyEVk5UrRvze3Tj3EvV4Ghur2iVyEzk9UQp8Xkz05SU5HcQPZJb
    cST6BzYeBuCYt/qZHuVMXAaNfoLl6N+Xe5ScvGxRzPNRzI8gmnbqp5WWPkVPmdnS/OGnAJb+cY/h
    J2u95AUn77+Q7b6E4pz/8bJaUMtSE8Qih1xzomDQz96sx9ZIdL9xzg8kCPQoDOCfM1NIRtJpiYxX
    oVhmFTo0AMX1dL+CRg4ovto1675CX1MIcBCD9XlGDtV0Ya/AdJDZnFC99T+gZZmEAMSq9/a+RQa2
    WwDm8CPXwNQUQKx4U+0DI6Nm09Ve5V1gZUqmf8zsA0+uKnQ8gWoHmIeM8I1bfFFi4bnwq/vGRSKl
    C6ns3MrFT+WQpI28uqjl/rJh3x96LSOH8OUyLzFswM6XhEmFaTgqKBk+kTmoJS7WSg0AIZsOhwJg
    1jHn20FL+hzdToKRX0Hjj9k956fSlnvEpQ9BY78HkmDhn8sdCCZlI8HfpxVTxKa0pIfgh31HKpvN
    6Ro4sW2IP2LyAhoy+MK/h1k/E+igRCDjdhrDKVc2SWew2K5qS10OmD5Z/Msz6Z/rUhWYXqNZXNBU
    lCYl1InheVrtvB45X8T3vrrg+cEDH1zYFJtZJ4LSVbTZa1ESrE27xD4PNNKnnzSponszUvGZOZxg
    akDW7EbKFQ==
    
$\endgroup$

closed as off-topic by fkraiem, e-sushi Aug 21 '18 at 0:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Seems trivial to break with A and M known by CPA of M = [0,0,0,...]. A*M+k = k in that case, right? Given k then any cipher text can be mapped back to a set of possible plaintexts. As you note, the encryption does not appear to be bijective. $\endgroup$ – Matthew Fisher Aug 20 '18 at 2:43
  • $\begingroup$ but we are not given an encryption oracle, I will edit the question to clarify that. $\endgroup$ – oddcoder Aug 20 '18 at 9:23
3
$\begingroup$

To directly answer your question, No brute force is not the only way to break this cipher.

As I noted in the comment, sending the all 0's text in breaks it immediately. This alone indicates that the scheme is deeply flawed. This is an example of a Chosen Plaintext Attack.

Even a few known plaintext will reveal the key. Known Plaintext Attack

Seems like a differential M^M1 will also give the key quickly. Differential Cryptanalysis

Ciphertext only attacks are not generally considered with modern ciphers. I didn't give it a lot of thought but there is likely a ciphertext only attack as well. Generally, an oracle is considered to be available due to Kerckhoff's Principle.

With a single ciphertext, this scheme (hash?) looks difficult to analyze. Given unlimited ciphertext, there is sure to be a differential attack. If two input blocks differ in just the last bit, the output will be nearly identical and will suggest a key bit. I believe this strategy can be used to peel the key bits one by one with only the ciphertexts if the plaintext is in a known language.

Analyzing these kind of 'weak' ciphers is a great way to build your knowledge. Work up through toy to real but broken cipher like DES, RC4, MD5 and understand how they were broken. Great fun and maybe some profit.

$\endgroup$
  • $\begingroup$ Hey matthew, thank for your answers but there are few misconceptions First regarding Schneier's Law, I am not the author of this cipher, it was created as practice for cryptanalysis during a security CTF event associated with the 34th Chaos Computer Club conference. While I agree that known plaintext would help and same if there is a oracle for chosen plaintext, but it wasn't the case here, We were supposed to solve it under very limiting constrains which I presented, and Normally there is a way to solve it under the given constrains but I can't reach the author. $\endgroup$ – oddcoder Aug 20 '18 at 14:34
  • $\begingroup$ I added some idea for a differential ciphertext only attack $\endgroup$ – Matthew Fisher Aug 20 '18 at 15:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.