Is there any research on the problem of making a number more memorable to humans? Authentication protocols often rely on humans dealing with large numbers correctly. For example, when a user logs into a remote machine using SSH for the first time, she is prompted to confirm that the fingerprint of the server is the expected fingerprint. The user can phone the owner of the server, and confirm that the sequence of 32 hex digits are the ones shown on her screen.

The process seems vulnerable to the shortcomings of human perception, memory and energy. In practise, users do not check the fingerprint, because it is too tiresome.

The fingerprint could be made more memorable. For example, it is conceivable that a sequence of 32 hex digits could be reversibly converted to a sequence of eight English words. This would work as long as all implementations share the exact same bidirectional mapping between a tuple of four hex digits and between an English word. (I'm not asking for a review of this example, I'm just trying to explain the problem by explaining a naive solution.)

Within the cryptographic community, what is this problem called? Has there been any research on it?

I look forward to seeing more research on ways of representing cryptographically significant numbers in ways that are easier for humans to memorize or use in other ways.

memorizing and typing

There are several ways to bidirectionally convert a series of completely random bits into a series of English words and back again.
(That series of English words is easier for a touch-typist to type in, easier for a human to memorize, easier for a human to visually compare two sequences, etc. than the same bits in the form of hex digits).

The most popular wordlists seem to be:

the Diceware wordlist of 7,776 unique words: any 64 bit number can be encoded into five words and back again.
The S/KEY one-time password system uses 2048 unique words: any 64 bit number can be encoded into 6 words and back again.
The mnemonicode system uses a dictionary of 1633 unique words: any 64 bit number can be encoded into 7 words and back again.
The PGP word list of 512 unique words: any 64 bit number can be encoded into 8 words and back again. (This system has an extra feature, not found in the other systems, that allows a repeated word to be immediately detected and the duplicated word dropped without error).

I find all of these systems much easier to use than raw hex digits.
And by definition (because they are all various ways of encoding a completely random 64 bit number) they are all just as secure as 64 bits represented as raw hex digits or as a series of ASCII characters that includes lowercase, digits, punctuation, etc.

The size of the dictionary is a tradeoff:
small dictionaries let you use common words that are much easier to remember how to spell, but force you to use more words to store a 64 bit number.
Larger dictionaries force you to use uncommon words that may be difficult to spell or to distinguish from each other, but allow you to use fewer words to store that same number.

Alas, all the research I've seen in designing such wordlists involves making the words as distinguishable as possible from each other when one human reads the series of words to another over a noisy audio link.

comparing

The "visual host key" is intended to make it easy for humans to compare two SSH fingerprints. (See
"ASCII Art Fingerprints"; also
"Easy to remember fingerprints for data?"  )
Compared to hex digits or English words, this "visual host key" seems to be easier for humans to visually compare two fingerprints.
Alas, compared to a series of English words, it seems to be more difficult for a human to memorize and type back in a key in this form.


Cryptanalysis of XOR cipher with repeated key phrase My assignment is to cryptanalyze cipher text that we know was encrypted with a stream cipher (bitwise XOR of plain text and key stream), and decrypt to plain text. We know the key stream is a repeated English phrase. I have tried a variety of methods without success. They include applying the Kasiski examination to determine the length of the key stream, and analyzing where in the cipher text 0's appear, because x ^ x = 0, and so it might be possible to perform frequency analysis and determine what x is in this case. However, I have not had much success with these methods. Any help or hints would be greatly appreciated.

The first thing you should do is estimate the key length.  While you may be able to do this using Kasiski examination, in this modern era of computers I very much recommend instead using the index of coindicence, which you can compute very easily, e.g. with this Python program:

import sys
msg = sys.stdin.read()   # read ciphertext from standard input

for step in range(1, 50):
    match = total = 0
    for i in range(len(msg)):
        for j in range(i + step, len(msg), step):
            total += 1
            if msg[i] == msg[j]: match += 1

    ioc = float(match) / float(total)

    # output the IoC as a percentage, and plot it as an ASCII bar chart
    print("%3d%7.2f%% %s" % (step, 100*ioc, "#" * int(0.5 + 500*ioc)))

(Actually, the ioc value this code computes is the raw ratio of matching pairs to all byte pairs a multiple of step bytes apart; unlike the Wikipedia definition I linked to above, it doesn't multiply it by the size of the alphabet.  For simply comparing IoC values between different key lengths, this difference doesn't matter.)

For a quick test, I encrypted your question text (length = 628 bytes) by XORing it with the repeated string This is the key. (length = 16 bytes), and then ran the code above on it, and got the following output:

  1   2.39% ############
  2   2.49% ############
  3   2.38% ############
  4   3.45% #################
  5   2.35% ############
  6   2.55% #############
  7   2.28% ###########
  8   4.77% ########################
  9   2.41% ############
 10   2.40% ############
 11   2.28% ###########
 12   3.52% ##################
 13   2.34% ############
 14   2.26% ###########
 15   2.32% ############
 16   7.30% #####################################
 17   2.51% #############
 18   2.58% #############
 19   2.22% ###########
 20   3.26% ################
 21   2.24% ###########
 22   2.22% ###########
 23   2.43% ############
 24   4.82% ########################
 25   2.05% ##########
 26   2.35% ############
 27   2.40% ############
 28   3.06% ###############
 29   2.20% ###########
 30   2.33% ############
 31   2.15% ###########
 32   7.21% ####################################
 33   2.17% ###########
 34   2.39% ############
 35   1.97% ##########
 36   3.58% ##################
 37   2.07% ##########
 38   2.25% ###########
 39   1.98% ##########
 40   4.44% ######################
 41   2.09% ##########
 42   2.26% ###########
 43   2.06% ##########
 44   3.19% ################
 45   2.41% ############
 46   2.16% ###########
 47   2.16% ###########
 48   7.38% #####################################
 49   2.13% ###########

Looking at the output, you can clearly see the peaks in the IoC at multiples of the key length (16 bytes), as well as lower peaks at multiples of 4 and 8 (which evenly divide the key length).

Now that you've determined the key length, you're basically left with the task of solving 16 (or however many characters your key has) single-byte XOR ciphers, one for each key byte.

There are several ways to do that; for example, you could simply split the ciphertext into 16 columns and apply standard frequency analysis to each column:

Try to decrypt each column with every possible byte.
Compute the number of times each byte appears in the result.
Select the key byte that yields a distribution most similar to natural English letter frequencies according to some statistical distance measure.

In fact, we can do better than that: since we know that each of the columns is sampled from the same plaintext, and thus presumably has approximately the same plaintext byte distribution, we can pick any two columns, run a frequency analysis on both, and output the byte that, when XORed with one of the columns, makes its byte frequency distribution most similar (by some measure such as the Battacharyya coefficient) to the other one.

This will not directly give us the key bytes, but it does give us a very good guess about their pairwise XOR, without requiring any prior knowledge of the underlying plaintext byte frequency.  Knowing the pairwise XORs of the key bytes, we can then reduce the problem to that of guessing any one of the actual key bytes, which is very easy.

Computing the most likely XOR between each pair of key bytes also gives us a nice built-in consistency check: the XOR values $x_{ij}$ should satisfy the consistency relation $x_{ik} = x_{ij} \oplus x_{jk}$ for all $i$, $j$, $k$; if they do not, that's a sign that (at least) one of the values must be wrong, and it might be worth trying one of the other likely values.

(I ran this test on the same example ciphertext as above, and it guessed all but one of the pairwise XORs between the key bytes correctly.  Spotting the single mistake was easy due to the failed consistency check.)

For the particular case where the key and/or the plaintext are (mostly) ASCII text, it may be quicker to exploit the bit structure of ASCII, and particularly the following facts:

Ordinary ASCII uses only 7 bits per character, so the eighth bit will always be zero in plain ASCII text.  (If there are any bytes in the ciphertext with the eighth bit set, it implies that either the plaintext and/or the key contains some non-ASCII bytes — possibly UTF-8 or one of the ISO Latin charsets.)
All ASCII letters have the seventh bit set, while spaces and numbers and (most) punctuation has it unset.
The sixth bit is set for lowercase letters and unset for uppercase letters.  The ASCII space character only has the sixth bit set, and so XORing a letter with a space merely flips the case of the letter!
All ASCII bytes with both the sixth and the seventh bit unset are unprintable control characters; the only ones likely to appear in normal text are the line feed (LF = 0xA), tab (0x9) and possibly the carriage return (CR = 0xD, normally always followed by a line feed).
Numbers have the seventh bit unset, and the fifth and sixth bit set.

In particular, this implies that:

If one of the ciphertext columns contains only null bytes and letters, and if most of the letters are uppercase, then it's fairly safe to guess that the corresponding key byte is a space (or possibly a punctuation mark).
Conversely, if a column contains mostly control characters and a few uppercase letters, with most of the letters being the same, then the corresponding plaintext byte is probably a lowercase letter (and probably the lowercase version of the most common uppercase letter in the column).
Finally, if a column contains mostly numbers and punctuation, with a few lowercase letters, then the corresponding plaintext byte is probably an uppercase letter (and probably the uppercase version of the most common lowercase letter in the column).

For example, I took the example ciphertext I got by encrypting your question with the 16-byte key This is the key. and split it into 16 separate files each containing one column.  Here are hex dumps of all these files:

