What to do when crib dragging does not work in OTP (One-time pad) ciphers? With a Cipher text of

7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B
73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B
64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B
7AC24F5EAF17F0A0754D5834BC3CC3A90ABD7B2A52C222ABC89B
72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B
73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A
74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B

It is assumed that each line is a different message encrypted with the same pad.

I have tried countless lengths of words that are supposed to lead me somewhere to the decryption of this cipher, however isn't it just downright impossible to "guess" your way to the answer?

Crib dragging does not seem to work since there seem to be too many possibilities…

I'm going to assume this isn't homework because otherwise reading this answer would count as cheating. If it is homework please tell me so I can delete this answer.

Crib dragging does work, you just need to be more persistent. I wrote a script (available via GitHub) that answers your question:

#Use this tool to solve multi-time pads
#Written on 4th march 2016
#Took me a good 30 minutes
#How this tool works:
#Suppose you guess a crib " the "
#We have n messages each of length k
#For each of the n messages and at each position k we want to guess the crib
#However, we can make our lives vastly easier if we guess the other way round:
#Instead of guessing each message separately, we guess at the same position for all the messages at the same time
#This will make it easier to spot when crib for message m at position k produces the wrong output for any other message
#Therefore, what this program does is to guess for each combination of message and position the crib for all messages at position k
#Suppose at message m position k the plaintext is " the ", then we can derive the key at position k with the length of our crib
#Once we have derived that part of the key we then apply it to the rest of the messages to see if we get a sensible output
#Therefore for any crib there are n * k outputs where n is the number of ciphertexts and k is the length of each ciphertext
#Each output is n strings of characters representing the "decoded" portion of each message at position k

#Todo: Use a dictionary to automate this.

from itertools import combinations
a="7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B"
b="73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B"
c="64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B"
d="72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B"
e="73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A"
f="74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B"
crib = " the ".encode("hex")
#data = [line.strip() for line in open("20k.txt", 'r')]

binary_a = a.decode("hex")
binary_b = b.decode("hex")
binary_c = c.decode("hex")
binary_d = d.decode("hex")
binary_e = e.decode("hex")
binary_f = f.decode("hex")
L1=[binary_a,binary_b,binary_c,binary_d,binary_e,binary_f]

def xor_strings(xs, ys,i=0):
    return "".join(chr(ord(x) ^ ord(y)) for x, y in zip(xs[i:], ys))

def initial_drag(crib):
    '''for combo in combinations(L1, 2):
        xored= xor_strings(combo[0], combo[1]).encode("hex")
        print combo[0].encode("hex"), combo[1].encode("hex")
        print xored
        for i in range(27):
            print xor_strings(xored.decode("hex"),the2.decode("hex"),i)'''
    for cipher in L1:
        for position in range(len(cipher)-len(crib)):
            key = xor_strings(cipher,crib.decode("hex"),position).encode("hex") #when we XOR our crib with the ciphertext, we should get back the key
            for c in L1:
                print xor_strings(c,key.decode("hex"),position), cipher.encode("hex"),position #we then XOR the key we got back with the other ciphertexts
            print ""

def crib_drag(crib,ciphertext,position):
    key = xor_strings(ciphertext,crib.decode("hex"),position).encode("hex")
    for c in L1:
        print xor_strings(c,key.decode("hex"),position), c.encode("hex"),position #we then XOR the key we got back with the other ciphertexts

# Step 1. Do an initial crib drag through all possible key fragments for your crib.
initial_drag(crib)

# Step 2. Once you have found a valid key fragment, expand on that fragment. I did this manually in the interpreter.
crib_drag(" the ".encode("hex"),L1[4],5)
crib_drag("ble pr".encode("hex"),L1[0],4)
crib_drag("able pr".encode("hex"),L1[0],3)
crib_drag("able pri".encode("hex"),L1[0],3)
crib_drag("nese puzzle".encode("hex"),L1[1],3)
crib_drag("chinese puzzle ".encode("hex"),L1[1],0)
crib_drag("notable prisoner ".encode("hex"),L1[0],0)
crib_drag("do not disturb those ".encode("hex"),L1[5],0)
crib_drag("notable prisoner is freed ".encode("hex"),L1[0],0)

The difference between the method I used and the one posted elsewhere is that I drag the crib over all ciphertexts at the same time, whereas the one posted in the blog only compared a pair of ciphertexts at a time, making it much more prone to false positives compared to my method.

If you start with crib dragging using the as the crib then you will find

le pr
se pu
ree o
 clea
g tra
 the
t dis

When you assume that the 5th position of 73cc5457bf17e7a4750c5423b178d0a44fff756355c03cabc28a begins with the. This stands out because almost all the other results you get will have weird symbols or obviously nonsensical combinations of letters whereas this one looks like a possible fragment of a grammatically correct English sentence. From there onwards you just keep lengthening the crib to get the rest of the key.


ecdsa nonce reuse to compute the private key, modular inverse question I am following along some cryptography challenges:, in particular ECDSA Nonce Reuse here (second problem):
https://blog.coinbase.com/capture-the-coin-cryptography-category-solutions-fe94d82165c5
I understand all the math, except this part:
def modinv(a, modulus): return pow(a, modulus — 2, modulus)
def divmod(a, b, modulus): return (a * modinv(b, modulus)) % modulus

Why is it modulus - 2? Shouldn't it be modulus - 1? I thought the modular inverse of a mod n would be $a^{n-1}$? Since $a * a^{n-1} = a^n = 1$?
Is it something to do with the fact that the EC group is size order, but the "group in the exponential" is size order - 1? I don't really understand though. We need to compute the private key as $\frac{ks'-z}{r}$. But according to ecdsa: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm r and s are all calculated mod n? So why are we doing n - 2? But then confusingly, k is selected in the set [1, .., n-1].
So yeah just a clear cut explanation would be helpful. Thanks.
Thanks for the help!
Oh wait, maybe this is really dumb: we just want the private key, and the private key exists in the integer multiplicative group [1, .., n-1], which is size n-1.

You are looking for the modular inverse of $r$
By Euler's Theorem
$$a^{\phi(m)} \equiv 1 \pmod{m}$$
Then
$$a^{\phi(m)-1} \equiv a^{-1} \pmod{m}$$
Now, for a prime $p$, $\phi(p) = p-1$ then we have
$$a^{p-2} \equiv a^{-1} \pmod{p}$$

Note 1: The multiplicative group $\mathbb{Z}^*_p$ contains $p-1$ elements, the zero is not included.
Note 2: Not all elements of $\mathbb{Z}_m$ has multiplicative inverse. To have one, $x \in \{1,\ldots,m-1\}$ we must have $\gcd(m,x)=1$
Note 3: The order of Secp256k1 is prime.


Questions about OAEP for RSA I have two questions about OAEP for RSA.

How are the number of bits to pad with 0 chosen? For example, if I'm sending a 255 byte message with RSA-2048 I have 8 unused bits (1 byte). Should I split the remainder bits evenly so I pad with 4 zeroes and my $r$ is 4 random bits, or do I pick the number of bits to pad randomly?
Does it matter if the hash functions $G$ and $H$ are the same (e.g. if both are SHA-256)?

Variables are in reference to the ones in the diagram found in the Wikipedia article “Optimal asymmetric encryption padding”.

Bonus question: What's the proper technique for expanding and shrinking data using hash functions? Could I use the hash as a seed for a secure PRNG and then generate $n$ random bits, or is that wrong?

First off, the maximum size of a message you can use is determined by the desired length of the padding (in my case, I am using RSA-2048 so I wanted a final padded length of 256 bytes) and the hash function you are using.

The formula is messageLength = desiredLength - 2 * hashOutputSize - 1 (in my case, I wanted to use SHA-256 so hashOutputSize would be 32 bytes).

The number of zeroes padded is desiredLength - messageLength - 2 * hashOutputSize - 1. This can be 0 sometimes. There are not always padded zeroes…!

After reading “PKCS #1: RSA Cryptography Specifications Version 2.0”, I realize that this question isn't important/doesn't make a lot of sense.
Yes. The specification only calls for 1 hash function as a parameter, not two different ones.
Bonus Question

MGF1 is what I used for generating masks (i.e. "expanding and shrinking data using hash functions").

And if anyone is reading this in the future and needs more resources to understand OAEP, I translated it to Java code (this is OAEP, not RSA-OAEP). Also, not strictly related to the forum, but if you can program this might make things easier to follow along:

public class OAEP {
    public static void main(String[] args) throws Exception {
        byte[] myMessage = "I wonder if this will work".getBytes("UTF-8");
        byte[] padded = pad(myMessage, "SHA-256 MGF1", myMessage.length + 32 + 32 + 1);
        StringBuilder sb = new StringBuilder();
        for (byte b : padded) {
            sb.append(String.format("%02X", b));
        }
        System.out.println(sb.toString());
        byte[] unpadded = unpad(padded, "SHA-256 MGF1");
        System.out.println(new String(unpadded, "UTF-8"));
    }
    public static final SecureRandom random = new SecureRandom(); // Uhh you may want to replace this though
    public static byte[] SHA256(byte[] input) throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        return digest.digest(input);
    }
    public static byte[] MGF1(byte[] seed, int seedOffset, int seedLength, int desiredLength) throws NoSuchAlgorithmException {
        int hLen = 32;
        int offset = 0;
        int i = 0;
        byte[] mask = new byte[desiredLength];
        byte[] temp = new byte[seedLength + 4];
        System.arraycopy(seed, seedOffset, temp, 4, seedLength);
        while (offset < desiredLength) {
            temp[0] = (byte) (i >>> 24);
            temp[1] = (byte) (i >>> 16);
            temp[2] = (byte) (i >>> 8);
            temp[3] = (byte) i;
            int remaining = desiredLength - offset;
            System.arraycopy(SHA256(temp), 0, mask, offset, remaining < hLen ? remaining : hLen);
            offset = offset + hLen;
            i = i + 1;
        }
        return mask;
    }
    public static byte[] unpad(byte[] message, String params) throws Exception {
        String[] tokens = params.split(" ");
        if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
            return null;
        }
        int mLen = message.length;
        int hLen = 32;
        if (mLen < (hLen << 1) + 1) {
            return null;
        }
        byte[] copy = new byte[mLen];
        System.arraycopy(message, 0, copy, 0, mLen);
        byte[] seedMask = MGF1(copy, hLen, mLen - hLen, hLen);
        for (int i = 0; i < hLen; i++) {
            copy[i] ^= seedMask[i];
        }
        byte[] paramsHash = SHA256(params.getBytes("UTF-8"));
        byte[] dataBlockMask = MGF1(copy, 0, hLen, mLen - hLen);
        int index = -1;
        for (int i = hLen; i < mLen; i++) {
            copy[i] ^= dataBlockMask[i - hLen];
            if (i < (hLen << 1)) {
                if (copy[i] != paramsHash[i - hLen]) {
                    return null;
                }
            } else if (index == -1) {
                if (copy[i] == 1) {
                    index = i + 1;
                }
            }
        }
        if (index == -1 || index == mLen) {
            return null;
        }
        byte[] unpadded = new byte[mLen - index];
        System.arraycopy(copy, index, unpadded, 0, mLen - index);
        return unpadded;
    }
    public static byte[] pad(byte[] message, String params, int length) throws Exception {
        String[] tokens = params.split(" ");
        if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
            return null;
        }
        int mLen = message.length;
        int hLen = 32;
        if (mLen > length - (hLen << 1) - 1) {
            return null;
        }
        int zeroPad = length - mLen - (hLen << 1) - 1;
        byte[] dataBlock = new byte[length - hLen];
        System.arraycopy(SHA256(params.getBytes("UTF-8")), 0, dataBlock, 0, hLen);
        System.arraycopy(message, 0, dataBlock, hLen + zeroPad + 1, mLen);
        dataBlock[hLen + zeroPad] = 1;
        byte[] seed = new byte[hLen];
        random.nextBytes(seed);
        byte[] dataBlockMask = MGF1(seed, 0, hLen, length - hLen);
        for (int i = 0; i < length - hLen; i++) {
            dataBlock[i] ^= dataBlockMask[i];
        }
        byte[] seedMask = MGF1(dataBlock, 0, length - hLen, hLen);
        for (int i = 0; i < hLen; i++) {
            seed[i] ^= seedMask[i];
        }
        byte[] padded = new byte[length];
        System.arraycopy(seed, 0, padded, 0, hLen);
        System.arraycopy(dataBlock, 0, padded, hLen, length - hLen);
        return padded;
    }
}


Why hash ( clear text + Secret ) instead of hash (encrpt(clear text) [ + secret ] ) Here is an excellent article on how SSH Authentication and Encryption works.

While thinking about how MAC's work, I had the same doubt as one of the comments left on the post:

The client combines the decrypted number with the shared session key that is being used to encrypt the communication, and calculates the MD5 hash of this value. Any reason why the client combines the decrypted number with session key to calculate md hash? Why not calculate md hash directly for the decrypted value?

Is it just to avoid the negligible overhead of encrypting?

(Which will any way get masked after hashing and add no protection or value--assuming the shared secret size makes no difference for the hashing function.)

There's a general principle in cryptographic protocols that every message should contain a value that depends on previous messages in the protocol. (This isn't an absolute rule, but it's usually the case.) Otherwise a man-in-the-middle might be able observe multiple runs of the protocol and combine parts of messages from different runs in unexpected ways.

I'm going by the description of the protocol on the tutorial you link to, which I think doesn't match the actual protocol (or is it SSH1? SSH2 uses the private key to sign, not to encrypt). The relevant steps are:

  3. If a public key with matching ID is found in the file, the server generates a random number and uses the public key to encrypt the number.
  4. The server sends the client this encrypted message.
  5. If the client actually has the associated private key, it will be able to decrypt the message using that key, revealing the original number.
  6. The client combines the decrypted number with the shared session key that is being used to encrypt the communication, and calculates the MD5 hash of this value.
  7. The client then sends this MD5 hash back to the server as an answer to the encrypted number message.

In step 3, the server generates a nonce and encrypts it with the public key. In step 5, the client demonstrates that it possesses the private key by using it to decrypt the nonce. In step 7, the client sends a value to the server which demonstrates that it was able to decrypt the nonce.

Now consider an active man-in-the-middle, which the protocol is supposed to defend against. The MitM waits for the legitimate client to start a session to the legitimate server, but hijacks the messages so that the legitimate client is actually talking to the MiTM, and the MitM starts its own session with the legitimate server in parallel.

The legitimate server generates a nonce $N$ (step 3) and sends the encrypted nonce $E_{\mathrm{privkey}}(M)$ to the MitM (step 4).
The MitM receives the encrypted nonce and transmits that to the legitimate client instead of generating and encrypting its own nonce. (The MitM is an attacker, so it can cheat: it doesn't have to follow the protocol correctly.)
The legitimate client receives an encrypted nonce, decrypts it and generates a hash containing it $H(N || \ldots)$ (steps 5–7).
The MitM receives $H(N || \ldots)$ and sends that to the legitimate server.

If the hash only depended on the nonce, then the MitM would be able to send a value to the server that authenticated it as a client possessing the private key. This would be a bug in the protocol.

To avoid this attack, the hash also depends on the shared session key. This shared session key is generated by a Diffie-Hellman key exchange. The DH algorithm guarantees that the resulting key depends on inputs from both sides. Therefore the session key used between the MitM and the legitimate server is different from the session key used between the legitimate client and the MitM. Since the hash calculated at step 6 includes this session key, the proof of possession expected by the server at step 7 is different from every session, which prevents a man-in-the-middle from reusing the proof of possession from another session.


Proof Dlog is hard in generic group model I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?

The lower bound for the generic group model is proved by Victor Shoup,

He showed in Lower bounds and Discrete Logarithm and Related Problems

  Lower bounds on the complexity of these problems are proved that match the known upper bound: any generic algorithm must perform $\Omega(p^{1/2})$ group operations, where $p$ is the largest prime dividing the order of the group.

Generic Group model;

To process with a group we must present them with bit strings. This must be a bijection, 1-1 and onto. A generic algorithm works independently from the representation of the group. They are not allowed to work with efficient representation as field and rings instead they are working with an oracle with the random representation $\sigma$ of the group. The oracle executes the group operation $$\text{add}(\sigma(a),\sigma(b)) = \sigma(a+b)$$ and $$\text{inv}(\sigma(x)) = \sigma(-x) $$ The running time is measured by the number of oracle calls.

The importance of this model is providing an answer to the question

What is the fastest generic algorithm for breaking a cryptographic hardness assumption?

The lower bound for the generic group model is proved by Victor Shoup. It is proven that any algorithm with constant success probability has at least $\mathcal{O}(\sqrt{q})$-time where $q$ is the largest factor of the group size $n$. The generic algorithms are

Baby-step Giant-step needs an upper bound knowledge of the group size and has running time $\mathcal{O}(\sqrt{n} \log n)$.
The Pohlig-Hellman algorithm needs the prime factorization of $n$ and has $\mathcal{O}(\sqrt{q} \log q)$ complexity.

Generic Group model has the same problem as the Random Oracle model - Real model vs Ideal model. It can be shown that Cryptographic schemes can be secure under the generic group model but trivially broken if instantiated 1,2


the decryptNode function for leaf nodes in CP-ABE Can someone please explain to me why decryptNode gives as result $e(g,g)^rq(0)$ for leaf nodes, I don't understand how they went from the second step to the third (here is the article: Ciphertext-Policy Attribute-Based Encryption), also note that there is an error in the second step, it's $g^q(0)$ and not $h^q(0)$

Since $H$ is a hash that projects into $\mathbb{G}_0$, one must be able to write $H(i)$ as $g^z$ for some unknown $z$, because $g$ is a generator of $\mathbb{G}_0$.

\begin{eqnarray*}
\text{DecryptNode(CT,SK,}x\text{)} & = & \frac{e(D_i, C_x)}{e(D^{'}_i, C^{'}_x)} \\
& = & \frac{e(g^r\cdot H(i)^{r_i}, g^{q_x(0)})}{e(g^{r_i}, H(i)^{q_x(0)})} \\
& = & \frac{e(g^r, g^{q_x(0)})\cdot e(H(i)^{r_i}, g^{q_x(0)})}{e(g^{r_i}, H(i)^{q_x(0)})} \\
& = & \frac{e(g^r, g^{q_x(0)})\cdot e(g^{z r_i}, g^{q_x(0)})}{e(g^{r_i}, g^{z{q_x(0)}})} \\
& = & \frac{e(g, g)^{r{q_x(0)}}\cdot e(g, g)^{z r_i {q_x(0)}}}{e(g, g)^{r_i z{q_x(0)}}} \\
& = & e(g, g)^{r{q_x(0)}}.
\end{eqnarray*}

The last step works because $e(g, g)^a\cdot e(g, g)^{-a} = 1$.


secretKey ⊕ (secretKey ≪ 1), is randomness lost? A truly random secret key is run through a cipher

secretKey ⊕ (secretKey  ≪ 1)

is randomness lost? As in, is the computational cost to guess the ciphertext from secretKey ⊕ (secretKey << 1) lower than the cost to guess secretKey?

While bmm6o's answer is correct, I want to give another angle onto things.

The function / transformation you described is linear! Specifically, it is a linear function over the vector space $\mathbb F_2^n$ if you consider $n$-bit inputs. Now this means, that you can apply all the tricks you learned in linear algebra to this transformation, which is characterized by the following matrix for $n=4$ (assuming $\ll$ denotes cyclic shift instead of logical shift):

\begin{equation}
\begin{pmatrix}
x_1'\\x_2'\\x_3'\\x_4'
\end{pmatrix}
=
\begin{pmatrix}
1&0&0&1\\
1&1&0&0\\
0&1&1&0\\
0&0&1&1
\end{pmatrix}
\cdot
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}
\end{equation}

If $\ll$ denotes logical shift (i.e. fill up on the right with 0 instead of what was pushed out), then simply replace the top-right $1$ with $0$.

As it turns out, if you have the top-right $1$, the determinant of the matrix is $0$ which also means, the transformation is not a permutation, as there's no unique inverse function!

However, if we use the version with a logical shift instead, we always get a determinant of $1$ and thus the confirmation that this indeed describes a permutation (and if we want to, we can also invert it).