Column 0:
0000000: 1974 7420 3720 203d 2726 2c3f 2674 203b  .tt 7  ='&,?&t ;
0000010: 2174 3335 313c 313a 3735 2c3b 2739 2d3a  !t351<1:75,;'9-:
0000020: 2031 3523 303c 2631                       15#0<&1
Column 1:
0000000: 111c 0b48 1a1a 1f06 1c11 1c0d 0d18 1a0e  ...H............
0000010: 1c01 4805 1a48 090f 0118 4848 1b48 1b0d  ..H..H....HH.H..
0000020: 001a 0c01 1b01 0d0c                      ........
Column 2:
0000000: 4906 001e 100c 0049 1b19 4710 1901 0049  I......I..G....I
0000010: 4907 1d00 0406 0449 1919 3700 000f 0049  I......I..7....I
0000020: 0045 491d 4707 0847                      .EI.G..G
Column 3:
0000000: 1253 0316 0312 0007 1607 5353 1601 161e  .S........SS....
0000010: 0010 1b1d 1a15 5f04 1b16 5307 1101 0004  ......_...S.....
0000020: 0053 1e1b 5307 0779                      .S..S..y
Column 4:
0000000: 5343 4800 544d 4545 4100 7753 4141 4445  SCH.TMEEA.wSAADE
0000010: 554c 4541 4e00 0048 4541 5800 4c45 0048  ULEAN..HEAX.LE.H
0000020: 0069 5500 6153 4c                        .iU.aSL
Column 5:
0000000: 1a1b 0c02 0c49 4911 041d 0c1d 1d1a 491d  .....II.......I.
0000010: 0a1c 491d 0c1d 080c 1b1b 4904 0c18 0808  ..I.......I.....
0000020: 0a49 0a1d 0749 10                        .I...I.
Column 6:
0000000: 1a0a 011d 1710 2b07 5a1c 5301 1616 121b  ......+.Z.S.....
0000010: 1017 381a 531b 1d01 535f 4e1a 5306 1d07  ..8.S...S_N.S...
0000020: 121b 1b1b 0a04 53                        ......S
Column 7:
0000000: 4750 004f 0049 6f00 0c00 4b45 440e 004f  GP.O.Io...KED..O
0000010: 4545 414f 5445 4445 5400 0047 5445 4400  EEAOTEDET..GTED.
0000020: 5341 0045 004f 41                        SA.E.OA
Column 8:
0000000: 1a00 0003 0304 2615 5404 1a15 5454 0210  ......&.T...TT..
0000010: 0754 071a 1c54 5454 1116 441c 1b1a 540c  .T...TTT..D...T.
0000020: 1102 0707 1c01 04                        .......
Column 9:
0000000: 0509 0d48 0100 4806 0904 0705 2d21 091b  ...H..H.....-!..
0000010: 1b09 0148 0d03 0901 100d 441c 480b 0c48  ...H......D.H..H
0000020: 460d 1d0d 0d04 18                        F......
Column 10:
0000000: 000b 1d12 1100 0a01 0b04 1245 0b45 1745  ...........E.E.E
0000010: 4b15 1611 4500 0b0b 1106 4545 151c 000c  K...E.....EE....
0000020: 4545 0645 0901 17                        EE.E...
Column 11:
0000000: 4e41 5441 4852 4600 4449 0049 4748 4957  NATAHRF.DI.IGHIW
0000010: 0050 4b4f 4c59 4100 0041 4142 4500 5453  .PKOLYA..AABE.TS
0000020: 684e 434d 5000 45                        hNCMP.E
Column 12:
0000000: 1f07 4b18 4b4b 4b00 4b05 1f18 070a 0e02  ..K.KKK.K.......
0000010: 3f07 024b 0e4b 071f 5b1e 050e 190a 0e4b  ?..K.K..[......K
0000020: 0404 0e0e 4b09 08                        ....K..
Column 13:
0000000: 451c 1145 044d 1500 0145 0d45 0c13 1111  E..E.M...E.E....
0000010: 0d1c 4501 0b16 1c0d 4216 0145 030b 170c  ..E.....B..E....
0000020: 1211 1611 0a00 0c                        .......
Column 14:
0000000: 1003 111c 591b 1500 1c0d 1c18 0a1c 0011  ....Y...........
0000010: 1c10 1c1c 1e0d 031c 0a1c 5909 1618 1417  ..........Y.....
0000020: 1c59 0a11 0b59 18                        .Y...Y.
Column 15:
0000000: 5d4b 4f40 5d47 4f0e 4d4b 0e0e 460e 0e41  ]KO@]GO.MK..F..A
0000010: 5740 565a 5a5c 470e 0e0e 5d41 5c42 470e  W@VZZ\G...]A\BG.
0000020: 5846 0e41 0e49 5a                        XF.A.IZ

You can clearly see that the columns corresponding to spaces (or the period at the end) in the key look completely different from the ones that correspond to letters.  The first column, corresponding to the uppercase T, has mostly punctuation and a few lowercase ts mixed in, while the columns corresponding to lowercase key letters contain mostly control characters plus some uppercase versions of the key letter (where the plaintext byte happened to be a space).

There's also a subtle but noticeable difference between the columns where the key byte is a space and the last one where it's a period: while both contain a lot of uppercase letters and some control characters, the last column also contains a bunch of punctuation (particularly @, [, \, ], ^ and _, which have the same sixth and seventh bits as uppercase letters in ASCII), and the control characters are mostly 0x0E (. = 0x2E, XORed with space = 0x20) rather than nulls.


Correctness of Propagating Cipher Block Chaining mode of operation (PCBC) I was looking at the Wikipedia article about Block cipher mode of operation and I was wondering how can you from the encryption $C_i = E_K(P_i \oplus P_{i-1}\oplus C_{i-1})$ get the decryption $P_i = D_K(C_i) \oplus P_{i-1}\oplus C_{i-1}$ ?
Is there even a way to get decryption from encryption  (and vice versa)  or not?

How the PPCBC mode works
Propagating Cipher Block Chaining mode of operation (PCBC) works as with message indexes starts from 1;

For PCBC encryption we have;

$$C_i = E_K(P_i \oplus P_{i-1}\oplus C_{i-1})\text{ and } \color{red}{C_0 = P_0 \oplus IV}$$

For PCBC decryption ve have;

$$P_i = D_K(C_i) \oplus P_{i-1}\oplus C_{i-1}\text{ and } \color{red}{C_0 = P_0 \oplus IV}$$
given $C_1$ to decrypt $P_1$
$$P_1 = D_K(C_1) \oplus P_{0}\oplus C_{0} = P_1$$
given $C_2$ to decrypt $P_2$
$$P_2 = D_K(C_2) \oplus P_{1} \oplus C_{1}$$ Now we can solce since we know, $P_1$ and we have all $C_i$s.
and so on...
The red part was missing in your question.

The Correctness of the PCBC mode
An encryption scheme must satisfy the correctness requirement; for every key $k$ output by the key generation algorithm and for every message $m \in \mathcal{M}$ ($\mathcal{M}$ is the message space), the following must hold;
$$ D_k(E_k(m)) = m$$

To see that PCBC has the correctness; take
$$C_i = E_K(P_i \oplus P_{i-1}\oplus C_{i-1})$$ take decryption on the both sides
$$D_K(C_i)= \color{red}{D_K}(\color{red}{E_K}(P_i \oplus P_{i-1}\oplus C_{i-1}))$$ cancel Enc with Dec.
$$D_K(C_i)= P_i \oplus P_{i-1}\oplus C_{i-1}$$
Therefore:
$$P_i = D_K(C_i)  \oplus P_{i-1}\oplus C_{i-1}$$
Since we know, all $C_{i}$s, and previously decrypted $P_{i-1}$.
If it is the first case $(i=1)$, then we already know $\color{red}{C_0 = P_0 \oplus IV}$


RSA by hand - did I do something wrong? (c = m on encryption) to understand RSA better I am doing a little calculation by hand, this is what I got:

Choosing:

$p = 3\\
q = 5\\
n = 15\\
\varphi(p\cdot q) = 2 \cdot 4 = 8\\
e > \varphi(n) \implies e = 13\\
e \cdot d = 1 \pmod 8\\
13 \cdot d = 1 \pmod 8\\
(13 \cdot 5) \mod 8 = 1$

So there has to be $m \le n$ and I choose $m = 7$

Encryption:

$c = m^e \mod n\\
c = 7^{13} \mod 15\\
c = 7$

And if I decrypt it's nice coming back to 7. But it looks a bit weird to me having $m = c$ but I don't find what I should be doing wrong.. ?

In fact, your calculating is right. The problem is:

At first, $e=13=5\pmod 8$.

Next, $d=5=e$ since $d\cdot e=1\pmod 8$. This means that the decryption key is identical to the encryption key. You should avoid this of course.

Third, $7^{13}=7^5=(7^2)\cdot(7^2)\cdot 7\pmod{15}=(4\cdot 4)\cdot 7\pmod{15}=7\pmod{15}$. This is why your decryption outputs the same as the input. If you try another message, you may find that the cihertext is different to the plaintext.


What is the difference between an anonymous-encryption scheme and an authenticated-encryption scheme? I was going through Indy-SDK when these two schemes were referenced. I want to know the precise differences between the two.

Indy-SDK links for reference to:

authenticated-encryption scheme

anonymous-encryption scheme

authenticated-encryption scheme

This one takes the sender's public key $g^a$ and the recipients public key $g^b$ and using the currently available secret key ($a$ or $b$) computes $g^{ab}$ and derives a symmetric encryption key from that. This is called a static-static Diffie-Hellman key exchange. It provides authentication for the sender because only the sender knows the correct (static) $a$ to come up with the same shared secret as the receiver.

  anonymous-encryption scheme

They work the same as the authenticated one, but this time the sender picks a new $a$ for each message and includes $g^a$ as part of the ciphertext. This way anybody could have picked this $a$ - including an adversary that intercepted the ciphertext, dropped it and computed a new one. This uses a so-called static-ephemeral Diffie-Hellman key exchange and the security guarantees are not unlike those of an unsigned, encrypted PGP message.


Construction of S-box in AES In my introductory cryptography class. There is a line describe the construction of S-box in AES
 "The S-box of AES is constructed by combining a function $h(x)=x^{254}$ defined on $GF(256)$  with an invertible affine transformation."
However, when I look into the Advanced Encryption Standard (AES) document , I can not find where the $h(x)=x^{254}$ is used. I understand that S-box is constructed by $a_{i,j}\to a_{i,j}^{-1}(mod\,x^8+x^4+x^3+x+1)$ and subsequent affine transformation. Does $h(x)=x^{254}=x^{-1}$ is used during the inverse proccess?

In the field $GF(2^8)$, $x^{254} = x^{-1}$ (except for $x=0$, as $0^{-1}$ doesn't exist; for AES, that's treated as 0), and so it's two ways of describing the same thing.

When we talk about AES, we typically use the $x^{-1}$ nomenclature; for whatever reason, your class decided to go with the $x^{254}$ one.


Sorting over encrypted data with different symmetric keys I'm working on a security project. I need to perform a sorting on the lists of encrypted integers and strings. The encryption used is symmetric. The clients send the encrypted data in a list to the server (encrypted by different symmetric keys, each key is shared b/w a client and the server). On receiving the list, server may again encrypt it using another key shared between the server (such as authentication server) and the service provider's server. If service provider server wish to sort the encrypted data, then how can it be achieved? It cannot decrypt the original messages encrypted by different users' keys. I found a paper, https://eprint.iacr.org/2014/1017.pdf, however, it performs sort over the data encrypted with same key. But in my project requirements are different where each data element is encrypted by a different key of the client. (each key shared b/w a client and the server).

Any help is appreciated.

In short: What you ask for is impossible.

You want to sort ciphertexts, which are encrypted with different keys, without being able to decrypt them and not knowing the key(s). Let's assume for a moment that this would be possible.

And then there is an attacker, who just gets a single ciphertext. Now, you have to assume that the encryption scheme is public, and everyone can encrypt anything with any key. And there is a certain message space, e.g. a 256 bit integer.