To see the above assertions, let's call the matrix $A$ and the value of the top-right bit $b$. Note $A-I$ is the companion matrix to the polynomial $x^n-b$, which means the characteristic polynomial of $A-I$ is $x^n-b$. Now the characteristic polynomial of a matrix $B$ is equal to $\det(B-xI)$, which in our case is $\det((A-I)-xI)=\det(A-(x+1)I)$ which for $x=-1$ yields $\det(A)=(-1)^n-b$, however in $\mathbb F_2$, $-1$ is equal to $1$, meaning $\det(A)=1-b$, which implies that the key transformation is invertible (and thus entropy-preserving) iff a logical instead of a cyclical shift is used for all values sizes of the input and output! Credit goes to Will Jagy for the inspiration (and for a shorter, but more mathy explanation).


Is password-based AES encryption secure at all? For a few years I have put all my passwords in a text file and encrypted that file with a password using a software solution (Axcrypt) which uses AES-128. The password is not really strong, but I thought AES encryption would make it strong somehow.

But it always bothered me how this can be secure and now that I have read a little about encryption it seems to me that this actually has nothing to do with AES encryption. Because when using a password instead of directly providing the key, the AES encryption becomes completely irrelevant. It doesn't matter anymore how many billion years it takes to crack AES because the only thing that now needs to be cracked is my password. The attacker finds my file, downloads Axcrypt, and bruteforce/dictionary attacks it until it's cracked. The attacker won't need to bruteforce my file with 128bit keys, he bruteforces it with passwords.

So I have two questions:

Am I right? Is it completely pointless to use passwords to AES encrypt files?
Axcrypt website recommends using a 22-characters-long password to achieve 128 bit security. Will a 22 character password be as secure as a randomly generated key? How?

(I know the actual key is derived from the password with an algorithm. I just can't understand how a password can be secure. The very existence of a password means the attacker will no longer have to deal with AES and keys, only with passwords)

You are correct in that the best strategy for an adversary would be to guess the password, as opposed to cryptanalysis of AES plaintext/ciphertexts. However, this does not make encryption pointless - password based key derivation is a challenge unto itself, separate from encryption, but one that does have practical solutions.

We can strengthen this weak link by making it require a large amount of time to derive the key from the password. If an adversary can only test a handful of passwords per second, then the probability that they will be able to crack a given password drops dramatically.

Granted, this is not a perfect solution - You might need to derive your key on a slow, old computer, while your adversary might have access to a distributed network armed with GPUs and FPGAs. So there is a balance to be had between how long it takes you to derive your key (which must be quick enough) and how long it takes an adversary to guess passwords (which must be slow enough).

Typically a duration of 1 second per derivation attempt is considered appropriate. However, the actual time duration required to compute a hash does not remain constant, even if you iterate the function a constant number of times. This is due to the way computing power scales with time - the iteration count you use to secure your password today may not protect you nearly as well in a few years.

As to whether or not a 22 character password is equivalent in strength to an 128 bit key, this is not a question that can be answered with a simple "yes" or "no" - for example, if your 22 character password is 1010101...10, then no, it absolutely does not have nearly as much entropy as a uniformly random 128 bit value. If your 22 character password consists of 3-4 english words with spacing, it does not have nearly as much entropy as a 128 bit random value.


Understanding a Blowfish cryptanalysis I'm reading a cryptanalysis on Blowfish, and I've come across something that I don't quite get. Let's denote

$$\delta = a \oplus a'$$

where a and  a' are bytes that cause a collision in some S-box when entered as the position to use in said box.

The structure of Blowfish looks like this:

with N+2 positions in P, where N is the number of rounds. Every zero represents one zero-byte. For each plaintext pair where
$$P \oplus P' = [0000\delta000]$$
we will get some corresponding ciphertext pairs where
$$C \oplus C' = [\delta000xyzt]$$
We denote
$$C = (L,R)$$
Now, the cryptanalysis claims that we have the equation
$$F(L \oplus P_{N+2}) \oplus F(L \oplus P_{N+2} \oplus [\delta000]) = [xyzt]$$
This is where I get stuck. I don't really see the connection, as the last position in the subkey array P is actually never part of any input to F(), except for in the decryption function, but I don't see how we end up with this algorithm that way either. Any ideas?

The article where I found the equation can be found here.

There seem to be some errors or inconsistencies in the question.

If $P \oplus P' = [0000\delta 000]$, and we use the 2-round structure shown in the picture, then the corresponding ciphertext pairs should satisfy $C \oplus C' = [xyzt\delta000]$.  This is different from what you wrote (did you omit the final swap shown in the picture above?).

If we let $C=(C_L,C_R)$ and $P=(P_L,P_R)$, etc., then one correct equation is:

$$F(C_R) \oplus F(C'_R) = [xyzt].$$
This follows because, if you look at the picture, the input to the $F$-box in the second (last) round is the same as the right half of the ciphertext.

Note that this is different from what you wrote.  (I cannot explain what you wrote; perhaps your notation does not match the picture you included, or something else.)

Edit: Now that you added a link to the paper where you got this from, I can explain what's going on.

First, at a high level: this is not the right first paper to learn differential cryptanalysis from.  You first need to understand the fundamental concepts of differential cryptanalysis before you will be prepared to understand that article.  That paper is a research paper written for expert cryptographers, who can be assumed to know those concepts.  It is not intended to be understandable to someone who does not already know advanced concepts of differential cryptanalysis.  Trying to explain the article to someone who does not understand those differential concepts is going to be ... challenging.

So, my primary recommendation is to go learn about differential cryptanalysis first, before trying to read that article.  There are good sources on this (you can search this site).  One of my favorites is Biham & Shamir's little book, Differential Cryptanalysis of the DES; it gives an excellent introduction to the topic.  But there are other sources as well.  Whatever source you read, make sure you understand the following concepts: differential characteristic, iterative characteristic, 1-R attack, 2-R attack, distinguishing attack, key-recovery attack.

Once you know those concepts, I can explain concisely what it is going on the particular paper you are referring to.  They are using a 2-R attack on Blowfish.  As a special peculiarity of Blowfish, after doing the last 2 rounds of Blowfish, you xor the output with two key values ($P_{10}$ and $P_{11}$ in this case).  That's not shown in your picture.  So, once you take that into account, the input to the last-round $F$-box will be $C_L \oplus P_{10}$, or $L \oplus P_{10}$ in the paper's notation.  Also since the two ciphertexts satisfy $C_L \oplus C'_L = [\delta000]$ (or in the paper's notation, $L \oplus L' = [\delta000]$.  Therefore, the input to the last-round $F$-box in the first encryption is $L \oplus P_{10}$, and the input to the last-round $F$-box in the second encryption is $L' \oplus P_{10} = L \oplus P_{10} \oplus [\delta000]$.  The equation shown in the paper then follows.

If that didn't make sense to you, I apologize, but you'll probably need to spend more time becoming expert at differential cryptanalysis before you'll be able to follow this paper.


PRP, PRF change at next selection? This is probably a silly question, and similar question was asked before; but  I can not figure out what actually is PRP/PRF. For example, it is commented that:

  A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set.

Now, does that mean, everytime we speak of a PRF; we randomly choose a new function from all such possible functions? Or, after we have chosen the function, we use it for sometime?

A PRF is indistinguishable from a function sampled at random from the set of all functions with the same domain and range. But that does not means that you need to pick a function at random across all possible functions to get a PRF. That can clearly not work: a random function has, with very high probability, a circuit of exponential size. So you cannot sample such a function in polynomial time, yet alone actually evaluate it on an input.

Sampling a PRF will be done by sampling it from a much smaller set, that contains only functions with a bounded polynomial size. Think of a PRF as a family of functions $\{f_k\}_{k \in \{0,1\}^\lambda}$, and sampling a function from this set is done by simply sampling its index $k$ - i.e., the key of your PRF. Note that even though they are easy to sample, there are $2^\lambda$ such $f_k$, so it is not implausible that an adversary that runs in polynomial time cannot distinguish a sample from this "small" (but still exponential-size) family, from a sample from the set of all functions. Note also that the adversary does not get the functions themselves when he tries to distinguish the set they have been sampled from - rather, he gets black-box access to the input-output behavior of the function.

Then, once you sample a single PRF key, you can use the same function for arbitrary polynomially many evaluations, since the function remains indistinguishable from a random function for the adversary, even if he gets to see an arbitrary polynomial number of evaluations of the function.


Why perfect secrecy can be ensured when a plain message and a cipher-text based on one-time pad are correlated? First, some well-known results are as follows.
For random variables $X$ and $Y$, we have
$$H(X,Y) \leq H(X) + H(Y).$$ The equality is achieved when $X$ and $Y$ are independent.

Second, in one-time pad, random variables $M$, $K$ and $C$ are used to denote a plain text, a private key and the codeword generated by $M \bigoplus K$ (modulo-2 operation), respectively. Note that $K$ is independent of $M$. We assume an eavesdropper also received the transmitted codeword $C$ through a public channel, but he does not know the key $K$.

Then my questions are as follows?

1) Are $M$ and $C$ correlated?
(The answer is "Yes" to me due to the post https://math.stackexchange.com/questions/1218305/if-x-and-y-are-correlated-random-varibales-and-z-is-independent-of-x-and-y-then )

2) If they are correlated, $H(M|C) < H(M)$ should be true according to the statements in the beginning. However, in one-time pad, perfect secrecy can be achieved, which means $H(M|C) = H(M)$ when $H(M) \leq H(K)$. Can anyone help me out of this confusion?

Thank you very much in advance.

Are M and C correlated?

No.

The distribution that the values the M and C may take on are independent of each other.  The condition probability distribution that M has is unchanged no matter what the observed C value is.

This is true whether you are using the statistical meaning of correlation, or whether you are looking more specifically at linear correlations.

Here's why the answer to the math stack exchange is "they might be correlated", while the corresponding answer here is "they aren't"; consider in the math stack exchange case that $X$ and $Z$ are independent variables that can take the values 0 and 1 with probability 0.5 each, and that $X=Y$, and that the addition is integer addition.  In this case, if $Y$ is 0, $X+Z$ can take on the values 0 and 1, while if $Y$ is 1, $X+Z$ can take on the values 1 and 2; hence the probability distribution of $Y$ and $X+Z$ are not independent.

This corner case can't happen with one time pad.


if a hash function has no known preimage attacks, does that mean there are no known attacks against using it in signatures? Suppose a hash function like SHA-1 has known collision attacks (including chosen-prefix collision attacks) but no known preimage attacks.
Does that mean there are no known attacks against using it in a signature scheme, under these assumptions:

I'm signing data by taking the SHA-1 hash and then using a public-key signing scheme to sign the hash (and assume the public-key signing scheme is not broken)
I salt the data before taking the hash, and then sign the salt along with the hash (so if the attacker tries a "chosen-prefix collision attack", where they have a 'good' document and an 'evil' document with the same SHA-1 hash value and they want me to sign the 'good' document, the salt will prevent that attack from working)

I don't understand why that would be considered unsafe if the only known attacks against SHA-1 are collision attacks.
Is it just because of the general inference that if a hash is vulnerable to collision attacks, it is more likely to be vulnerable to preimage attacks, even if none are known currently?

Your idea of salting the signature to prevent the collision attack doesn't work, because your salted signing operation is a deterministic mathematical function, and the random choice of salt is only made at signature time, not at verification. Your signature algorithm has to be something like this. For a document $x$ and hash function $H$:

Hash the document: $h = H(x)$;
Generate a random salt $s$;
Apply the signature primitive function: $r = \mathrm{Sign}_{sk}^s(h)$;
Return $(s, r)$—the pair of the salt you picked and the signature primitive's result.  Because verifiers are going to need the value of $s$ you picked on this occasion to verify the signature.

For a document $y$ and a putative signature $(s, r)$, the verification algorithm has to work something like this:

Hash the document: $h = H(y)$;
Apply the verification primitive function: $\mathrm{Verify}_{pk}^s(r)$.

No random choices involved in verification. So if I can craft a pair of colliding documents and convince you to sign the "good" one for me, I can take the signature you produced and give it to somebody along with the "bad" document, and when they try to verify it it'll check out.


WOTS+: Why does it XOR before running data through the hash function? I'm implementing WOTS+ in a new language and I can't seem to wrap my head around the fact that WOTS+ XOR's their input with its mask right before hashing it.

I tried to look for any reasoning but so far haven't found any. In my mind I also can't seem to come up with the logic that would make this more secure. For instance, this source says:

  In each iteration, PRF is used to
     generate a key for F and a bitmask that is XORed to the intermediate
     result before it is processed by F.

But it doesn't explain why this XOR is so important. Why is there a random mask needed in the first place? As far as I can understand, you are supposed to disclose the mask along with the signature and the message in order to get to the final public key that signed it.

It allows the security of the construction to be reduced to second-preimage-resistance, rather than collision-resistance. This is a significant distinction, since brute force against collision-resistance is $2^{n/2}$ while brute force against second-preimage-resistance is $2^n$. In short, this XOR trick allows signatures/keys in the scheme to be half as long for the same level of security.

It is hard to express why the XOR trick helps the proof, without getting into the weeds. But here is a sketch of how to prove security of a Winternitz-like scheme.

The security reduction $\mathcal{S}$ plays the role of an adversary trying to break second-preimage resistance. It has to provide public keys and signatures to an adversary $\mathcal{A}$ trying to break unforgeability. In the event that $\mathcal{A}$ produces a signature forgery, $\mathcal{S}$ should break second-preimage resistance.

In plain Winternitz, we imagine a hash chain starting at $x_0$ and with $x_i = f(x_{i-1})$. The public key is $x_n$. The reduction $\mathcal{S}$ will guess an index $i^*$ such that $\mathcal{A}$ will ask for a signature value later than $i^*$ in the chain, but will generate a forgery consisting of a value at or before $i^*$ in the chain. If the guess is correct, then we want $\mathcal{S}$ to break second-preimage-resistance of $f$ somehow.

$\mathcal{S}$ is itself trying to break second-preimage-resistance. It will request a first-preimage $a$ and try to find a second preimage with $a' \ne a$ and $f(a) = f(a')$. It needs to incorporate $a$ into the hash chain somehow --- ideally, set $x_{i^*} = a$, so that if the adversary computes a preimage of $x_{i^*+1}$, it will be a second-preimage of $a$.

But if $x_{i^*}=a$, then what are $x_0, \ldots, x_{i^*-1}$ such that $x_i = f(x_{i-1})$? The reduction $\mathcal{S}$ can't make a consistent chain. It receives $a$ externally and would need to compute a preimage of $a$.

However, if we augment the scheme in the style of W-OTS+, we have additional $r_i$ values and $x_i = f(x_{i-1} \oplus r_{i-1})$. These $r_i$ values allow the reduction to "patch things together."

The reduction $\mathcal{S}$ chooses $x_0$ and computes a forward chain until $x_{i^*}$, as usual. Then it receives $a$ externally, and chooses $r_{i^*}$ so that $r_{i^*} \oplus x_{i^*} = a$. This means that the input into the next $f$ is $a$. This means that to make a forgery, $\mathcal{A}$ would have to find a preimage to go with $a$. From this point, the rest of the chain is computed normally.

So, the extra XOR just gives the reduction extra flexibility to insert a "trap" into the hash chain --- ensuring that a particular $a$ is used as input to $f$ in the chain, even when the reduction algorithm $\mathcal{S}$ didn't itself choose $a$. And this is exactly what's needed to reduce the signature security to second-preimage resistance.


Is a composition of computational hardness problems still hard? It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard?
Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ where $n$ is a composite number of secret factorization, is it hard to get $x$?

This is essentially equivalent to factoring $n$.

From the composition you have given it is obvious that this is at most as hard as the easier of the two instances of the hard problems. So let's look at both of them.

Computing square roots over composite rings. This one is known to be equivalent to factoring the ring modulus.

Computing discrete logarithms over composite rings. This one is more intriguing. It is known that if you can compute prime-based discrete logarithm (for all the prime factors) and factor, then you can compute the discrete logarithm over the composite ring. It is also known that if you can compute the discrete logarithm over composite rings, then you can factor the modulus.

If you wanted the composition to be more like "you need to break both instances", then you should formulate it as, "given $(g,g^y,x^2)$ with $x,y\in\mathbb Z_n$ with $n$ having a secret semi-prime factorization, find $(x,y)$".


How are all necessary parameters shared between signer and verifier in the ED25519 signature scheme? I want to use the ED25519 signature scheme in my application which requires frequent sharing of secret data between two entities in the public domain.