Now the attacker chooses the integer in the middle, encrypts it under any key. With this value and the challenge ciphertext he uses the sort algorithm. Even if the sorting would be randomized, he still could detect his own input - he chose the key for that ciphertext. And from the sorting he now knows if the plaintext in the ciphertext is lower or higher than his own chosen message. If the ciphertext was lower, he will do the same again, with a value in the middle of the lower interval. Basically, this is just a binary search for the plaintext. Therefore, the encryption scheme is insecure even against a ciphertext-only attack.


Why have round constants in hashes? This may seem like basic crypto knowledge, but why do hash functions like SHA-2 and Whirlpool have round constants that are absorbed into their respective states?

I can understand that in a cipher you need some way to incorporate a variable secret key, but there are no such user keys for hash functions.  All the round constants start off from fixed (and publicly known) values. I thought that substitution and permutation operations were sufficient for encryption. So, why XOR in round constants?

There are attacks on both blockciphers and hash functions that can exploit symmetry in the round functions.  For example, completely identical round functions can permit Slide Attacks on Hash Functions, and rotational symmetries of the round function can permit rotational cryptanalysis.  The round constant addition or 'iota' step of the Keccak Hash Function is designed to break up the self-similarity symmetry of the round function.  Similar tweaks to the 'key schedule' (i.e. round) constant of Threefish/Skein were intended to break up rotational symmetries (see section 9.5.2 of the latest specification for details).

The up shot is that too much symmetry can be very dangerous, even for hash functions, and opens the door to attacks.  Round constants are an easy and cheap way to close that door.


How are the AES S-Boxes calculated? I'm trying to understand how the AES S-Boxes are calculated. I understand how the multiplicative inverse is calculated over $GF(2^8)$, but I'm confused by the description of the affine transformation. I haven't been able to Google a good explanation of how the S-Box values are calculated. Can someone explain how this works, starting after the calculation of the multiplicative inverse?

The affine transformation works similar to MixColumns, but operates on an array of 8 bits instead of 4 bytes. Confusion in various descriptions of the affine transform in AES comes from where the LSB of the input byte is located. Some show it at the top of the column, others show it at the bottom. I will be using the version shown in the Rijndael paper, with the LSB at the top of the column.

The matrix used in AES is a rotational matrix based on the value 0x1F, which is 00011111 in binary. The multiplication is performed in the field GF(2), as is the addition of the final vector 0x63. Addition in GF(2) is the same as xor.

The bit indexes for the matrix are 76543210, with 0 being the least significant bit and 7 being the most significant. Each column is the previous column rotated to the left by a single bit, as shown here:

0  7  6  5  4  3  2  1
1  0  7  6  5  4  3  2
2  1  0  7  6  5  4  3
3  2  1  0  7  6  5  4
4  3  2  1  0  7  6  5
5  4  3  2  1  0  7  6
6  5  4  3  2  1  0  7
7  6  5  4  3  2  1  0

For the AES 0x1F affine matrix, the bits are arranged in the following way:

1  0  0  0  1  1  1  1
1  1  0  0  0  1  1  1
1  1  1  0  0  0  1  1
1  1  1  1  0  0  0  1
1  1  1  1  1  0  0  0
0  1  1  1  1  1  0  0
0  0  1  1  1  1  1  0
0  0  0  1  1  1  1  1

For an input of 0x53 in AES, we first find its inverse, which is 0xCA, represented in binary as 11001010

The affine transformation is as follows. The input bits are multiplied against the bits of a given row, with the first bit the LSB of the input. Input bit 0 is only multiplied by row bit 0, and so on. Only when both values are one (logical AND) is the result one. Finally, all bits are XORd against eachother within that row to generate the transformed bit for that row.

Input = 0  1  0  1  0  0  1  1 (LSB First)
Row 0 = 1  0  0  0  1  1  1  1
Bit 0 = 0  0  0  0  0  0  1  1 = 0

Row 1 = 1  1  0  0  0  1  1  1
Bit 1 = 0  1  0  0  0  0  1  1 = 1

Row 2 = 1  1  1  0  0  0  1  1
Bit 2 = 0  1  0  0  0  0  1  1 = 1

Row 3 = 1  1  1  1  0  0  0  1
Bit 3 = 0  1  0  1  0  0  0  1 = 1

Row 4 = 1  1  1  1  1  0  0  0
Bit 4 = 0  1  0  1  0  0  0  0 = 0

Row 5 = 0  1  1  1  1  1  0  0
Bit 5 = 0  1  0  1  0  0  0  0 = 0

Row 6 = 0  0  1  1  1  1  1  0
Bit 6 = 0  0  0  1  0  0  1  0 = 0

Row 7 = 0  0  0  1  1  1  1  1
Bit 7 = 0  0  0  1  0  0  1  1 = 1

The final result LSB first is 01110001 or MSB first is 10001110 = 0x8E. This value is then added (XOR) to the final vector 0x63, giving an output of 0xED


How random is the shared secret in the Diffie Hellman key agreement How random is the value $ZZ$ in the DH protocol?

This question was triggered by this somewhat naïve implementation in I2P shown by Sergei at Stackoverflow. Obviously $ZZ$ is distinguishable from a random oracle, as the first byte will be lower or equal to the highest byte of $p$, if $p$ is encoded using the same $I2O$ (integer-to-octetstring) function.

Is there a mathematical function that shows how much "entropy" there is in the first (highest order) $x$ bytes taken out of $ZZ$?

The shared secret generated by the Diffie–Hellman key exchange is a random element of the subgroup of the multiplicative group modulo $p$ generated by $g$.

In particular, for $g$ and $p$ chosen as specified in RFC 2631 section 2.2, i.e. so that $p = jq+1$, where $q$ and $p$ are both prime, $j$ is a small number (often 2, making $p$ as safe prime) and $g$ generates the order $q$ subgroup modulo $p$, this subgroup contains $q$ elements and the shared secret therefore (assuming that the private keys are appropriately generated, of course) has $\log_2 q$ bits of entropy.

The recommended way to extract this entropy into a useful form is to hash the shared secret or, better yet, feed it into a key derivation function like HKDF (RFC 5869).
What you're asking is how bad is it if we simply take the first (or last) 256 bits of the binary encoding of the shared secret and use them as an AES-256 key?

My answer, a bit surprisingly, would be "not too bad."  We may not get quite 256 bits of entropy out of the secret that way, but we ought to get at least 247 bits or so (assuming that the secret is long enough to have that many bits in the first place, of course), which is still plenty enough for any practical purposes.

Specifically, let's assume that $p$ is a safe prime (i.e. $j=2$), and that the secret is padded to the minimum number of bytes needed to encode $p$, as specified in RFC 2631.  Thus, the padded secret will be a bitstring with $n = 8 \cdot \lceil (\log_2 (p+1)) /8 \rceil \le \log_2 p + 8$ bits, and will contain $$m = \log_2 q = \log_2((p-1)/2) = \log_2(p-1)-1 \approx \log_2 p - 1$$ bits of entropy.  When we truncate the secret to 256 bits, we throw away some of this entropy, but at most only as many bits as we remove from the length.  Thus, the truncated secret will contain at least $m - (n - 256) = 256 - (n - m) \ge 256 - 9 = 247$ bits of entropy.

Now, in the code you refer to, the secret is apparently not padded to a fixed number of bytes, but rather has leading zero bytes removed.  However, at least assuming that $q \gg 2^{256}$, this still should not make much difference.  (In fact, in some cases it might even slightly increase the entropy left after truncation.)

To see why, let $k = 8 \cdot \lceil (\log_2(z+1))/8 \rceil$ be the number of bits needed to encode the secret $z$.  First, we'll observe that ${\rm Pr}[k < 256] = {\rm Pr}[z < 2^{256}] \le 2^{256} / q = 2^{256-\log_2 q}$.  For, say, $q > 2^{336}$, this probability is negligible (less than $2^{-80}$).  Thus, for large enough $q$, we may safely assume $k \ge 256$.

Now, for each possible length $k$, the secret $z$ lies in the interval $2^{k-8} \le z < 2^k$.  Using the same argument as above, we may show that, for any given $k$, $z$ must have at least $k - 9$ bits of entropy, and that truncating it to 256 bits must leave at least $256 - 9 = 247$ bits of entropy.  Since we'll have at least 247 bits of entropy regardless of $k$ (except in negligible cases), we'll have at least 247 bits of entropy overall.

(For $j > 2$, the constant $9$ above becomes $8 + \log_2 j$ instead, but that makes little difference unless $j$ is huge, which it normally shouldn't be.)

All that said, none of the above should be taken as an argument against using a proper KDF to convert Diffie–Hellman secrets into key material.  You definitely should do that, if only because a) the standards say so, b) it's still more secure and c) it provides other benefits such as salting.
Still, it does appear that simply using the raw truncated D–H shared secret as an encryption key may not be quite as bad as one might assume just based on reading the RFCs.


Is there some way to generate a non-predictable random number in a decentralised network? Is there a way to generate a random number with given restrictions:

It will be used in a decentralised network with a big number of peers (no central authority to generate it)
Its generation should not rely on any third-party service (for example, going to a specific website)
Its generation is triggered by a semi-random data being sent through the network, and it should relate to the data
The computer sending the data should not have an advantage in determining the random number (for example, computing some number that would have a really high chance of becoming the seeked number)

I was thinking of using a random number like that to counter a 51% attack against the Bitcoin network. The main problem there is that an attacker with a lot of computation power can compute a couple "blocks" in advance and only release them to counter "blocks" generated by legitimate users. I figured a way to counter that would be by requiring generation of some random number that couldn't be pre-computed in advance, but only when a block is sent through the network. Required use of that number would then invalidate blocks that are precomputed beforehand, preventing the attack.

So, is there a way to generate a random number like that described above?

The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them modulo some number or xoring them together. As long as your value was included then you are confident that the result is random. If the numbers used are large enough, the nonce is not required.


Blockchain use in record management From my understanding of blockchain, I feel the main use of blockchain is to do something in a decentralised way as compared to the traditional centralised way which involves a middle man. Usually, the centralised way is a much simpler way, but use of a more complicated way (blockchain) becomes justified because you are able to decentralise.it.

However, I see a lot of companies which are currently the central party trying to get into Blockchains. For e.g. banks etc. I am not sure what advantage there is here.

For example, take a look at this - ironmountain.com - What-is-blockchain-and-why-should-records-management-professionals-care

In my opinion, regular PKI is best suited for this. A user signs his document with his private key & then submits it to Iron Mountain. This will ensure integrity. So what advantage is it to either Iron Mountain or the user if Blockchain is adopted in this case.

It also seems as if Blockchain is getting forced into places where it's not necessarily the best solution.