I know that the Schnorr signature scheme has a key authentication center (KAC) which decides and shares common parameters to be used by signer and verifier. The KAC also signs the public keys of everyone with its own private key. And then the signer signs the message and sends his public key along with the signature to the verifier [From Schnorr's paper 1991].

But is there any KAC in ED25519? And what are the parameters shared in ED25519 by the KAC?

Ed25519 is well-defined and requires you to use SHA-512 as internal hash function along with the twisted Edwards version of Curve25519, hence there's no need for a KAC when it comes to questions about the parameters. As for the integrity of the public key, there's not yet a standard for Ed25519 based certificates so there would be a custom solution needed for a given application.


How to use HMAC for authenticating multiple messages The standard HMAC function, $H(K, m)$, authenticates a single message $m$.

Instead, I'd like to authenticate 2 messages, like this: $$H'(K, m_1, m_2)$$

The simplest solution, $H(K, m_1||m_2)$, confuses e.g. "ab"+"cd" or "abc"+"d" as messages.

Would this be secure instead: $H(H(K, m_1), m_2)$?

If the hashing function $H$ is secure, then $H(H(K, m_1), m_2)$ is secure. But at the cost of applying $H$ twice.


Loss of data due to encryption Could any kind of encryption method (AES, etc.) lead to data loss like in lossy compression? I'm interested if data (lossy compressed, lossless compressed, uncompressed) that is encrypted and decrypted will always come back in the same state as before the encryption process, no matter what encryption method is used.

Regards,
Neil

Removing some verbosity:

  I'm interested if data that is encrypted and decrypted will always come back in the same state as before the encryption process.

Yes, it's actually one of the first things you learn in Crypto 101: if $e$ is the encryption function of a cryptosystem and $d$ is its decryption function, then $d(e(m)) = m$ for all valid messages $m$. Any system which does not satisfy this property cannot really be called a cryptosystem.


Shannon confusion and diffusion concept I read the document(not the whole document) from Shannon where he speaks about the concepts of confusion and diffusion. I read in many places(not in the document but around the internet) that confusion is enforced using substitution. Diffusion is enforced using permutation/transposition. Ciphers must use both of them because either confusion or diffusion alone are not enough. I read that a substitution cipher can apply by itself confusion(only). Permutation/Transposition applies by itself diffusion(only). It's precisely the last case that bothers me: Can a permutation/transposition cipher by itself apply diffusion?

Shannon explains diffusion as a property that spreads statistic properties of text all over the text preventing statistic analysis. It's frequently translated to: an alteration to a plaintext symbol affects many cipher text symbols. Assuming permutation of bits or characters, how can diffusion be achieved by simple permutation? I mean, if you permute bits, there will be no other bits affected.
But if you consider a symbol a character and you permute bits, a change in a character will affect many other characters. It's a question of what is a symbol.

I also read versions of this diffusion concept where the point was just changing bits order just to avoid pattern analysis of the text. But, where is the avalanche effect in simple permutation?

So, what is the correct definition and the implications of diffusion?

I hope you understand what is troubling me.

Thank you once more

I think that you missed a pivotal point in the concept, which is the small blocks that are used to compose a secure PRF (or PRP), i.e. when you permute one bit, you actually change the value of the small block of that bit, i.e. the whole small-block is effected and thus prepared to be confused in the next round, this way you will reach a confusion of the entire big-block very fast.

I attach a good explanation of the concept as described in Lindell-Katz Book

  In addition to his work on perfect secrecy, Shannon also introduced a
  basic paradigm for constructing concise,random-looking permutations.
  The basic idea is to construct a random looking permutation $F$ with a
  large block length from many smaller random (or random-looking)
  permutations $\{f_i\}$ with small block length. Let us see how this
  works on the most basic level. Say we want $F$ to have a block length
  of $128$ bits. We can define $F$ as follows: the key $k$ for $F$ will
  specify $16$ permutations $f_1,\ldots, f_{16}$ that each have an $8$-bit
  ($1$-byte) block length. Given an input $x\in\{0, 1\}^{128}$, we parse
  it as $16$ bytes $x_1,\ldots,x_{16}$ and then set (equation 6.2)
  $F_k(x)=f_1(x)||\ldots||f_{16}(x_{16})$. These round functions
  $\{f_i\}$ are said to introduce confusion into $F$. It should be
  immediately clear, however, that F as defined above will not be
  pseudorandom. Specifically, if $x$ and $x'$ differ only in their first
  bit then $F_k(x)$ and $F_k(x')$ will differ only in their first byte
  (regardless of the key k). In contrast, if $F$ were a truly random
  permutation then changing the first bit of the input would be expected
  to affect all bytes of the output. For this reason, a diffusion step
  is introduced whereby the bits of the output are permuted, or “mixed,”
  using a mixing permutation. This has the effect of spreading a local
  change (e.g., a change in the first byte) throughout the entire block.
  The confusion/diffusion steps—together called a round —are repeated
  multiple times. This helps ensure that changing a single bit of the
  input will affect all the bits of the output.

  As an example, a two-round block cipher following this approach would
  operate as follows. First, confusion is introduced by computing the
  intermediate result $f_1(x_1)||\ldots||f_{16}(x_{16})$ as in Equation
  (6.2). The bits of the result are then “shuffled,” or re-ordered, to
  give $x'$. Then $f'_1(x'_1)||\ldots||f'_{16}(x'_{16})$ is computed
  (where $x'= x'_1,\ldots,x'_{16}$), using possibly different functions
  $f'_i$, and the bits of the result are permuted to give output $x''$.
  The $\{f_i\},\{f'_i\}$, and the mixing permutation(s) could be random
  and dependent on the key, as we have described above. In practice,
  however, they are specially designed and fixed, and the key is
  incorporated in a different way


Unable to reproduce correct signature data "Skatteetaten" is the Norwegian tax authority.

We're currently trying to implement signing of messages for digital cash registry systems and i'm not able to reproduce the desired signed data.

Went back and forth with different types of padding and hashing algorithms, still unable to reproduce the desired return data.

I'm using their validation tool hosted here on github. Trying to get a private key using RSA 1024 to work (Form in Validator.html).

Example private key:

-----BEGIN RSA PRIVATE KEY-----
MIICXwIBAAKBgQDag84L+pT6OlFZ8kav08ixPdugo6bsqOICJrl8TzGY87Iek9K1
dgbz2sr7r0OBl2/ndz0CoxiyKoiLc5YY6wy5Qg1qNRCc4C71r2A7N+vjhfkSSoS7
RQekuhKSMJ1Wp8RfXB/AccWPdqb0Mm1TjklSizptJAANppC12fijFVTocQIDAQAB
AoGBAMSsIQXzEaduWc4lG64hZd7xF/4rjZAwKMta41OZS8CohkazMdEVXAibglqp
Uo8PKC8iyQzYkt+5HJC3Bf+DfzyMMty5NPJVpNK1fr0ftz1TfAK7A0I5PWOq9DPL
pjNmz8DIGCfoMOsg1plfh2oprqK36shpWzG1jzXizui4u+aBAkEA/A6M8fM01L5r
xeGtppKEY8EtaSImnBc09kONP1vPqexNUA8cORqZn3J1GKhv90zk79IWdTrzPN4C
ZTHGpGR/eQJBAN3u7HyT/HqvvIhZksqKS+DTbjYaKGr3KxiAEAKU0PeQOBD5TQds
JVstZ2vGSbAsCU6VNEh8eQfTpxzy59S2mrkCQQCM8P3zFNGH3GqbHdRh/i+1MAHa
ddQtF/Tvd1p2ATqfg5i/mZNogu0/8Vp0zUq+d+rUBx+zsaDteh7QwwKWTfPRAkEA
x01W5pFnPS4wWypFnsoPVjnJUaCwB08sTnZC6m6GMqw7DVM0j6PY8EaYB7ssVZ9W
RFHNgAL4FcVG38Jr2ySZUQJBAOPa7ScbGi7XTiV3TStW2rhmd9CyKnOeSdjIejGm
R4xrannBqg+ikWXuW0cnuGk2a2a/ymHXq1pSCTFAa2VeryA=
-----END RSA PRIVATE KEY-----

Example public key:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDag84L+pT6OlFZ8kav08ixPdug
o6bsqOICJrl8TzGY87Iek9K1dgbz2sr7r0OBl2/ndz0CoxiyKoiLc5YY6wy5Qg1q
NRCc4C71r2A7N+vjhfkSSoS7RQekuhKSMJ1Wp8RfXB/AccWPdqb0Mm1TjklSizpt
JAANppC12fijFVTocQIDAQAB
-----END PUBLIC KEY-----

When using these keys with the signing data:

0;2014-01-24;23:59:59;123456789;1250.00;1000.00

Performing signing with sha1WithRSAEncryption i get the signed data:

gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=

Which is base64 of the signature.

I've tried various PHP-crypto libraries and the openssl commandline tool to reproduce this signature and i can't just get the desired output.

If their validation library is not broken i must be missing something and all the possible combinations i've tried has not yielded the correct result...

Help would be appreciated to say the least.

Obcrypto: note RSA-1024, although not actually broken, is no longer considered to provide an adequate safety margin and is prohibited or deprecated in most applications. For example CABforum began phasing it out in 2014, and Chrome and Firefox warned for it.

$ printf '0;2014-01-24;23:59:59;123456789;1250.00;1000.00' \
> |openssl sha1 -sign cry64393.key |openssl base64 -A; echo
gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=
$ # or
$ printf '0;2014-01-24;23:59:59;123456789;1250.00;1000.00' |openssl sha1 -binary \
> |openssl pkeyutl -sign -inkey cry64393.key -pkeyopt digest:sha1 |openssl base64 -A; echo
gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=

Both rsautl -sign and pkeyutl -sign with RSA key default to SSA-PKCS1-v1_5, but if you want you can specify -pkcs or -pkeyopt rsa_padding_mode:pkcs1 respectively. openssl sha1 is an abbreviation for openssl dgst -sha1 and openssl base64 for openssl enc -a.

(I can try for PHP also if you need it but that will take longer to set up.)

ADDED: I should have noted this only works because RSASSA-PKCS1-v1_5 is deterministic, which is unusual. Most other public-key signature schemes, and essentially all public-key encryption schemes (and symmetric encryption schemes also), when executed multiple times on the same data (and key) produce results which are all different but valid, so it is futile to try to reproduce or compare outputs.


Key Agreement between two nodes of a Wireless Sensor Network Can there be a way to form a shared secret key between two nodes of a Wireless Sensor Network who are more than one hop away, simply on the basis of their IDs?

Yes, using identity-based cryptography; in particular the Sakai-Ohgishi-Kasahara non-interactive key distribution protocol, generalized in "Provably secure non-interactive key distribution based on pairing".

The downside is that it requires a "Private Key Generator", a trusted party which is able to compute the private key of any node. The private keys also need to be securely deployed in each node.

Using the protocol, each node will have and ID. They simply need to exchange IDs and will be able to compute a shared key.


Recover elliptic curve order from ECDSA signatures I need the elliptic curve order to recover the private key from two signed messages with ECDSA.

What I have:

two signatures signed by the private-key I want to get
the messages that have been signed
the random $k$ used to sign both messages

So breaking the Cipher should go like that:

$k = (z - z')(s - s')^{-1} \bmod n$

$d = (s \times k - z)  r^{-1} \bmod n$

The Calculations are clear, but the elliptic curve order $n$ is missing.
Can I calculate $n$ somehow from the signatures like I can do for $r$ and $s$?  Or is there any other way to do this?

Actually, you can recover $n$ from ECDSA signatures (assuming that you can obtain several signatures with the same $k$ value, which means that the ECDSA signature implementation is broken); however it would require 3 such signatures (if you don't mind factoring a value circa $n^2$), or 4 such signatures (if you don't have that many resources conveniently at hand).

Each ECDSA signature has:

$$s_i = k^{-1}(h_i + rd) + m_i n$$

where:

$k^{-1}$ is the inverse of the (unknown) common $k$ value
$h_i$ is the known hash of the $i$th message signed
$rd$ is the common unknown product of the value $r$ (which we do know, and is constant if $k$ is constant), and the secret key $d$.
$n$ is the unknown curve order we're trying we're trying to recover
$m_i$ is the unknown value that is added as a part of the $\bmod n$ operation (it is selected to make sure $0 \le s_i < n$, however we don't care about that.

Now, if we compute $(H_3 - H_2)(s_1 - s_2) - (H_1 - H_2)(s_3 - s_2)$, you'll see that the $k^{-1}(H_i + rd)$ portions cancel out; leaving us with $m \cdot n$, with the size of $m$ approximately the same as $n$.  If we can factor $mn$, we can do so and this will immediately give us $n$ (and possibly a false hit).

If $mn$ is too large for us to factor conveniently, we can then take a fourth such signature, and compute $(H_4 - H_3)(s_2 - s_3) - (H_2 - H_3)(s_4 - s_3)$; this gives us $m' \cdot n$ (for an $m'$ likely unrelated to $m$); computing $\gcd( mn, m'n )$ immediately gives us $\gcd(m, m')n$; even if $\gcd(m, m')>1$, it is likely small, and so easy to remove.


Are there any formal tests to estimate encryption strength? So I'm trying to design/make my own encryption algorithm and I believe it to be ok. I'm not saying it's extra secure but I know it's not useless so, what I was wondering is if there are any specific tests I can carry out in order to try and get a better representation of how secure my algorithm is.
Here is some data from tests that I have carried out:

Repeated blocks of data are different from each other
1-bit change in password will completely change the result
1-bit change in input text completely changes the output
even if you encrypt the same file with the same password you will get a different output each time because each encryption gets a different random salt
when tested over a large number of files matching bytes in both encrypted and unencrypted file that matched in the same place was 0.3% random is about 0.34% other encryptions get about 0.28-0.29%

here I have tried to layout the mode of operation for my algorithm. I believe it to be closest related to a PCBC mode of operation but there are some differences in the way I have laid mine out

TLDR: There are no tests that prove that some algorithm have particular strength.
Statistical metrics can only prove that an algorithm is weak. If the metrics give "good" results, it does not mean anything.
Example: If your algorithm produces encrypted messages that are indistinguishable from a random stream of bytes, you can get "good" metric values. But if this algorithm uses effectively only the first 40 bits of the 128-bit password, it can be relatively easy brute-forced.
Brute-forcing as iterative trying of all possible values is not used in serious cases, because it may require the computational power of the whole planet and even 1 000 000 000 years may be insufficient to try all possible password candidates.
Instead, first the analysis of the encryption algorithm should be done to reduce the amount of work needed for decrypt. For instance, if some algorithm uses 128-bit passwords, a straight forward brute-forcing may need 2^128 "units of work", which means that it is practically impossible to find a password. But if somebody finds a way (an algorithm, an "attack") to exclude many passwords or in some other way to reduce the number of "units of work" from 2^128 to only 2^40, then this will require little resources and it can be successfully brute-forced.
Finding ways to reduce the amount for work needed for brute-forcing is a very complex activity. It cannot be formalized fully. This is the reason why we need cryptographers.
What can you do? Such question was already answered many times on Crypto SE: Pay a professional cryptographer who will analyze your algorithm. If there are some trivial weaknesses, they will be found. But even if not found, it does not mean there are no any weaknesses.


Should DES be avoided when developing new systems? According to wikipedia…

  DES is now considered to be insecure for many applications

However, since it can be broken relatively easy, should it not just be avoided for all applications?

Yes. DES is no longer considered an approved algorithm by NIST, and breaking a 56-bit key can be done quickly - in 1998 the EFF DES Cracker managed to break a DES key in 56 hours. The average time it required to break any DES key was 4½ days. You could use triple DES instead, which is still considered secure, but it's very slow (in software, even single DES is slower than AES), and a time-memory tradeoff described by Martin Hellman in 1980 shows how to break 3DES with a 168 bit key in $2^{112}$ time. In addition the 64 bit block size is a major practical problem if using 3DES in some modes, as described by Thomas in his answer.


zero knowledge proof for complete new user authentication Consider an environment, an user A who is completely new to the environment is entering. An user B who is member of the environment need to verify A as genuine not liar.

No information about user A is known to B.

Is it possible using the zero knowledge proof.

No, you can not.

You assume:

$B$ does not know anything about $A$.
You need to know if $A$ is actually called Alice.

Well, that does not work. There is no possible proof that $A$ is actually called Alice. That is unless you verify some other credentials, e.g. an ID card. But trust can not be generated out of nothing. That is simply impossible.

For example, if there is no way to verify a persons name, then no one in the world can decide if he is actually talking to the real Alice or to Eve who is just calling herself Alice.

The question has nothing to do with zero knowledge - that is just impossible in general.


How to improve long-term duration of standard checksum for authenticity purposes? Official CMS's of Government gazettes (in the third world), need to publish the checksum of each article and each cited external documentin (eg. full-text contracts) in a permanent support medium like paper, CD, DVD, etc. And, this is valid as legal proof for decades...

But the checksum is not valid for decades, and the CPU-cost to compute a checksum in this context is not the first problem... So, the question is

  how to improve standard checksums, with minimal impact on the existing workflow?

Examples: (so alternative question is "what is the best?" or "why not?")

use the truncated form of "the best of the best" (ex. truncated SHA256 instead SHA1).
use two checksums instead of only "the best of the best" (ex. SHA1+MD5).
use two checksums, the second after some "file conversion", such as gzip, imagemagick (eg. png2jpg), some pandoc (eg. pdf2text), that preserves main content.

CONTEXT AND EXPLANATIONS

The SHA1 is a cryptographic hash that has been  used as checksum with aims of integrity and authenticity... So, the context of the question is this tradition of use cryptographic checksums for authenticity comprovations, there are no alternatives for a tradition, please not insist :-)

Let's give the name "authenticity-checksum" to this tradition and the methodologies it uses.

The theme gained more appeal last week with the first practical attack, with the discovery of an algorithm that can build a PDF document with the same SHA1 of other distinct PDF... You can check by yourself in a Linux terminal:

  wget -c https://shattered.io/static/shattered-1.pdf
  wget -c https://shattered.io/static/shattered-2.pdf
  # open each file with your PDF-viewer, see how much distinct they are.

  sha1sum shattered-1.pdf shattered-2.pdf
     # 38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
     # ...
  # look at your terminal! the same SHA1 for both files!

The SHA1 was published as a standard by NIST in 1995, gaining popularity and intensive in the 2000s. The first real and published attack was last week, 2017 (when standard was 22 years old). The first published "attack in theory" demonstration was in 2005, so 10 years after launch.

MD5, its precedent, published as RFC in 1992,  with theoretical demonstration in 2008 and real attack in 2012.. It has had a similar timeline in its life-cycle.

We can use the standard's timilines as good time-scale reference, decades, and the historic facts (and Moore's law) as clue that SHA256 will survive less than a decade.

... So, about the use of authenticity-checksum in important digital repositories and digital preservation with horizon of decades context.

Imagine a CD-ROM with a big list of file-names and its checksums, a CD recorded in the year 2004, when we still believed in the durability of SHA1. For this "Use Case in the past", what the best practices, what can we suggest to improve?

(is impossible to test hypothesis with the new standards, as SHA256, but we can in an imaginary use cases, testing the old standards, truncated hashes, and extrapolating results)

In this case, a simple change will improve robustness: include hashes produced by multiple functions. (This can be counterproductive if the hashed data is not fully public, because one hash being inverted would reveal the data even if the other hashes had resisted. But here the data is public so there's no loss of security in adding extra hashes.)

So for example, today, you should include (at least) both a SHA-256 (SHA-2) and a SHA3-256 (SHA-3) hash. (Or other sizes if you prefer, but today there's no strong reason.) One of the reasons why SHA-3 was chosen to be what it was is that it uses rather different techniques (a sponge construction, whereas MD5, SHA-1 and SHA-2 all used a Merkle-Damgård construction), so it's very unlikely that both will be broken at the same time.

You can find recommended hash lengths for a given duration of protection according to various authorities on keylength.com. Most are satisfied with a 256-bit hash for as long as they're willing to give recommendations for. My personal inclination would be to make an effective 512-bit hash by concatenation SHA-256 and SHA3-256.

The primary threat against your system is second-preimage resistance (not being able to tamper with a legal document after it was archived), but collision resistance is also a concern: someone could submit a document (e.g. a contract) with a prepared “trap” that allows them to craft a collision after the contract has been signed (e.g. “you owe us \$1 if you have a blue contract or \$1,000,000 if you have a red contract” — uh-oh). Hash functions seem to be more vulnerable to collision attacks, i.e. finding $M$ and $M'$ such that $H(M) = H(M')$, than to second-preimage attacks, i.e. finding $M'$ such that $H(M) = H(M')$. For example, collisions are known for MD5 and SHA-1, but nobody knows how to find a collision for a given message as opposed to a specially-crafted message (at least nobody who's said so publicly). Here are two things you can do to mitigate collision attacks:

The known techniques to generate collisions require taking the hash function through “near-collision” states which are extremely unlikely to occur naturally. So you can detect a probable collision attack when hashing a single message! This idea is due to Marc Stevens and an implementation for SHA-1 is available.
Crafting collisions for MD5 or SHA-1 requires a bit of “garbage” in the middle; that garbage can be hidden in some insignificant part of a complex format such as PDF, or in comments in a computer program, but current techniques don't allow crafting a collision between plain text English documents even with MD5. If you hash plain text¹ rather than (or in addition to) complex formats such as PDF, collision attacks will be easy to detect after the fact, unless our knowledge of how to craft collision makes significant leaps. If your input is not plain text, this does require a deterministic process to generate the plain text.

In the longer term, the only viable solution is algorithm agility: periodically re-hash the documents with newer hash functions. This can be combined with the need to verify and update physical supports. Paper can last centuries or more with proper care, but a magnetic tape or CD is unlikely to last so long; data needs to be transferred to new media every so often. That point in time is a good time to verify originals and re-hash them using up-to-date algorithm. Note that this requires access to the originals, which isn't the case for a plain medium-to-medium transfer; you might not want to do it on every physical transfer, but you should have a procedure for it.

Note that a hash only guarantees integrity, not authenticity. There's only one message with a given hash (as long as the hash function isn't broken), but anyone can produce this hash. Authenticity requires a signature: having a valid signature shows that somone holding the corresponding private key saw the document and was willing to endorse it (subject to the conditions under which the signer is willing to sign documents).

¹  Here, “plain text” means a pure text format (e.g. stragiht ASCII or Unicode), what MIME would classify as text/plain, not cryptographic plaintext as opposed to ciphertext.


Does the relationship between plaintext and ciphertext moduli affect the security of BGV/BV SwHE? The SwHE schemes due to Brakerski and Vaikuntanathan (BV) and Brakerski-Gentry-Vaikuntanathan (BGV) have common concept in which the message bit is put in the least significant bit of the ciphertext.
Let $t, q\in \mathbb{Z}$ be moduli that determine the plaintext and ciphertext space, respectively.
The BV and BGV scheme require $t$ and $q$ to be co-prime.

Let

$\mathbf{s} \in \mathbb{Z}_q^n $: a secret key sampled from a key distribution
$\mathbf{e} \in \mathbb{Z}_q $: an error sampled from an error distribution
$\mathbf{a} \in \mathbb{Z}_q^n $: a random vector sampled from $\mathbb{Z}_q^n$ uniformly at random.
$m \in \mathbb{Z}_t $: a message.

Then,
$$
(\mathbf{a}, b):=(\mathbf{a}, \langle \mathbf{a},\mathbf{s} \rangle + t\cdot e + m) \in \mathbb{Z}^n \times \mathbb{Z}
$$
is a symmetric encryption of $m$.
Decryption works by computing
$((b - \langle \mathbf{a}, \mathbf{s} \rangle) \mod q )\mod t$.

Is this plaintext and ciphertext space relationship ($t$ and $q$ are co-prime) needed for the security?
What happens if $q$ is divisible by $t$?
I understand that modulus switching does not work, so it affects the correctness at least.
What about the security?

This is necessary for security. Consider if $q$ was a multiple of $t$, so $q = v\cdot t$. Take your ciphertext $(a, \langle a, s \rangle + t\cdot e + m)$ and multiply through by $v$. You now have
$$(v\cdot a, \langle v\cdot a, s \rangle + v\cdot t\cdot e + v \cdot m) = (v\cdot a, \ \langle v \cdot a, s \rangle + v\cdot m) \mod q$$
Suppose you're playing the CPA game, so there are only two possible values for $m$, which you know, so just try subtracting $v\cdot m$ from the second element and solve the "learning without errors" problem using your favorite algorithm to solve a linear system of equations (Gaussian elimination will work for BV & BGV).

For a more general answer, if $t$ is a zero-divisor in the ring $\mathbb{Z}_q$, the above attack will work, since you can kill the error by multiplying through by a non-zero value. By mandating that $t$ and $q$ be coprime, the only way to kill the error is to multiply by a multiple of $q$, which is 0 in the ring $\mathbb{Z}_q$.


Does encryption of data/information take place in peer to peer networks like Gnutella, Bittorrent? Do peer to peer networks like Gnutella, Bittorrent have any encryption system to secure the users privacy or encrypt the file/data being shared? Elaborate please.

BitTorrent, when encryption is used (optional in most clients), uses the Diffie-Hellman protocol for key exchange and RC4 for confidentiality. It also drops the first 1kb of data from the RC4 output as part of the specification.

There is no authentication, not really enforceable anyway due to the nature of peer-to-peer sharing networks. Standard theory applies; man in the middle is possible, but a passive attacker, only able to observe traffic, cannot see the content of the messages being sent.

The idea is to stop people from figuring out specifically what data is being sent, but bandwidth analysis will clearly reveal the use of peer-to-peer technology. Other factors, such as popularity (peer count) and total bandwidth may help in identifying the specific files being downloaded.


RSA public key of dead cryptographers Two cryptographic schemes—RSA accumulators, and RSA-based Verifiable Delay Functions (VDFs) such as this one—require an RSA modulus to operate. These RSA constructions are secure if the trapdoor, namely the factorisation of the RSA modulus, is secret. In the context of a blockchain we do not want to trust anyone with the trapdoor.

The RSA public key of a dead (or presumed dead) cryptographer could be acceptable as a "trustless" RSA modulus. (Or at least, one of several moduli for an accumulator or a VDF built from multiple parallel sub-accumulators or sub-VDFs.) The idea is that the trapdoor, stored in the cryptographer's brain, disappears upon death. I tried to find an RSA key (e.g. from a PGP key) for Aaron Swartz and Satoshi Nakamoto, without success.

Are there famous dead cryptographers that have an RSA public key attached to their name?

What you're looking for is hard-to-factor numbers where no one knows the factorization.

One approach to do this is to use the larger numbers in the RSA Factoring Challenge.  These are composite numbers selected by RSA Laboratories, in an attempt to encourage research on factorization methods.  As such, they went to great lengths to make sure that no one knew the factorization (including destroying the PC that generated the factors afterwards).

While the smaller numbers on the list have been factored, the larger ones (including RSA2048) have not.

I believe that this would address the problem you are attempting to solve.


How does Blowfish avoid successful cryptanalysis? I have researched the Blowfish algorithm and am curious as to why there  exists no effective cryptanalysis for this algorithm as of yet. What basic principles or features allow Blowfish to achieve this?

The same way other ciphers, basically, only it does it better than some. From the Blowfish paper these were the relevant building blocks "demonstrated to produce strong ciphers" in previous designs:

"Large S-boxes. Larger S-boxes are more resistant to differential cryptanalysis."
"Key-dependent S-boxes. While fixed S-boxes must be designed to be resistant to differential and linear cryptanalysis, key-dependent S-boxes are much more resistant to these attacks."
"Combining operations from different algebraic groups." (Blowfish uses XOR and  addition modulo $2^{32}$.)
"Key-dependent permutations. The fixed initial and final permutations of DES have been long regarded as cryptographically worthless."

The basic structure is a Feistel network, which has also been shown to produce secure ciphers provided the round function is good.

Of course, it's not a perfect cipher. For one, its 64-bit block size puts some restrictions on how we can use it securely. Its key setup is rather slow. There's also a class of weak keys for up to 14/16 rounds, which is quite close even if it allows no attacks. Schneier himself has been quoted as recommending people move to e.g. Twofish instead.


How to understand RSA Proofs of correctness at Wikipedia From Wikipedia(https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Proofs_of_correctness):

$m^{ed}$ ≡ $m$ $\pmod{q}$
$m^{ed}$ ≡ $m$ $\pmod{p}$
 then $m^{ed}$ ≡ $m$ $\pmod{pq}$

Question:
if $m^{ed}$ ≡ $m$ $\pmod{q}$,then $q$|$m^{ed}$- $m$
if $m^{ed}$ ≡ $m$ $\pmod{p}$,then $p$|$m^{ed}$- $m$
that is to say, $m^{ed}$- $m$ is the common multiple of both $p$ and $q$

At this time, if there is $lcm(p,q)=pq$, then $m^{ed}$ ≡ $m$ $\pmod{pq}$.
However,  I am not sure $lcm(p,q)=pq$ holds true or not, so how can I prove $m^{ed}$ ≡ $m$ $\pmod{pq}$?

If $m^{ed} \equiv m \pmod{q}$, then $q\;|\;(m^{ed}-m)$;
if $m^{ed} \equiv m \pmod{p}$, then $p\;|\;(m^{ed}-m)$;
thus $m^{ed}-m$ is a multiple of both $p$ and $q$;
thus $m^{ed}-m$ is a multiple of $\operatorname{lcm}(p,q)$.

Because both $p$ and $q$ are distinct primes, $\operatorname{lcm}(p,q)=pq$ holds;
Thus, $m^{ed}-m$ is a multiple of $pq$.

So $(pq)\;|\;(m^{ed} - m)$ clearly holds.
Thus finally, $m^{ed} \equiv m \pmod{pq}$.


Use of cryptographic hash for computing previous block hashes in blockchains Why is the previous block hash computed using a cryptographic hash function instead of a regular hash function in Bitcoin and other blockchains?
What cryptographic hash properties (pre-image resistance, second pre-image resistance and collision resistance) are needed and why?

Collision resistance and pre-image resistance, both first and second, are important for Bitcoin. This answer may not apply to all blockchain instances.

Collision resistance is important for the property of distibuted consensus.

  In bitcoin mining, the inputs for the function are all of the most recent, not-yet-confirmed transactions (along with some additional inputs relating to the timestamp and a reference to the previous block).

Think about what would happen if there were more than one input that could hash to the same value.

Preimage resistance is important to the mining process, and by extension to the strength of the consensus which is mined into the blockchain.

Each bitcoin block contains a nonce. The job of miners is to find a nonce value such that the resulting hash of the block contains a certain number of leading zeros. The number of zeroes corresponds to the difficulty of mining the blockchain. Without pre-image resistance, and depending upon the difficulty of finding a pre-image, it could be possible for miners to find a nonce value with less difficulty than by exhaustively enumerating the nonce field. If it were very easy to mine the blockchain, in particular if one group had a significant advantage in doing so, then they could launch an attack in which they control the majority of the hashing power of the bitcoin network. .

Finally, second pre-image resistance is necessary for the same reason as collision resistance. If a second input could be found which matched one of the block hash values then there would be uncertainty about the canonical state of the blockchain.


Collision resistant hash functions Let (Gen1,H1) and (Gen2,H2) be two hash functions.  Define (Gen,H) so that Gen runs Gen1 and Gen2 to obtain keys s1 and s2, respectively. Then define Hs1,s2(x)=Hs1(x)||Hs2(x).

a) Prove that if at least one of (Gen1,H1) and (Gen2,H2) aris collision resisistant, then (Gen,H) is collision resistant.

b) Determine whether an analogous claim holds for second pre-image resistance and pre-image resistance, respectively. Prove your answer in each case.

Now assume H is any collision reistant hash function. Then is the composition H o H necessarily collision resistant?

Since it's your homework, I'll only hive you the direction and not a full formal proof:

a) if at least one of H1 and H2 are collision resistant then H is too. Because if H is not coll-resistant then it's possible to find x and x' s.t. H(x)=H(x') so H(x)=H1(x)||H2(x)=H1(x')||H2(x')=H(x') which means that H1(x)=H1(x') and H2(x)=H2(x') so we found a collision in both H1 and H2.

b) About preimage res, if H is not preimage-res then given y it is possible to find x such that H(x)=y. We know that y=y1||y2=H1(x)||H2(x), thus you can find the preimage of y in both H1 and H2 as before.

c) about the composition, it is clear that a composition is also coll-res. Assume that H(H(•)) is not coll-res then it immediately means that H(•) is not coll-rea, by contradiction to the fact that H is coll-res.