Or am I wrong?

The purpose of the  bitcoin block chain is to provide an imitable public ledger.

If you read the original bitcoin paper you will see that the block chain is but one component of a larger whole that provides public trust that coins were not double spent. See section 2 "Transactions" that states this explicitly.

Within a traditional bank the ledger is private and transactions are not signed by the owner. The trust in this case is somewhat blind but revolves around a promise by the bank that it will handle transactions on your behalf with care, and after all it is in the banks own best interests to prevent double spending.

Why don't banks use a bitcoin style ledger, well a few spring to mind but I will admit to a little speculation here.

Block-chains are computationally expensive to check continuously and their are much faster book keeping methods borrowed from traditional accounting practices.
Database transaction logs and transaction hashing is available to prevent corruption of data in storage.
The ledger is private so the only entity the bank needs to satisfy the correctness of transactions is itself.
If the bank were to use a Block-chain then where are the private keys to sign transactions going to come from? Is the bank going to store them for its customers?

Lets now look at the article you cite from Iron Mountain. This is a slightly different kettle of fish. They store data that you CAN sign and while we expect that data to be private between the owner and storage provider the trust equation here is different. The bank was self incentivized not to duplicate or modify transactions because it would directly loose money, in the IM storage case - aside from paying them monthly fees and perhaps reputation - we have no implicit reason to trust that they will not modify information. So for IM storage we do have a case for the use of a block-chain.

The question of 'are digital signatures enough' depends on

You use a decent key size sufficient to provide perfect forward security.
You trust all members of your organisation that have access to the private keys.

For archiving purposes a block-chain can also prove that one document preceded the next, something that digital signatures alone can not do. It can also show that no record has been tampered with by users with access to the private keys.


what is the benefit of lcm in cryptography? what is the benefit of lcm in cryptography?
and what is the effect of lcm on public key?

note *
lcm = Least common multiple

thanks

Regarding public key: In two prime RSA you often compute the secret key from the public as $d=e^{-1} \pmod {(p-1)(q-1)},\;$ but using $d=e^{-1} \pmod {\mathrm{lcm}(p-1,q-1)}$ may have some advantages.


Why do we use $a=1$ in elliptic curves? $y^2 + xy = x^3 + ax^2 + b$ is the elliptic curve over $\mathbb F_{2^m}$.

In the elliptic curve standard, most of the curves use $a=1$ a lot.

Is there any mapping for this such that $y^2 + xy = x^3 + ax^2 + b$ is equal or similar to $y^2 + xy = x^3 + x^2 + b$?

The title of your question is wondering why you often see $a = 1$ in the form of the elliptic curve you specified. I would first check the top answer (Thomas Pornin's) to this question.

This form of the curve is called non-supersingular. If $b=1$ and $a \in \{0,1\}$, it's called a Koblitz curve or anomalous binary curve.

The short, quick answer is: if your curve is of the form you specified over $\mathbb{F}_2$, with $a = 0$ or $a = 1$, and $b=1$, it allows you to use the Frobenius endomorphism $\tau: \mathbb{F}_{2^m} \rightarrow \mathbb{F}_{2^m}, \alpha \mapsto \alpha^2$ to very quickly calculate $2P$ for a point $P$; you just square coordinates instead of having to use the usual doubling or addition formula. This is much more efficient than the usual method of doubling.

For a point in $\mathbb{F}_{2^m}$, $\tau$ satisfies $2 = \mu \tau - \tau^2$, where $\mu = (-1)^{1-a}$. So if you want to compute $nP$, with $P \in \mathbb{F}_{2^m}$, first write $n$ as a sum of powers of $\tau$ and then apply those terms to your point $P$: $\tau(P) = (\tau(x), \tau(y))$.

I'm not sure if this is the mapping you're looking for, but you can see you get a lot of mileage out of  $a \in \{0,1\}$ on an elliptic curve over $\mathbb{F}_{2^m}$!


What's the meaning of probabilities in differential privacy formula? I don't understand what does it mean by "The probability is taken is over the coin tosses of K."

Does it mean, the probability distribution is generated based on exactly same data but only the function is selected randomly?

So it's the data that ensures the differential privacy instead of the function, right?

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms.

For simplicity, assume there are $N$ randomized functions $\mathcal{K}$ possible, and one choose one uniformly with probability $1/N.$

For example, if we restricted ourselves to polynomials of degree $\leq k$ over $GF(q),$ there would be $N=q^{k+1}$ such possible functions and we choose a function by uniformly choosing each of its $k+1$ coordinates from $GF(q)$, thus with probability $q^{-(k+1)}.$

In this case the probability expression just means that
$$
\frac{\#\{\mathcal{K}: \mathcal{K}(D_1) \in S\}}{N}\leq
\exp(\epsilon)\frac{\#\{\mathcal{K}: \mathcal{K}(D_2) \in S\}}{N},
$$
and of course $N$ can be cancelled in the two sides of this equation. In general, the distribution may of course not be exactly uniform.


Evaluating Algebraic Complexity of a S-box While studying the design and the desirable properties of an AES S-box , I came to know that Algebraic Complexity is also an important property of an S-box which is usually considered while evaluating the properties of an S-box.

After reading several papers (such as APA), I get to know that Algebraic Complexity is basically the number of terms appearing in the "Algebraic Equation" representing that S-box.

After doing a bit of a research (source) I get to know there are three main methods for finding the polynomial equation to represent S-box which are:

Lagrangian interpolation
Polynomial linearization
Q-ary polynomial deduction

But honestly I am unable to understand any of the above methods to find the algebraic equation of the given S-box. So that ultimately I can evaluate it's Algebraic Complexity.

So, if someone can explain it in detail (or algorithm for the same), it would be really helpful for me to write the code for it. Or if there is some other way (or codes) to find Algebraic Complexity or Algebraic Equation of an AES S-box please share it.

TL;DR: Given an S-box ($n \times n$) , how can we evaluate its Algebraic Equation or Algebraic Complexity?

The interpolation of Sbox is based on Lagrange algorithm.
the following three steps are used to calculate the interpolation of S-box:

represent the S-box values as polynomial system, where P and C are polynomial representation of S-box input and output.
M (N x N ) is a matrix composed of P power polynomial. N is sbox size (256 for 8-bit sbox)
solve B form the following equation: M.B=C

# the Equation is M.B=C.
#     1  p0  p0^2  p0^3  p0^4  p0^5 .......  p0^d
#     1  p1  p1^2  p1^3  p1^4  p1^5 .......  p1^d
#  M= 1  p2  p2^2  p2^3  p2^4  p2^5 .......  p2^d
#     1  p3  p3^2  p3^3  p3^4  p3^5 .......  p3^d
#       .
#       .
#       .
#     1  pn  pn^2  pn^3  pn^4  pn^5 .......  pn^d
#  size of M is dXn , d and n are equal for sbox, they are GF (2^8) (8-bit sbox)
# Calculation steps.
#   1. convert Sbox table to polynomial of input and output, vectors (P is input  and C is output)
#   2. calculate M table
#   3. B=M.solve_right(C)
#

The following code is implementation of interpolation representation of Rijndael S-box

f=x^8+x^4+x^3+x^1+1  # irreducible polynomial
L.<z>= GF(2^8,modulus=f)
R=PolynomialRing(L,'x')
N=256
M=matrix(L,N,N)
S=[0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
                             0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
                             0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
                             0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
                             0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
                             0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
                             0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
                             0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
                             0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
                             0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
                             0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
                             0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
                             0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
                             0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
                             0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
                             0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16] # rajS-box

C=vector(L,N)
P=vector(L,N)

# step 1
for i in range(0,N):

    P[i]= (i) + z^1*(i>>1) + z^2*(i>>2) + z^3*(i>>3) + z^4*(i>>4) + z^5*(i>>5) + z^6*(i>>6) + z^7*(i>>7)
    C[i]= S[(i)] + z^1*(S[i]>>1) + z^2*(S[i]>>2) + z^3*(S[i]>>3) + z^4*(S[i]>>4) + z^5*(S[i]>>5) + z^6*(S[i]>>6) + z^7*(S[i]>>7)

#print P
#print C
# step 2
for j in range(0,N):
    for i in range(0,N):
        M[j,i]= P[j]^i

#step 3
B=M.solve_right(C)

print B


What tests can I do to ensure my random number generator is working correctly? In the past I have used the Chi-squared test to check the statistical randomness of my generator. Is this a good test to use? Are there other tests?

Checking statistical randomness is a semi-good test. What I mean by that is that if a given PRNG does not look good statistically, then it is utterly proven to be pure junk. On the other hand, good statistical randomness does not tell you much with regards to cryptographic security. Cryptographic security is about whether the PRNG output could be predicted by a sentient attacker who knows the in and outs of your algorithm (but not its internal state). Statistical randomness is about whether the PRNG output could be predicted by a trained monkey.

"Diehard tests" used to be popular for testing non-cryptographic PRNG. During the AES competition (a dozen years ago), NIST ran them on all AES candidates, and found nothing, and the general opinion among cryptographers was that it was mostly a waste of time.

A Linear Feedback Shift Register has handsome results with Diehard -- and using it for cryptography is immediate failure.


Applying differential cryptanalysis to ciphers with addition mod $2^{32}$ I am studying differential analysis and have a question.

Consider the following simple cipher:
$$c_1 = S(m_1 \oplus k_1) \oplus k_2$$
(Plaintext $m_1$ xor with key $K_1$, then result goes into an S-BOX, the output of which is xor'd with $K_2$). This case is very simple. Using the main property of XOR we can get differential that independent from KEY.

How do we can get such differential if instead of XOR we use addition modulo $2^{32}$? When using XOR, we have  $(m_1 \oplus k_1) \oplus ( m_2 \oplus k_1 ) = m_1 \oplus m_2$. What operation need apply to get rid of the key when using addition modulo $2^{32}$?

This is called an Even-Mansour cipher.

Actually, for the differential cryptanalysis it does not matter what sort of difference you use, you only need that it propagates deterministically through linear transformations  (whatever linearity means). In this case you use a difference modulo $2^{32}$:
$$
A \boxminus B \equiv (A-B)\pmod{2^{32}}.
$$

You compute the differential distribution table for $S$ in the same way, but replace $\oplus$ with $\boxminus$.


Public Key Cryptography: Diffie-Hellman Key Exchange Please watch this video it's very short. If you already know cryptography and really good at it please start from 3:51.

I didn't understand the step at 4:39, can someone here to explain?

Why is $16^{54} \mod 17$ is equal to

$3 ^ {24\times54} \mod17 \equiv 1$?

He just wrote that. Alice didn't knew bob's private number how did he raised $3 ^{24}$?

Alice didn't know that $16\equiv 3^{24}\mod 17$. The video just made it clearer that they were intrisically computing the same value.

I'm guessing that the point the video was trying to make was that
$$3^{54\times24}\equiv3^{24\times54}\equiv 16^{54}\equiv15^{24}\equiv1\mod 17.$$


Generating a strong unique Initialization Vector How can I determine if I am generating a unique and strong Initialization Vector? If my mode is generating Keystream? Is there any scientific explanation in generating a unique and strong Initialization Vector?

"Unique" is relatively straight forward. It's something you haven't used before. Unique usually only applies to the individual party, you only need to verify that the IV is unique for your usage with the current key.

"Strong" relates to the requirements that your mode of operation has for the IV. Different modes require different constraints on the IV. Which ties in with...

The "scientific explanation" for a good IV comes from a security proof reduction. Researchers design a scheme (like a mode of operation, such as CBC) that uses a cryptographic primitive (like a block cipher, such as AES) that requires an IV, then they prove (or at least argue) that the scheme using the IV is as secure as the underlying primitive given certain constraints on the IV. In other words, if the scheme can be broken it isn't due to the IV as the IV's requirements makes the scheme no weaker. This principle applies to every form of IV, be it for a stream cipher or block cipher. Those constraints on the IV are the strong IV values you should use.

For example, CBC mode for block ciphers requires that the IV be unpredictable. So commonly it is either a) random or b) a unique value encrypted by a key. (The two most common IV requirements are that it be random or unique.) CBC has a proof of security that says that if one of those criteria for the IV are met, then the resulting scheme is as strong as the underlying block cipher.

How do you verify the IV is good? You should put your analysis into the process that does generate the IV, then you can test the IV after it is generated. The main focus should go on how the IV is generated and verifying it conforms to the specification's requirements.

For example: the requirement you are satisfying may be that the IV be random. You might use the high-quality native random number generator from the operating system (/dev/random, CryptGenRandom, etc) to do so. You can do some tests on the output to verify that something obvious hasn't gone wrong, like the IV doesn't fail to all zeros. But you can't verify that the IV is actually random, only that it looks sufficiently random. Verifying that something random or indistinguishable from random is really hard to do in real-time.
Another example: the requirement you satisfying may be that the IV be unique. You can use a counter that increments every time an IV is generated and ensure that the counter has a sufficient size that it won't roll over too soon. Or you can use a timestamp and take care to ensure you don't generate multiple IVs within the resolution period of the timestamp. If you want to be very careful, you can keep a list of all previously used IVs and check the list for each new one to ensure you aren't re-using it.

The summary is: Cryptography researchers say that certain schemes are secure given constraints on the IV. These constraints will be widely known and should be available for you to find.


Is Lamport-Diffie EUF-CMA secure in the standard model? Is the Lamport-Diffie signature secure in the standard model? I ask this question because I am reading the Postquantum-Cryptography book and the reductions the authors use one-way functions and not hash functions. According to my understanding, ROM is used to replace hash function for random oracles, but in Lamport-Diffie only pre-image resistance functions are sufficient.

Is the Lamport-Diffie signature secure in the standard model?

Technically, no, the Lamport(-Diffie) one-time signature scheme is not EUF-CMA secure, however, also technically "it depends".
Nominally, a signature scheme is typically called "secure" - especially in the public-key world - if for a polynomial number of adverserial interactions with it in the relevant model the advantage of said adversary is still negligible - with the negligibility coming from some security assumption typically.
However, you can easily construct an adversary which performs 2 interactions with the signature scheme in the EUF-CMA model and achieves an advantage of 1 from that. Such an adversary would e.g. query $0^n$ and $1^n$ as messages, revealing all private keys.
Also however, we can still construct a security statement, namely $$\mathbf{Adv}^{\textsf{EUF-CMA}}_{\text{LD-OTS}_F}(\mathcal A;q,n)\leq\begin{cases}\mathbf{Adv}^{\textsf{OWF}}_{F}(\mathcal A';n)&q\leq 1\\1&\text{else}\\\end{cases}$$ where $n$ is the security parameter, $q$ is the number of queries, $\mathcal A'$ is an existentially qualified adversary against the underlying OWF $F$ and $\mathcal A$ is the polynomially-bounded universally qualified adversary. The order of quantifiers is for all $\mathcal A$ exists $\mathcal A'$.


Is a collision attack possible on MD5 if message is known partially Is it possible to find $m'$ such that $\operatorname{MD5}(m'||m_1)=\operatorname{MD5}(m_1||m_2)$ if I know $m_2$ and $\operatorname{MD5}(m_1||m_2)$? Is this a collision or a preimage attack?

Also in this case is it possible to find $m'$ and $H$ such that $\operatorname{MD5}(m_1||m')=H$ if I know $\operatorname{MD5}(m_1||m_2)$ and $m_2$?

Basically a message like $(M,\operatorname{MD5}(M||m1))$ is sent from server to client (only client and server know $m_1$). So is there an attack in this scenario?

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, and want to find $m'$ such that $\operatorname{MD5}(m'||m_2)$ reaches a known, predetermined value, then you must break MD5's preimage resistance, or at least second-preimage resistance.