random oracle model vs standard model vs selective model Can someone clearly outline the main difference between each of the three security models:

random oracle model
standard model
selective model

This post What is the "Random Oracle Model" and why is it controversial? gives a very good description of the random oracle. According to what I have been reading, the standard model depends on some strong assumptions (for example DDH).

What I don't understand is how the selective model is different from both. And to what extent is it weak.

In the random oracle model, you assume the existence of random behaving function, which is at the control of the protocol designer-challenger- during the game played between the adversary and the challenger in case of game based definitions. Usually the challenger manipulates the random looking output at its will in order to 'inject' the challenge of a presumably difficult problem like DDH, CDH, etc. In the real world, the random oracle advocates conjecture that this can be instantiated with a collision resistant hash function and argue that if such function raises security problems then we just replace it but the model itself does not break. This is still questionable as researchers have manage to cancel security guarantees by exploiting the non-random-looking instantiation of such hash functions.
In the standard model, there is no assumption for the existence of such random looking function and the security of the scheme lies on the hardness of mathematical assumptions, usually at the cost of a less efficient protocol but without making any assumption about random functions.
Selective model cannot be compared with random oracle and standard model. It is like comparing apples with lemons. Selective model dictates the way an adversary is getting information from the challenger (paper). In the selective model the adversary somehow declares in advance the challenge is gonna get later in the protocol. That renders the model a bit weak. In contrast in the adaptive model this limitation does not exist.