This would be true even if you knew $m_1$: if you know $m_1$, then the problem becomes: find $m'$ such that $\operatorname{MD5}(m'||x) = y$ for two given values of $x$ and $y$ ($x = m_1$ and $y = \operatorname{MD5}(m'||m_2))$ in your presentation). Since $y$ is the result of MD5 on a known entry, this problem is a second-preimage attack with an extra constraint on the result. MD5 is still quite robust against second-preimage attacks, so this cannot be done with existing knowledge and technology.

Not knowing $m_1$ cannot help: if the problem is already hard with knowledge of $m_1$, then it cannot be easier without knowledge of $m_1$.

The explanation above is the general case. In some cases it can be quite easy: for instance, if $m_2$ happens to be equal to $z||m_1$ for some value $z$, then $m' = m_1||z$ would be a solution.

If you have $\operatorname{MD5}(m_1||m_2)$ and you know $m_2$, then you can trivially compute $\operatorname{MD5}(m_1||m')$ for any $m'$ which begins with $m_2$, followed by the MD padding, followed by arbitrary contents. This requires knowledge of the length of $m_1$ (but not its contents). For details, look up the length extension attack.


Exposed raw RSA private key operation Assume that there is a smartcard or other hardware token that exposes the raw RSA private key operation (modular exponentiation, with or without CRT parameters). Is there any possibility that raw RSA leaks information about the private key that would not otherwise become available?

Please clearly distinguish between attacks on the algorithm itself and side channel attacks. This question is not about the security of unpadded RSA signatures themselves.

As far as we know, no: from a mathematical standpoint, exposure of the raw RSA private key operation does not leak the private key, or anything allowing to perform the raw RSA private key operation (such as another private key, or a factorization of the public modulus). We have no proof; but this has been well studied, and any advance in that direction would make the headlines.

Things can be very different in practice, where you have to consider side channel and fault injection attacks. There are so many such attacks around, and they depend so much on the implementation (hardware, CRT or full modulus, Montgomery or straight arithmetic, blinding(s), randomized exponent scanning, other countermeasures..) that I pass on that part of the question.


$\alpha^{2^{m} + 1}$ is a generator of $\operatorname{GF}(2^m)$? This is from a paper (Partitions in the S-Box of Streebog and
Kuznyechik) about S-Boxes:

Let $\operatorname{GF}(2^{2m}) = \mathbb{F}_2[X]/p(X)$ be a finite field of even degree defined by a primitive polynomial $p$. The multiplicative subgroup $\operatorname{GF}(2^{2m})^*$ is cyclic and generated by $\alpha$ which is such that $p(\alpha) = 0$.
In this context, $\alpha^{2^{m} + 1}$ is a generator of the multiplicative subgroup of the subfield $\operatorname{GF}(2^m)$

I don't understand why it holds that $\alpha^{2^{m} + 1}$ is a generator of the subfield?

Since you haven't heard of splitting fields, here is an argument based on more elementary group theory.

Let $G$ denote a cyclic group. Then, it is easy to show (or you might already know it) that if $\alpha \in G$ is an element of order $n$ (we write $\mathsf{ord}(\alpha)=n$ to denote this), then
$$\mathsf{ord}(\alpha^k)= \frac{\mathsf{ord}(\alpha)}{\gcd(\mathsf{ord}(\alpha),k)} = \frac{n}{\gcd(n,k)}.$$
Choose $G = \text{GF}(2^{2m})^*$ whose generator $\alpha$ is of order $n = 2^{2m}-1$, observe that $2^{2m}-1 = (2^m-1)(2^m+1)$, and deduce that
$$\mathsf{ord}(\alpha^{2^{m}+1}) = \frac{2^{2m}-1}{\gcd(2^{2m}-1,2^{m}+1)} = \frac{(2^m-1)(2^m+1)}{2^{m}+1}
= 2^m-1.$$
Thus, $\alpha^{2^{m}+1}$ generates the unique cyclic subgroup (of order $2^m-1$) of $\text{GF}(2^{2m})^*$ which itself is of order $2^{2m}-1$. Now, $\text{GF}(2^{m})$ is a subfield of $\text{GF}(2^{2m})$ and so this subgroup must be $\text{GF}(2^{m})^*$.


Encrypting any text without key after padding oracle attack in CBC mode Suppose the decryption program is already built. Now I want to encrypt an arbitrary plain text given the IV and the decryption program (no key). From the formulas, we have $$Dec(C_i)\oplus C_{i-1}=P_i$$ $$Dec(C_1)\oplus IV=P_1$$. However, given these information, I can only figure out $Dec(C_1)$. I have read this question, but it assumes all $Dec(C_i)$ are known, which is not correct for my case. My question is how can I find out all $C_i$? (Please note there isn't a database of $P_i$, $Dec(C_i)$ pairs to look up collisions).

I thought about using the decryption program to brute force each possibility, but it will take too long time. I also tried applying similar technique for decryption algorithm(tried to reverse the process), but still can't get a result. Any hints would be appreciated.

CBC encryption requires the encryption operation of the cipher, which cannot be build from just the decryption operation of the cipher. Your solution space is empty.

Padding oracle attacks let you find the plaintext without attacking the cipher itself. That's not the same as creating an encryption oracle.


Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$ Recently a few papers have appeared that describe a new approach to factoring, using elliptic curves over $\mathbb{Q}$.  See, e.g.,

Factoring integers and computing elliptic curve rational points, Iftikhar A. Burhanuddin and Ming-Deh A. Huang.
Factoring integers using elliptic curves over Q, Xiumei Li, Jinxiang Zeng, arXiv:1207.0274v2.

However, these papers don't seem to describe the complexity of these novel methods.  What is the running time of these methods?  Are these methods faster than the standard known algorithms for factoring?  What is the impact of these new ideas on the security of RSA and other factoring-based cryptosystems?  Should we be concerned?

I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.)

There are many ways to compute factorings and discrete logarithms where you first do some very hard number theoretic computations (e.g. related to an elliptic curve over the rationals), then easily factor or compute a d.log. I designed such an algorithm myself once, and it was utterly useless.


is MAC double-hashing enough to prevent length extension attacks? I know that
$$mac=\operatorname{SHA1}(secret\mathbin\|message)$$
is prone to length extension attacks, but what about:
$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))?$$
In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial $\operatorname{SHA1}$ itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)
(edit: originally had a second question about HMAC here as well, but I think I'll take that in a separate thread, sorry about the confusion in the comments)

$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))$$

is mac double-hashing enough to prevent length extension attacks?

Double hashing is defined by Ferguson and Schneier in their book Practical Cryptography in Chapter 6.3.1  to countermeasure again length extension attacks (and SHA256D used in Bitcoin). The details in their book, I don't have a copy. So, we can assume it has resistance to length extension attacks. Or, one can give a simple argument as;
To execute the length extension attack, the attacker needs to produce $$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad\mathbin\|message_2\mathbin\|pad_2))$$ But they can only control the $h$ and the actual length extenstion attack can work on the outer call like this
$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad)\mathbin\|message_2\mathbin\|pad_2)$$. And even the attacker can forge the mac (i.e. the result is same) it will fail since it will not work.

In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial SHA1 itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)

So, you want to use this as a Message Authentication Code (MAC).
If the secret is at least 128 bits, then there is no way to brute-force the secret.
Bruteforce the initial here is called a preimage attack that is given a hash value $h$ find an input $x$ such that $h=H(x)$ ( or $h=H(H(x))$). The cost of the generic pre-image attack is $\mathcal{O}(2^n)$ where $n$ is the output size of the hash function $h$. For SHA-1 this makes $\mathcal{O}(2^{160})$. SHA-1 is shattered but not broken in the pre-image resistance. Therefore pre-image attack is infeasible. Actually, the pre-image attack doesn't guarantee to return the actual message used to create the hash value. One may fail there too.
There is no security proof of this construction as far as I know as a secure MAC. There is one extensive answer that on the upper level  $H(k\mathbin\|H(k\mathbin\|m))$.
Instead, use the proven one; the HMAC-SHA256, or the new one with SHA3; KMAC. Since SHA3 has resistance to length extension attacks, the construction of KMAC is much easier.
SHA3 design makes the prefix construction $H(k\mathbin\|m)$ a secure PRF, and come with built-in PRF mode, the keyed KMAC. Is comes with a theorem that connects the security of the PRF to the primitive.
Also, note that the trimmed versions of SHA2 series also have resistance to length extension attacks like SHA-512/256. The trim prevents to add an extension message and the padding to continue to hashing. One has to guess/try the trimmed amount that is impossible if the trim > 120.

update: I've looked into the book section 6.4. It turns out that they propose two methods and a new one in the new book.

propose is replacing $m \to h(m)$ with $m \to h(h(m)\mathbin\|m))$. And they defined $h_{DBL} := h(h(m)\mathbin\|m))$
They believe that if $h$ is a secure cryptographic hash function with $n$ nit output then it has a security level $n$. This is slow and you need to has the entire message twice.

propose is the double hashing $h(h(m))$ with only claimed claimed that it is has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.

proposal is in the new book Cryptography Engineering: Design Principles and Practical Applications 1st Edition