Truncated 60 bit SHA1 collision detection? So, I have managed to get a 52 bit collision for a SHA1 but after three days of brute forcing, I am unable to get a 60 bit collision.

My question is simple, how should I approach this?

I am currently using a random hex code of about 15 bits and randomly alternating between these digits. I then get the 60bit SHA1 for this and then check if its in my array. If it is I display the matching SHA1 values and the hex strings which generated them.

Frustrating isn't the word at the moment so any guidance or help will be greatly received.

It seems I am now running out of memory before computing the end answer which is bizarre

Typical brute-force issue.

Here’s a hint: do NOT store results in arrays as that’s most probably what’s currently causing you to run out of memory. Look at the numbers: if we would assume no collisions, you’ld need your array (read: memory allocation) to hold up to $2^{60}$ elements to store all 60-bit results; and we’re not yet counting memory you need to run the OS, to run your code, and to store things like the random 15 bits hex codes you’re hashing.

Of course – due to the fact SHA1 collisions are known to exist – your array won’t grow that big, so you won’t need to worry that you might be needing a rough 144115 Terabytes of memory to store all “SHA1 truncated to 60-bit” results. Thinking about the resources available when using an average desktop computer, a project going for 60-bits of truncated SHA1 without running out of memory should be feasable. An SHA1 hash truncated to its first 60 bits, should take around and about 60 or 120 million iterations/hash-calculations before hitting a collision – depending on how lucky you are. Unless your computer is 10 years old or older,and unless you mess up your implementation, that number of elements should easily fit into memory.