$$h_d := h(h(0^b\mathbin\|m)$$
and claimed that it has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.


IPsec authentication and encryption lgorithms I am looking for the implementation of IPsec security algorithms for both
authentication and Encryption.
Is there any open source implementation available for the same ?

And if someone supposed to implement these algorithms, then what background knowledge is required for someone new in the cryptography world?

Please recommend some links and documents that can help in understanding these
algorithms for the implementation.

Also suggest some open source implementations of following algorithms:

 HMAC-MD5,
 HMAC-SHA1,
 DES-CBC,
 Triple-DES-CBC and
 AES

and the open source projects that have used it.

Apart of the one I have listed above which are others algorithms that can be used for IPsec ?

What are the differences between authentication algorithms (HMAC-MD5 and HMAC-SHA1) and similarly
what are differences between encryption algorithms (DES, 3DES, AES) ?

Your question is kind of broad, but I think it's still more or less answerable.  Let me just address your sub-questions one by one:

  I am looking for the implementation of IPsec security algorithms for both authentication and Encryption. Is there any open source implementation available for the same?

Yes, plenty.  If you specified which platform and/or language you're using, we could point you to some suitable ones, but just off the top of my head, the OpenSSL library is fairly extensive and portable.

  And if someone supposed to implement these algorithms, then what background knowledge is required for someone new in the cryptography world?

It depends a lot on just which kinds of algorithms you want to (re)implement.  Generally, high-level "derived" algorithms like HMAC or basic cipher modes like CBC, which simply build on top of existing crypto primitives, are relatively easy and safe to implement, whereas low-level "primitive" algorithms like block ciphers or hash functions are difficult to reimplement efficiently and securely.

In any case, the standard advice with crypto is that, if you don't have to implement something yourself, don't.  Unless you're only doing it as a learning exercise, that is, and never intend to actually use your code for anything security-critical.

In any case, if you do end up implementing some crypto code yourself (especially, God forbid, if it's low-level), the very next thing you should do is read up on possible attacks against your code, and see if you can break it.  If not, show it to someone who knows more about crypto than you, and see if they can break it.  Repeat until your code gets broken, or you run out of experts to consult. :-)

  Please recommend some links and documents that can help in understanding these algorithms for the implementation.

What you really need, to begin with, is a good introduction to cryptography and data security.  I'm not really the best person to give specific recommendations here, but some books I've seen recommended by other include the Introduction to Modern Cryptography by Katz & Lindell, the Handbook of Applied Cryptography by Menezes, Oorschot & Vanstone, or, if those seem too intimidating in their scope, perhaps Cryptography: A Very Short Introduction by Piper & Murphy.

For learning about specific crypto algorithms, Wikipedia is often a very good starting point, and will typically have links to further material.  If the algorithm is standardized, reading the relevant RFC / NIST SP / other standard is also often helpful.  Many algorithms also have their own semi-official web pages maintained by their developers; for example, if you wanted to learn about HMAC, you could do a lot worse than starting at Mihir Bellare's HMAC page.  And, of course, there's plenty of useful information right here on Crypto.SE, if you just search for it.

  Also suggest some open source implementations of following algorithms: HMAC-MD5, HMAC-SHA1, DES-CBC, Triple-DES-CBC and AES, and the open source projects that have used it.

Those are all very common algorithms, and any half-decent crypto library (such as the OpenSSL library mentioned above) should support them.

  Apart of the one I have listed above which are others algorithms that can be used for IPsec?

I'm not really familiar with IPsec myself, and the Wikipedia page just refers to RFC 4835, which seems to be the authoritative reference.  It's a pretty short and readable document, so I suggest you just read through it.  In particular, sections 3.1.1 and 3.2 list the encryption and authentication algorithms that IPsec implementations MUST, SHOULD and/or MAY support:

    Requirement    Encryption Algorithm (notes)
    -----------    --------------------------
    MUST           NULL [RFC2410] (1)
    MUST           AES-CBC with 128-bit keys [RFC3602]
    MUST-          TripleDES-CBC [RFC2451]
    SHOULD         AES-CTR [RFC3686]
    SHOULD NOT     DES-CBC [RFC2405] (2)

    Requirement    Authentication Algorithm (notes)
    -----------    -----------------------------
    MUST           HMAC-SHA1-96 [RFC2404] (3)
    SHOULD+        AES-XCBC-MAC-96 [RFC3566]
    MAY            NULL (1)
    MAY            HMAC-MD5-96 [RFC2403] (4)

  What are the differences between authentication algorithms (HMAC-MD5 and HMAC-SHA1) and similarly what are differences between encryption algorithms (DES, 3DES, AES)?

In brief:

MD5 is an old hash function that is considered broken for many purposes, although there are so far no known effective attacks on it when used specifically in the HMAC construction.  SHA-1 is also considered somewhat weak these days, although not nearly as weak as MD5, and the NIST now recommends phasing it out (although HMAC is, again, considered an exception).

The hash functions currently recommended by NIST (and mostly by industry consensus) are the SHA-2 family of hashes, which are considered more secure than SHA-1.  There's also an upcoming SHA-3 standard, which has not yet been finalized, but should be due any day now; it's not designated as a replacement to SHA-2, which is still considered secure, but as an alternative to it.

In any case, given the choice between MD5 and SHA-1, you should definitely go with SHA-1.  But it would be better yet if SHA-2 were an option.
DES is an old block cipher from the 1970s, and should no longer be used; its main weakness is simply its short key length, which makes it vulnerable to brute force attacks on modern computers.

3DES, a.k.a. Triple DES, is an encryption scheme built on top of the DES cipher, which effectively doubles its key length, but also triples the time needed to encrypt and decrypt messages.  It's still considered secure, although it's not as efficient as more modern ciphers.

AES is the modern replacement for DES, and the block cipher currently recommended by NIST.  It has several improvements over DES, including significantly longer key length, twice as long block size (which matters for some application involving large amounts of data) and, frequently, higher speed.  In general, if you have no specific reason to use something else, AES is the cipher you should be using these days: it's fast, it's secure, it's widespread and, above all, it's standard.  To slightly misquote an old catchphrase, nobody ever got fired for using AES.


How to compute result in last step of Socialist millionaires problem? I was trying to understand Socialist millionaires problem and solution in OTR protocol, but I'm stuck at figuring out how and who computes $(Q_{a}Q_b{}^{-1})^{\alpha\beta}$.
If I'm Bob then I received $Q_{a}$, I can compute $Q_{b}^{-1}$ and I know my $\beta$. However I don't know $\alpha$. How is it computed then?
I'm uploading screenshot of wikipedia page, which I'm reffering to, in case it get's modified in future

The answer is that Bob and Alice each calculate $(Q_a Q_b^{-1})^{\alpha \beta}$. Alice computes the quantity $Q_a$, Bob computes $Q_b$, Alice computes $(Q_a Q_b^{-1})^\alpha$ and sends that to Bob, who can compute $c = (Q_a Q_b^{-1})^{\alpha \beta}$.

Let's step through the protocol, keeping in mind the OTR reference (assuming that you do the tests, which I'm leaving out because it clutters things more):

$\text{Alice} \rightarrow \text{Bob}$: Alice picks random $a$ and $\alpha$, sends $g_{2a} = h^{a}$ and $g_{3a} = h^{\alpha}$ to Bob.

$\text{Bob} \rightarrow \text{Alice}$: Bob picks random $b$ and $\beta$, computes $g \equiv g_{2a}^{b}$ and $\gamma \equiv g_{3a}^{\beta}$, picks random $s$, sends $P_b \equiv \gamma^s$, $Q_b = h^s g^y$, $g_{2b} = h^b$, and $g_{3b} = h^\beta$ back to Alice. note: At this point, Bob has computed the secure $g$ and $\gamma$.

$\text{Alice} \rightarrow \text{Bob}$: Alice also computes $g = g_{2b}^{a}$ and $\gamma = g_{3b}^{\alpha}$, computes $P_a \equiv \gamma^r$, $Q_a \equiv h^r g^x$, and $R_a = (Q_a Q_b^{-1})^{\alpha}$, sends $P_a, Q_a, R_a$.

$\text{Bob} \rightarrow \text{Alice}$: Bob computes $R_b \equiv (Q_a Q_b^{-1})^{\beta}$, compute $c = R_{ab} = R_a^{\beta}$, check whether $c = P_a  P_b^{-1}$, send $R_b$.

$\text{Alice} \rightarrow \text{Bob}$: compute $c = R_{ab} = R_b^{\alpha}$, also check $c = P_a P_b^{-1}$.

Bob can compute $c$ in the fourth step, because Bob computed $Q_b$ in step 2, and received $R_a$ from Alice in step 3.


Will repeated rounds of SHA-512 provide random numbers? If I hash a keyword with SHA-512 and then feed the output as the key for the next round ....and keep repeating this process, will I gather a stream of random numbers?

For an adversary not knowing the definition of SHA-512 (or just not knowing the 512-bit initialization constant of SHA-512, defined as the first sixty-four bits of the fractional parts of the square roots of the first eight prime numbers), the sequence obtained by
$$\begin{align*}
H_0&=\text{SHA-512}(Seed){\small\text{ where }}Seed{\small\text{ is the statement's keyword}}\\
H_{i+1}&=\text{SHA-512}(H_i)\\
\end{align*}$$
is a Cryptographically Secure Pseudo-Random Number Generator as far as we know. It is in practice indistinguishable from random for said adversary, with residual odds of the contrary less than $2^{-100}$, assuming a few additional requirements:

Less than $2^{200}$ outputs are available to the adversary [rationale: if it happens that the generator enters a cycle, then the adversary can predict future output, including with feasibly little memory; after about $2^{(512-100+1)/2}$ iterations of a random function with 512-bit output, odds of cycling are about $2^{-100}$; I kept some margin]. Notice that producing even the first $2^{60}$ outputs would take at least five years with current technology, because this RNG and SHA-512 are a serial process [estimate based on two gate delays each one picosecond per round].
This adversary uses classical computing means bound to perform less work than needed for $2^{250}$ hash computations (a safe assumption), or anything that I can fantasize today (your call) [rationale: the best explicit attack I have enumerates the SHA-512 initialization values, and that reaches odds $2^{-100}$ to succeed at about $2^{412}$ hashes; I kept a helluva of margin]; Note: 1 and 2 can be combined into the adversary can not perform the classical-computing equivalent of counting to $2^{200}$, which is still very credible.
$Seed$ is never reused.
The adversary does not obtain the SHA-512 specification (including initialization value) by some oblique mean: reverse engineering, operating goof, spying (including bribery and planting trojans), rubber hose cryptanalysis, side channels.. [Note: reading the official specification was discounted in the first sentence].

However, with respect to an adversary knowing the full definition of SHA-512 (which is the assumption a cryptographer will make by Kerckhoffs's principles), the generator is unsafe. In particular, $H_j$ for $j>i$ can be trivially predicted from $H_i$; the generator fails the next bit test.

In addition, from a practical perspective, the generator is very bad by the mere fact that it is simultaneously

deterministic;
without another key than a keyword presumably of low entropy;
without provision for key streching to slow keyword enumeration.

If the keyword is simple enough to be reliably memorized in a real application by a majority of adult humans, then password cracking can quickly find the keyword by enumeration knowing say 10 bytes of $H_0$.

So all in all, the generator is secure for some non-cryptographic applications like numerical simulations, and disastrous from the perspectives on-topic here.


Confusing XOR notation in textbook sample solution I am preparing for the midterm exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. The sample solution at the end the textbook makes this problem more confusing instead of clarifying it. $\oplus$ denotes XOR operation but what are we trying to XOR with?

$c = \oplus c_i$ and $i \in I(c)$, but $c_i$ is getting XOR with what?

Any help would be appreciated.

Textbook question:

Textbook sample solution:

The notation $c=\oplus~c_i$ is (terrible) shorthand for $$c=\bigoplus_{i \in I(c)} c_i$$ where the sum sign should be replaced by the big xor sign which could also be written as $$ c=\sum_{i \in I(c)} c_i,$$where $\sum$ denotes vector addition modulo 2.

An example of this decomposition (for length 8 vectors) is
$$c=(1,0,1,0,0,0,1,0)=$$
which is nonzero in positions 1,3, and 7, and satisfies
$$c=(1,0,0,0,0,0,0,0)\oplus(0,0,1,0,0,0,0,0)\oplus(0,0,0,0,0,0,1,0)$$
$$=c_1\oplus c_3 \oplus c_7=\bigoplus_{i \in I(c)} c_i$$ where $I(c)=\{1,3,7\}.$

Then, since $E$ is assumed to be linear, all the places you marked with an arrow make sense.


Simple question about the branch number of the matrix what is the branch number of the binary identity matrix?

For example, $ I $ is 4x4 binary identity matrix,

\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}

Here, the branch number is $min_x ( wt(x)+wt(Ix))=2 $.
Is that correct?

Yes. This a degenerate matrix that provides no mixing and has minimal branch number.


Visualization of Elliptic Point Addition In an introductory text, I found that point addition for elliptic curves can be made plausible as follows:

Given two Points, P, Q, the sum is defined as the point on the curve I get by connecting P with Q with a straight line. This line intersects the curve on a third point. After reflecting y I get the sum P+Q.

However, taking the points R and Q on the attached figure $y^2=x^3-\frac{29}{10}x +1$, where is the third point?

Should it be the point at infinity?
That cannot be from my point of view, because $P+Q=\infty$ would imply $P = -Q$ which is not the case.

See also:

http://demonstrations.wolfram.com/AdditionOfPointsOnAnEllipticCurveOverTheReals/
The Snapshot 1 is the curve I talk about. The following is stated below:

  For two points P and Q on an elliptic curve, the addition is defined as follows. Draw the line through P and Q to intersect the curve in a third point; then reflect that point in the  axis.

I think this is on-topic for cryptography, as this is a basic elliptic-curve related question that anyone interested in ECC will come across. Moreover, it is easily answered.

Although on the picture it seems that there is no third intersection point in the plane, there is one. Note that not the whole curve can be fit into this picture, since at some point we cut off the rest of the $x$ and $y$-axis. What remains unknown is what happens when $x$ becomes larger. Well, what happens is that slope of $E$ keeps increasing (resp. decreasing), going towards infinity (resp negative infinity). You can see this by considering the function $y(x)=\sqrt{x^3-\frac{29}{10}x+1}$, and always taking the positive (resp. negative) root. The derivative will go to infinity (resp. negative infinity) as $x$ goes to infinity.

Therefore if you want to continue the drawing of this curve, you have to extend the rightmost part by making it more and more vertical. If you also extend your line, you will see that they will intersect.


Diffie-Hellman "handshake" vs RSA "handshake" I have a question about exchanging symmetric keys. I have read something about the Diffie-Hellman algorithm, where two parties generate the shared key independently, sharing only some parts of it before generation.

In general, I guess that I get the point of how this works, but wouldn't it be easier if the server requested a public RSA key from the client, encrypts the symmetric key using this public key, and sending it back to the client?

Hope you can help, and thanks in advance.

fre3zr

Using a client's RSA public key to encipher a session key generated by the server is possible, but has a several disadvantages:

If the client's RSA private key leaks in the future, past communication sessions can be deciphered; there is no forward secrecy, like there can be in some Diffie-Hellman variants. The only option to get that desirable property would be to use a new RSA key pair for each exchange, but then

the server has no way to verify the public RSA key generated by the client, thus the protocol might become vulnerable to a man-in-the-middle, unless the client also has a long-term key to sign it's one-session RSA public key.
as pointed in that other answer, it requires generation of an RSA key on the client side for each session, and that is typically quite slow.

The client does not participate in the generation of the session key, thus might be vulnerable to replay, and rightly less confident in the session key (one generator more easily becomes stuck or low-entropy than the combination of two generators implemented by two parties).
RSA decryption on the client side is significantly more compute-intensive than the whole Diffie-Hellman exchange needs to be (same for the signature of the RSA public key needed for forward secrecy, if that signature is RSA-based). That's true if DH is performed on a group $\mathbb Z_p$ (notice that the modulus is of the same order of magnitude in RSA and DH for comparable security, but the decryption exponent in RSA has about as many bits as the modulus, when it can be much shorter in DH; we are talking e.g. 2048 versus 256 bits, and commensurate performance gap; use of RSA CRT does not fully offset that); the difference in performance can be even larger if we use an elliptic-curve group for DH.


The Encode algorithm of Garbling scheme is probabilistic or deterministic? In general the garbling scheme works as follows:

$\textrm{Garb}(1^\lambda, C)$: on input the security parameter $\lambda$ in unary and the circuit $C$, it outputs a garbled circuit $\widehat{C}$ and a garbling key $K$
$\textrm{Encode}(x, K)$: on input the input value $x$ and the garbling key $K$, it outputs a garbled input $\widehat{x}$
$\textrm{Eval}(\widehat{C}, \widehat{x})$ outputs the result of $C(x)$

My question is whether the second algorithm "Encode" is probabilistic or not? I reviewed some papers and most of them indicate it is deterministic, but some of them think it is probabilistic. I'm currently in confusion about this, please give your best illustration why it is probabilistic or deterministic?

I don't know of any Yao-type garbling scheme where Encode is probabilistic. Think about Yao circuits - the encoding is providing the garbled key on the input wire for the associated bit. Note that the garbling is of course probabilistic and must be. However, once the garbling is fixed, the encoding is typically deterministic.

Having said the above, as a way of defining things, it is better to define it as probabilistic. This is due to the fact that although we don't know of any probabilistic way now, it doesn't mean that in the future there won't be. Since any deterministic algorithm is also (vacuously) probabilistic, this is more general.

This can also explain the confusion. As a definition, probabilistic is more general and thus preferable. But, in practice, Yao garbling using deterministic encodings until now.


ElGamal encryption security Assume we have 2 prime numbers in form p = 2q + 1.
Is it safe to use the cyclic group of order p-1 instead of one with order q in ElGamal encryption? I couldn't find any suitable source to explain why we should use q as order of our group and avoid p-1.
Most websites and sources just say:

use cyclic group of order q

without any explanation.
What have I tried?
I assumed p = 11 and therefore q = 5. I did all calculations of ElGamal-Encryption by considering 10 as my group order($Z_{p}^{*}$):

Group(G) = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Group Order(q): 10
*Generator(g): 7
Message(m): 9

and there was no problem in decrypting the message. So I think there is something wrong with its security!
I thinks there is no need to mention the calculations using q = 10 But if you need them, just comment below the question to bring them into the question as an update.

The answer to your question can be found in the paper Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh et al. It is an easy paper to read and worthwhile going through the details there.


Does this guarantee a unique 32 bit Hash? I came across some source code that loosely does the below in order to achieve a 32 bit hash.

The input string is passed through MD5 to get 16 bytes Hash (as usual). Then the 16 bytes are split into 4 byte words . Each of these words are $\oplus$ with each other in order to get a final 4 byte word, this is considered as a 32 bit hash.

The application does not really care about security in sense of pre-image resistance etc. but all it wants is Collision Resistance.

So, does the above guarantee no collisions (any better than birthday-bound)? Of course it depends on the input string's entropy etc., but given that we don't know before hand what possible strings could be passed as input: how do we analyze such scheme for collisions?

As far as I understand, the scheme is:

$$MD5(x) = a_1||a_2||a_3||a_4 \, \, \Longrightarrow \, \, H(x) = a_1 \oplus a_2 \oplus a_3 \oplus a_4,$$

with $a_i$ 4-byte/32-bit words.

Obviously you can't guarantee a unique 32-bit hash from an unbounded domain, due to the pidgeonhole principle. Neither can you make finding collisions infeasible, since $2^{16}$ MD5 invocations takes a few seconds if that.

If MD5 was an ideal 128-bit hash, it wouldn't matter whether you take the first 4 bytes, XOR the 32-bit words or anything else. All of them would be ideal 32-bit hashes. However, it isn't and you can find collisions in about $2^{33}$ operations. That doesn't directly lead to an attack on this, because it's slower than brute force, but it's possible it could be extended. There's a chance the XOR could make such an attack slightly harder or easier than truncation, but it really doesn't matter with a 32-bit hash since brute force is sufficient.

Assuming you don't let an attacker control the inputs (since that would be totally broken), the question isn't about the collision resistance, but pseudorandomness of MD5. MD5 is still thought to behave like a PRF in the sense that if the input strings are chosen "randomly", the output is uniformly random as well. (Which is why HMAC-MD5 is secure.) XOR doesn't affect that, so you should have the 32-bit hash behave like a PRF as well.

So, with inputs that aren't under the attacker's control, you should see collisions at the birthday bound. No sooner or later, other than what variance you expect with a 32-bit hash. However, there's no real benefit to the XOR, so you might as well just use the first 4-byte word.


Is RSA vulnerable to the padding oracle attack? I know that AES in combination with CBC mode is vulnerable against the Padding Oracle Attack. RSA also uses some kind of padding, hence can this attack be apply to RSA encrypted messages too?

Yes, and it's devastatingly effective, too. See OAEP and other RSA/asymmetric-function padding standards. OAEP is what you should use these days so far as I am aware. PKCS#1 has other defined padding schemes also (eg PSS, PKCS1.5), only some of which are effective.


Using crypto_sign then crypto_box_seal for anonymous messages If you have a message M and you want the sender (alice) to be anonymous to everyone but the recipient (bob), is it ok to do?
crypto_box_seal(crypto_sign(M, alice), bob)

(Alice signs message, then box seals to bob.)
This answer suggests crypto_box_seal then crypto_sign, am wondering if the opposite ordering is ok.
Thanks!

No, it is not!.
If you signed a message to someone before then they can use this to send an anonymous message to Bob and Bob may consider that it is coming from Alice.
The solution is easy, use crypto_box (Authenticated encryption of the NaCl) to produce a message and send it with crypto_box_seal.
$$\text{crypto_box_seal}(\text{crypto_box}(m)).$$ Here we are using short form of the boxes, no details.
The outer layer provides anonymity for all, the inner layer provides the identity. Since only Bob can reveal the crypto_box_seal, then only Bob can reveal the crypto_box and will understand the message is coming from who; Alice.
Note that Bob may not be aware that there is a crypto_box in the crypto_box_seal, put an additional message in the crypto_box` for indication.
$$\text{crypto_box_seal}(\text{After the columns there is a crypto box:}||\text{crypto_box}(m))$$


What does the term "differential" in "differential privacy" mean? I'm new in Differential Privacy (DP) and I have two questions:

Why do we have the term differential in differential privacy?
Are The local and global differential privacy and global and local sensitivity referring to different concepts?

The term "differential" was proposed by Mike Schroeder, to characterize the guarantee as being a relationship between distributions with and without any input record. At the time most papers simply defined "(x,y,z)-privacy as ..." and the work felt of a sufficiently different character (both weaker and stronger than prior work) to call out the distinction.

Other adjectives that were discarded were "incremental privacy" and "marginal privacy", for retrospectively obvious reasons.

The name stuck in part due to the analogy to differential cryptanalysis.
Yes, per Ted's answer, which is exactly correct.


RSA with modulus n=p²q I've been wondering what would happen if the RSA modulus would be $n=p^2q$ instead of $n=pq$. I feel like there is an obvious security flaw (as there is with most modifications). Would this choise of $n$ make RSA less secure? If so, why? If not, then why isn't $n=p^2q$ standard since it allows operations on a bigger $\mathbb{Z}_n$? Btw, I'm talking about textbook RSA here.

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations.  However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes $p$, $q$ and $r$.

As for the security, well, reducing the size of the primes does make factoring methods such as ECM easier.  However, with the current state of the art, it would appear that ECM against a product of three 682-bit primes (whether two of the primes were duplicated or not) would be harder than doing NFS (which doesn't care how big the primes were); however it's still enough to make people uneasy.

If you are really interested in performance, you probably should look at Elliptic Curve systems anyways...


Shortest key in symmetric algorithm used only once is unsecured? Considering a message of n bits, one ridiculously short key of 1 bit and using this cryptographic function which performs the XOR operation to each bit of the message, resulting in a single ciphertext, could we assume that if the attacker doesn't know anything but this ciphertext, that this system is anywhere close to being safe?

If we don't know anything about the original n bit message, we can guess the message with probability $1/2^n$ which for anything but very small values of n quickly becomes zero.
However if we xor the message with a single bit (repeating it n times) we only have 2 possible keys: 1 and 0. And the xor result is either the original message or it's negation. Therefor given a cipher text we have exactly two possibilities for plain text. And even if we know nothing about the plain text and can't validate our guess we can still guess with 50% chance of success.

Guessing the plain-text with 50% likelyhood is not secure by any means.

Obviously even with a very limited understanding of plain text, we would be able to determine which of the 2 options is correct.

Note security proofs for One-Time-Pad do not apply as we are repeating the key in the same message. This is no better than repeating it in later messages.


Are there any high level memory-hard PBKDF constructions? The PBKDF2 construction from PKCS #5 v2 has the convenient feature that it can be implemented using only standard interchangeable cryptographic primitives.  Specifically, it only requires the availability of a suitable PRF, typically implemented using a standard cryptographic hash function via HMAC (another high level crypto construction).  Thus, PBKDF2 can be easily implemented on top of any crypto library that provides access to a suitable hash function, even if the library does not directly implement PBKDF2 (or even HMAC) itself.
However, while PBKDF2 implements an adjustable work factor (in the form of an iteration count) to thwart brute-force password cracking attempts, it uses only a fairly small amount of memory.  This leaves it vulnerable to attacks using parallel computing hardware such as GPUs, FPGAs or dedicated ASICs.
In recent years, several "memory-hard" password-based key derivation functions, such as scrypt and Argon2, have been developed to address this issue.  These functions, however, all tend to use specific non-standard primitives that are not (yet) implemented by many crypto libraries, and which would be hard if not impossible to implement securely and efficiently from scratch in a high-level programming language.
Thus, my question would be: Are there any memory-hard PBKDF constructions that can be implemented using only common standard crypto primitives, like (generic) hash functions and/or block ciphers?
Ideally, the security of the construction should be easily reducible to reasonable security assumptions on the underlying primitives.  I do suspect that for some aspects (particularly, the memory-hardness) this reduction may be non-trivial, but hopefully still provable.
Also, to be well suited for implementation in high-level languages, the construction should ideally be implementable using only a relatively small number of high-level calls to the underlying crypto library.  For example, a construction based on a block cipher should ideally spend most of its time running the cipher on bulk data in a widely implemented mode of operation like (bulk) ECB or CBC, instead of requiring repeated high-level calls to encrypt individual blocks.  Similarly, for hash-based constructions, it would be ideal for most of the hash invocations to be on fairly long input strings.  (Note that PBKDF2-HMAC fails this additional requirement, invoking the hash repeatedly on short strings.)

Ps. This earlier question is a good example of the kind of use case for which such a construction would be useful for:

"I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt).
My current key derivation is simply an iteration of HMAC (password + salt). But it seems that using AES or other encryption ciphers, one could construct a fairly simple, memory-hard key derivation function using build-in PHP capabilities such as HMAC and AES encryption (assuming PHP is compiled with openssl support)."

Alas, their proposed construction does not actually seem to be memory-hard.  I've been thinking about possible alternative constructions to achieve the same goal, but before investing a lot of time and effort on analyzing their security and memory-hardness, I thought I'd first ask whether this is already a solved problem.

Are there any memory-hard PBKDF constructions that can be implemented
  using only common standard crypto primitives, like (generic) hash
  functions and/or block ciphers?

Of course there is one, and it even got a "special recognition" at PHC:
Catena.

I won't go into the details of Catena here (the paper does it much better on its 50+ pages), but it comes with pebble-game-based security reductions, rigorous security proofs, default instances and a alot of customizable parameters (namely four):

It uses a cryptographic primitive, the paper suggests Blake2b, but really any hash will do, which you can compute quickly
It uses a round-reduced cryptographic primitive, although a full-rounded version will also work
It takes an optional randomziation layer, to harden memory initialization
It takes some "memory-hard" function

Finally it uses all these parameters and a clever graph driven data flow to achieve basically all desirable properties being expected from a modern password hash.

Note: Default parameters for the latter two choices are provided, so that the user basically has the choice between two Catena variants based on their favorite hash.