One potential solution to your memory problem is to use random hex codes as you currently do, and to store things in a tree indexed by the first 60-bits of the hash. (In case of doubt, look for “Binary Indexed Trees”, also known as “Fenwick Tree”.) Yet, if that’s indeed the best way to do it somewhat depends on implementation details, available resources, and – last but not least – used programming language. As we handle coding-related questions as “off topic” here at Crypto.SE, I’ll refrain from diving into that.

Background Info: Exponential Growth Problem

I’m assuming you did some research before practically programming things up. If you did, remind yourself of the fact that the resources required for a brute-force attack grow exponentially with the data size (here: number of bits) you are brute-forcing. Among other sources, you can find this information in the Wikipedia article about Brute-Force attacks. Note that when we talk about the exponential growth of needed resources, we’re not only talking about raw computer memory – “time” is also one of the exponentially growing factors.

Here’s a graphic (from an SHA1 brute-force project) that puts things into perspective for you:

The fact that brute-force attacks cause you to quickly run out of several kinds of resources is the main reason why password-brute-forcing tools and utilities tend to prefer “dictionary attack” methods for longer passwords, and it’s one of the main reasons why cryptanalysts dive into cryptographic algorithms to find weaknesses and/or attack vectors that allow them to avoid having to bluntly brute-force things.

Long story short: Unless you’re a governmental agency with ample resources, or you’re merely attacking something small enough to fit your desktop computer, brute-force attacks can quickly become a rather futile effort.

Optimizing Collision Attacks

Lucky for you, SHA1 is considered “broken” and some attacks have been found which are more speedy than plain “brute-forcing collisions for (truncated and non-truncated) SHA1”. For details, you might want to check the papers mentioned in an answer to “SHA-1 collisions - what about practical attacks?”

For your convenience, here’s the relevant snippet:

  I'll assume … enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

  by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
  or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to

  $2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
  $2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
  $2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

Based on the information available in the papers mentioned above, you should be able to derive something more optimal compared to your current, non-optimized brute-force approach to find “truncated SHA1” collisions. After all, “time” is a pretty valuable resource.


How to Update Non-Membership Witness upon deletion in RSA Dynamic Universal Accumulator The Universal Accumulator paper mentions the following for updating non-membership witness upon member deletion.

Choose $r$ such that $a\hat x − rx ∈ Z$$2^l$

What is Z$2^l$ and how can we efficiently evaluate $r$?
I suppose we need to brute force search by guessing values of r, is there any room for optimization here? Perhaps by making an educated guess about the value of r.
Update:
Can it be that $a\hat x − rx$ can be construed as $a\hat x$ $mod x$? If yes, then we can find
$\hat a = a\hat x$ $modx$
And,
$r = (a\hat x - \hat a)/x$
Am I right in assuming this?

The updated Non-Membership Witness ($\hat a, \hat d$) upon deleting a member $\hat x$ can be calculated as follows:
$\hat a = a\hat x\mod x$
$r = (a\hat x - \hat a)/x$
$ \hat d = (d\hat c$ -r )$\mod n$
Hope this is useful to future developers trying to deconstruct these equations.


Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA For prime number generation, one can use a probabilistic prime number generation algorithm like the Miller–Rabin primality test that will yield a composite as a probable prime with probability $\frac{1}{4^r}$ for $r$ rounds. If we use $r=50$, this has probablity $2^{-100}$. This is enough to believe that it is prime due to the high probability, if the collective power of Bitcoin miners is not searching a candidate, we will not see one around.
What if we want to make sure that it is 100%? We can use the deterministic AKS primality test and its faster variants to see that it is prime or it was a pseudoprime for the Miller-Rabin. AKS primality test, however, is very slow, and that is why we use probabilistic methods.
Now, instead of AKS, we want a faster approach and use it in the RSA cryptosystem to encrypt and decrypt a message. If everything works we will assume it is prime (should we?)!
Take a well-known prime like Fermat or Mersenne primes call it $p$ and the pseudo-prime (a real one can be found if we use fewer rounds but assume that we found one with 50 rounds) and call it $\bar{p}$. Construct the RSA as usual with the exception that instead of choosing firstly $e$ then finding primes, choose a suitable $e$.

$n = p \cdot\bar{p}$
$\varphi{(n)} = (p-1)(\bar{p}-1)$, (actually we can use $\lambda{(n)}$)
find $e$ such that $\gcd(e, \varphi(n)) = 1$
find $d \equiv e^{-1} \pmod{\varphi(n)}$

and the rest is textbook RSA encryption and decryption.
Question(s):

We expect that the encryption will fail since the incorrect $\varphi(n)$. Is there a pseudo message that correctly encrypts and decrypts under this pseudoprime $\bar{p}$?

If, so, how we can find one?
If, so, what is the probability of the pseudo messages?

We expect that the encryption will fail since the incorrect $\varphi(n)$.

Not always; for example, consider the case $p=31$ (a Mersenne prime) and $\bar{p} = 561 = 3 \times 11 \times 17$.  We'll set $e = 13$ and $d = e^{-1} \bmod 30 \times 560 = 3877$.
Then, if we pick a random message $m=2$, then $2^e \bmod n = 8192$, and $8192^{3877} \bmod n = 2$; encryption and decryption works just fine.  Actually, it turns out that any value $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
Lets try it again with another random example; this time we'll pick a Fermat prime $p=17$ and an arbitrary $\bar{p} = 91 = 7 \times 13$, and so $n= 1547$.  This time, we'll use $\lambda(n) = (p-1)(\bar{p}-1) / \gcd( p-1, \bar{p}-1 )= 720$; we'll pick $e=7$ and so $d=e^{-1} \bmod \lambda(n) = 103$.  Again, if we pick a random message (we'll try $m=3$ this time, we have $3^e \bmod n = 640$ and $640^d \bmod n = 3$.  And, again, any $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
So, how did this work?  Did I just pick these examples at random?  Is this always true of Fermat and Mersenne primes?  Well, no, for this trick, I selected my $\hat{p}$ values carefully, and most everything else was arbitrary.
In the first case, I selected $\hat{p}$ to be a Carmichael number, that is, a composite number such that $\lambda(\hat{p})$ is a factor of $\hat{p}-1$.  It turns out that a Carmichael number acts just like a prime as far as RSA is concerned; any $p$ (relatively prime to $\hat{p}$ would make it work).
In the second case, I selected a $\hat{p}$ that wasn't a Carmichael number (561 happens to be the smallest), but instead it is something we may call a "semicarmichael number" (terminology I just made up, so don't bother googling it); it has the property that $\lambda(\hat{p})$ is a factor of $2(\hat{p}-1)$.  Now, these numbers won't always work within RSA, however it does work if either $p \equiv 1 \bmod 2^{k+1}$ (where $2^k$ is the largest power of 2 which is a divisor of $\hat{p}-1$), or alternatively you use the $\phi(n)$ relation of $e, d$ (rather than the $\lambda(n)$ relation - for primes and Carmichael numbers, it doesn't matter - for semicarmichael numbers, it does).
So, what does this stage magic trick relate to your question:

If, so, what is the probability of the pseudo messages?

Higher than you'd expect, if you did a number of rounds of Fermat or Miller-Rabin beforehand.  It turns out that Carmichael numbers will always fool Fermat (unless you happen to pick a generator that's not relatively prime to the Carmichael number), and semicarmichael numbers will fool Fermat half the time.  And, both these numbers have good probability of fooling Miller-Rabin (obviously $< 1/4$, however sometimes not much less).  Hence, while Carmichael and semicarmichael numbers are rare, if you have a composite number that fools several rounds of Fermat or MR, the probability you started with such a number is pretty good.


Why does rsyncrypto require a public key during decryption? I recently came across a project called rsyncrypto that sacrifices some security so that you can have rsync-friendly files. My understanding is that it works by generating a symmetric key for each file you're encrypting, and saving that symmetric key to a file. It then encrypts the file using that symmetric key, encrypts the symmetric key with a public key, and concatenates the encrypted symmetric key to the encrypted file. The purpose of this is so that each file can be encrypted with a different key, but even if you lose the symmetric key file, the data can be decrypted by using the private key (private key decrypts symmetric key in the file, symmetric key decrypts the file itself).

The project seems to require the use of the public key in addition to the symmetric key file for decryption, however, and I'm confused as to why this is. It seems like if you have the symmetric key in a file already (which you do, generated by the program), you could just decrypt the data and disregard the embedded copy of the same symmetric key. I know that this is a question better posed to the maintainer, but he seems to have disappeared years ago. Anyone familiar with the program (or even if you're not) that could explain to me why you might need the public key in addition to the symmetric key for decryption? The most likely explanation I can think of is that I'm missing something about how this program works, but all the reading I've done doesn't seem to have cleared anything up about this.

Disclaimer: Thusfar my google-fu has been strong and I have never needed to post a question on any forum before, so this is my first. Please be gentle. =)

For completeness / posterity / future inquisitors, this is the response I got when I asked on the mailing list. I have also included it below because links sometimes break.

  No, you're not missing anything. This requirement is not,
  algorithmically, necessary.

  When you're decrypting with the symmetric key available, rsyncrypto uses
  the public key in order to know how much of the file's header to skip.
  In other words, all it actually needs from your public key is how many
  bits it is. Since the first part of the file is the symmetric key,
  encrypted using the private key, the key's length is needed in order to
  know how much to skip.

  Of course, in retrospect, I could have stored that information inside
  the symmetric key file, and made the usage simpler. I'm hoping to, some
  day, get around to working on rsyncrypto again, and this will definitely
  go there.

  Unfortunately, rsyncrypto's current file format makes it impossible to
  encrypt using a stream algorithm. Since this is a kinda important
  change, the changes planned for rsyncrypto 2.0 are breaking changes. As
  that's the case, I will not do another breaking change (changing the
  format of the symmetric key file) for so little gain.

  If this restriction is a problem for the deployment type you are
  planning, you can simply generate some random public key for the
  decryption machine. So long as it is the same length as the original
  encryption key, everything should work fine.

  Shachar