Timing vulnerability of byte array equality test? Would the following code to test MAC equality leak timing information ?

bool equal(unsigned char *a, unsigned char *b, int len) {
    unsigned char c = 0;
    for (int i = 0; i < len; i++) {
        c |= a[i] ^ b[i];
    }
    return c == 0;
}

More precisely, does the last expression c == 0leak timing
information ?

I don't think so, because it doesn't allow to know where would be the mismatch.

Why are then some crypto libraries using complex expression to convert c into a 1 or 0 value than later simply compare that value with a simple == with 1 (or 0) ?

Would a timing difference between MAC mismatch and identical MAC condition be relevant ?

The comparison c == 0, like the rest of your code, will probably run in constant time.

However, there's no guarantee that it will, and it's just barely conceivable that there might be some compiler and CPU combination out there where it might not.  Of course, that's basically true of any code not written in assembly for a specific CPU model and version.

After all, the C language standard does not actually offer any guarantees about execution times, and it would be perfectly valid for a smart enough compiler to look at your code, go "Hey! It looks like you're trying to compare two byte arrays for equality!" and decide to replace your code with a call to memcmp() or something equivalent.  And, as you can see from the results below, modern compilers actually are getting close to that level of cleverness, if they're not quite there yet.

Indeed, I suspect that the real reason why your code isn't getting optimized away like that is because compiler authors have more or less consciously decided not to make their compilers recognize it as a memory comparison, on the assumption that if you're writing your comparison code in such a convoluted way, you're probably doing something unusual and don't want it replaced by memcmp().

You can take a look at how common compilers translate your code into assembly using the Godbolt Compiler Explorer.  It turns out that, even on the same CPU architecture, the result depends a lot on the compiler and the optimization level chosen.

(I've included a fairly long discussion of the x86-64 assembly produced by various compilers below, since it's kind of interesting in itself, but it's really only relevant as an illustration of how much the compiler output varies.  Feel free to skip it.)

As a fairly typical example, when told to optimize your code for minimum size (-Os), GCC 7.2 generates a rather nice and simple piece of assembly code:

equal(unsigned char*, unsigned char*, int):
  xor eax, eax
  xor ecx, ecx
.L3:
  cmp edx, eax
  jle .L2
  mov r8b, BYTE PTR [rdi+rax]
  xor r8b, BYTE PTR [rsi+rax]
  inc rax
  or ecx, r8d
  jmp .L3
.L2:
  test cl, cl
  sete al
  ret

The last three lines of assembly correspond to your return (c == 0) statement, and indeed that part of the output seems to look pretty much the same (modulo register choices) for all compilers (for the x86-64 platform, that is) and optimization levels.  I would indeed expect it to run in constant time, assuming that the timing of test isn't data-dependent, which it really shouldn't be.

(At worst, if it wasn't constant-time on some CPU architecture, I'd expect the most likely timing differences to most likely be between the cases c == 0 and c != 0, which the code reveals through its return value anyway.  Of course, if you don't want that return value leaked through timings, e.g. because it's used as just one input to a more complex condition whose individual inputs should be secret, then even that leak could be too much.)

Of course, what typical timing attacks target isn't the final byte test, but the comparison loop itself.  And that's where the compiler differences really come in.  For example, at optimization level 1 or level 2, GCC's output looks quite similar to the code above.  (The main difference is that the loop condition test is moved to the end and an explicit test for len <= 0 is inserted at the top of the code instead.)  At optimization level 3, however, something weird happens and the output turns into this unrolled monstrosity:

equal(unsigned char*, unsigned char*, int):
  test edx, edx
  jle .L9
  mov rcx, rdi
  lea r8d, [rdx-1]
  mov r9d, 17
  neg rcx
  push rbp
  push rbx
  and ecx, 15
  lea eax, [rcx+15]
  cmp eax, 17
  cmovb eax, r9d
  cmp r8d, eax
  jb .L10
  test ecx, ecx
  je .L11
  movzx r8d, BYTE PTR [rdi]
  movzx r10d, BYTE PTR [rsi]
  xor r10d, r8d
  cmp ecx, 1
  je .L12
  movzx eax, BYTE PTR [rdi+1]
  xor al, BYTE PTR [rsi+1]
  or r10d, eax
  cmp ecx, 2
  je .L13
  movzx eax, BYTE PTR [rdi+2]
  xor al, BYTE PTR [rsi+2]
  or r10d, eax
  cmp ecx, 3
  je .L14
  movzx eax, BYTE PTR [rdi+3]
  xor al, BYTE PTR [rsi+3]
  or r10d, eax
  cmp ecx, 4
  je .L15
  movzx eax, BYTE PTR [rdi+4]
  xor al, BYTE PTR [rsi+4]
  or r10d, eax
  cmp ecx, 5
  je .L16
  movzx eax, BYTE PTR [rdi+5]
  xor al, BYTE PTR [rsi+5]
  or r10d, eax
  cmp ecx, 6
  je .L17
  movzx eax, BYTE PTR [rdi+6]
  xor al, BYTE PTR [rsi+6]
  or r10d, eax
  cmp ecx, 7
  je .L18
  movzx eax, BYTE PTR [rdi+7]
  xor al, BYTE PTR [rsi+7]
  or r10d, eax
  cmp ecx, 8
  je .L19
  movzx eax, BYTE PTR [rdi+8]
  xor al, BYTE PTR [rsi+8]
  or r10d, eax
  cmp ecx, 9
  je .L20
  movzx eax, BYTE PTR [rdi+9]
  xor al, BYTE PTR [rsi+9]
  or r10d, eax
  cmp ecx, 10
  je .L21
  movzx eax, BYTE PTR [rdi+10]
  xor al, BYTE PTR [rsi+10]
  or r10d, eax
  cmp ecx, 11
  je .L22
  movzx eax, BYTE PTR [rdi+11]
  xor al, BYTE PTR [rsi+11]
  or r10d, eax
  cmp ecx, 12
  je .L23
  movzx eax, BYTE PTR [rdi+12]
  xor al, BYTE PTR [rsi+12]
  or r10d, eax
  cmp ecx, 13
  je .L24
  movzx eax, BYTE PTR [rdi+13]
  xor al, BYTE PTR [rsi+13]
  or r10d, eax
  cmp ecx, 14
  je .L25
  movzx eax, BYTE PTR [rsi+14]
  xor al, BYTE PTR [rdi+14]
  or r10d, eax
  mov eax, 15
.L4:
  mov ebp, edx
  pxor xmm1, xmm1
  sub ebp, ecx
  mov r8d, ecx
  xor r9d, r9d
  mov ebx, ebp
  lea r11, [rdi+r8]
  xor ecx, ecx
  shr ebx, 4
  add r8, rsi
.L6:
  movdqu xmm0, XMMWORD PTR [r8+rcx]
  add r9d, 1
  pxor xmm0, XMMWORD PTR [r11+rcx]
  add rcx, 16
  cmp ebx, r9d
  por xmm1, xmm0
  ja .L6
  movdqa xmm0, xmm1
  mov ecx, ebp
  and ecx, -16
  psrldq xmm0, 8
  por xmm1, xmm0
  add eax, ecx
  movdqa xmm0, xmm1
  psrldq xmm0, 4
  por xmm1, xmm0
  movdqa xmm0, xmm1
  psrldq xmm0, 2
  por xmm1, xmm0
  movdqa xmm0, xmm1
  psrldq xmm0, 1
  por xmm1, xmm0
  movaps XMMWORD PTR [rsp-40], xmm1
  movzx r8d, BYTE PTR [rsp-40]
  or r8d, r10d
  cmp ebp, ecx
  je .L7
.L3:
  cdqe
.L8:
  movzx ecx, BYTE PTR [rdi+rax]
  xor cl, BYTE PTR [rsi+rax]
  add rax, 1
  or r8d, ecx
  cmp edx, eax
  jg .L8
.L7:
  test r8b, r8b
  sete al
  pop rbx
  pop rbp
  ret
.L14:
  mov eax, 3
  jmp .L4
.L9:
  mov eax, 1
  ret
.L12:
  mov eax, 1
  jmp .L4
.L13:
  mov eax, 2
  jmp .L4
.L10:
  xor eax, eax
  xor r8d, r8d
  jmp .L3
.L15:
  mov eax, 4
  jmp .L4
.L16:
  mov eax, 5
  jmp .L4
.L19:
  mov eax, 8
  jmp .L4
.L17:
  mov eax, 6
  jmp .L4
.L11:
  xor eax, eax
  xor r10d, r10d
  jmp .L4
.L18:
  mov eax, 7
  jmp .L4
.L20:
  mov eax, 9
  jmp .L4
.L21:
  mov eax, 10
  jmp .L4
.L22:
  mov eax, 11
  jmp .L4
.L23:
  mov eax, 12
  jmp .L4
.L24:
  mov eax, 13
  jmp .L4
.L25:
  mov eax, 14
  jmp .L4

It looks like GCC has vectorized the XOR/OR loop to process 16 bytes at a time using SSE instructions, with a bunch of additional special case code to handle the possibility that len might not be a multiple of 16.  At a glance, I suspect this may still run in constant time (for any given len value), but I wouldn't be more than pocket change on it.

FWIW, replacing the len parameter with the constant 16 gets rid of all the special-case handling and yields this very elegant assembly code with no jumps or loops whatsoever.  Literally translated back into C / C++, what it basically does is:

bool equal(unsigned char *a, unsigned char *b) {
    uint128_t c = *(uint128_t *)a ^ *(uint128_t *)b;
    c |= (c >> 64);
    c |= (c >> 32);
    c |= (c >> 16);
    c |= (c >>  8);
    return (unsigned char)c == 0;
}

As for other compilers, Clang's output looks pretty similar to GCC's at low optimization levels, but at -O2 and above, things get even weirder than with GCC.  Again, that's clearly vectorized with SSE, but (if I'm parsing the code correctly) it's only reading the input 4 bytes at a time and doing some really weird within-register byte shuffling.

The core loop of ICC's output at -O3 looks similarly vectorized as GCC's, although the rest of the code is quite different.  FWIW, if you fix the length at 16 bytes, ICC doesn't vectorize the code at all, although it does unroll it.  Also, ICC at -O2 and above is the only x86-64 compiler I found that doesn't use the test + sete combo for the final c == 0 test; it uses test + cmove instead:

  mov edx, 1
  test al, al
  mov eax, 0
  cmove eax, edx

Anyway, in practice, the only way to be really confident that your code runs in constant time is to (first examine the assembly output for any telltale signs of potential timing issues, and then) test it.

For example, here's a quick and dirty online benchmark showing that (at least for the specific platform, compiler, options and parameters used) your code does seem to be constant-time:

The first two tests (AllDifferent and AllSame) are general baseline timing tests, the next two (FirstHalfSame and LastHalfSame) exercise the comparison loop to see if its execution time depends on the length of the matching prefix / suffix, and the last two (CaseFlipped and LSBFlipped) exercise the final c == 0 test by comparing two strings which differ only by having a specific bit in each byte flipped.

Of course, in practice, you should carry out your benchmark using the specific compiler and hardware you're targeting (or as wide a selection of both as possible, if you don't have a specific target) and using realistic inputs (e.g. not just constant strings) to reduce the chance of compiler optimizations messing up your benchmarks.

(For example, while making the quick benchmark above, I noticed that assigning the output of the comparison to a global variable was necessary to stop the compiler from optimizing out all the comparisons entirely(!) and making them all run at same speed as the "Noop" baseline loop.  Also, in the AllSame test, I found that Clang is in fact smart enough to optimize out the comparison if both inputs point to the same address, so I had to use two separate strings with the same content to properly test it.  Benchmarks can be tricky like that.)


Is this Diffie-Hellman key exchange variant vulnerable to man-in-the-middle attacks? As we all know, the Diffie-Hellman key exchange protocol without authentication is vulnerable to a man-in-the-middle attack. And if we use STS(Station-to-Station protocol) instead, it would be secure.

My question is:
Suppose we use a variant of Diffie-Hellman key exchange protocol with signatures like this:

Alice $\rightarrow$ Bob : $Bx = g^{Ax} ,S_a(Bx)$
Alice $\leftarrow$  Bob : $By = g^{Ay} ,S_b(By)$

Then they have a shared key $g^{(Ax\ \times\ Ay)}$.

It's like STS but not the same.

So is it secure against man-in-the-middle attack?
Suppose Eve is an active man-in-the-middle, will Eve be able to decrypt Alice's or Bob's message later on? (Suppose Alice and Bob won't send Ax,Ay in this channel)

It is secure against private key exposure but not against replay attacks by Eve. A three-way protocol avoids this, and doesn't need to use timestamps. The description below is from Delfs and Knebl's book Introduction to Cryptography.

  Each user, say Alice, has a key pair
  $(e_A, d_A)$ for encryption and another key pair $(s_A, v_A)$ for digital signatures.

  It is assumed that everyone has access to Alice’s authentic public keys, $e_A$
  and $v_A$, for encryption and the verification of signatures. Define the signature algorithm as the pair $Sign(),Verify(),$ the encryption algorithm is DH, using public key $e_A$, e.g.

  Alice chooses $r_A$ at random, sets $t_1 := (B, r_A)$ (where $B$ represents
  Bob’s identity), $s_1 := Sign_{s_A}(t_1)$
  and sends $(t_1, s_1)$ to Bob.
  Bob verifies Alice’s signature, checks that he is the intended
  recipient, chooses $r_B$ and a session key $k$ at random, encrypts
  the session key with Alice’s public key, $c := E_{e_A}(k)$, sets $t_2 :=
(A, r_A, r_B, c)$, signs $t_2$ to get $s_2 := Sign_{s_B}(t_2)$ and
  sends $(t_2, s_2)$ to Alice.
  Alice verifies Bobs signature, checks that she is the intended recipient
  and that the $r_A$ she received matches the $r_A$ from step 1
  (this prevents replay attacks). If both verifications pass, she is
  convinced that her communication partner is Bob. Now Alice decrypts
  the session key $k$, sets $t_3 := (B, r_B)$, $s_3 := Sign_{s_A}(t_3)$ and
  sends $(t_3, s_3)$ to Bob.
  Bob verifies Alice’s signature and checks that the $r_B$ he received
  matches the $r_B$ from step 2 (this again prevents replay attacks).
  If both verifications pass, Bob and Alice use $k$ as the session key.


average-case SIS and average-case BDD In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem
                     " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a vector $s\in \mathbb{Z}^{m}_{q} \backslash \{0\}$ such that $As=0$ and $||s||\leq \beta$"

but not  instances like this
       " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a matirx $B\in \mathbb{Z}^{m\times k}_{q} \backslash \{0\}$ such that $AB=C$ and $||B||\leq \beta$".
The latter instances are more general and the former instances just include some cases of the latter.

And the same case happens in BDD (bounded-distance decoding) problem.  We say that LWE problem is an average-case problem because it just includes some cases of BDD problem.

Did I understand that correctly?

If you want, one can define a "general SIS problem", with parameters $(n,m,q, \beta)$, as follows: I give you a matrix $A\in\mathbb{Z}_q^{n\times m}$, and you must find a nonzero vector $\vec x \in \mathbb{Z}_q^m$ such that $||\vec x|| \leq \beta$ and $A\cdot \vec x = \vec 0$.

The matrix $A$ specifies an instance of this general SIS problem. You get different variants of the problem by defining how the instance $A$ is chosen. What average-case hardness of SIS means is just that it is assumed to be hard to find (with good probability) a solution to the problem above when the instance is chosen randomly from some distribution of instances. This is in contrast to worst-case hardness, which would be the (much weaker) assumption that the problem is hard to solve for some instance $A$.

Now, when we talk about the SIS problem, by default this refers to the conjectured average-case hardness of the problem I described above, where the distribution over instances is the uniform distribution over $\mathbb{Z}_q^{n\times m}$. You can view this if you like as a special case of a more general family of SIS-problems, where one could consider both average-case hardness for different distributions over instances, or worst-case hardness.

However, the terminology "average-case" has nothing to do with the fact that SIS can be seen as a special case of a more general problem where one attempts to find a small-norm matrix $B$ such that $AB=C$ instead of a small-norm vector $\vec x$ such that $A\vec x = 0$. Note that the first one is also well known (it asks about solving several instances of the inhomogenous SIS problem) and indeed more general if we define $k$ and $C$ to be parameters of the system. But this has nothing to do with the terminology average-case - in fact, you could equivalently discuss average-case hardness and worst-case hardness for the more general problem which you consider as well. And the same goes for BDD and LWE.


Self authenticating tamper resistant first meetings I'm not sure what the precise words I am looking for are so I apologize if there is a better way to phrase this. What I am thinking of is ways to transfer an identity in a way that it is tamper resistant and can be used for authentication.

Normally to know who someone is people use driver licenses or a person's face. In cryptographic terms this would be similar to your public key. You can use this to sign and encrypt messages validating you are who you say you are just like when someone speaks and you here it come from the person's mouth. You know who they are by their face.

If you send a public key over a unsecured network it has the chance to be modified in such cases as using Diffie-Hellman key exchange. Your communications are secure but not authenticated.

One solution to this is such things used by PGP a network of trust where people would sign your key after seeing your photo id or knowing you by being your friend etc. They vouch for your identity by seeing those things that prove who you are.

Would it be possible to digitize this by transferring video of a person with a QR code representation of your key? Such as a video chat the other person can see your face and your public key. The attacks on this would be man in the middle but even then you would either have to modify the video stream or create a fake of the video with your own QR code.

Is there any other holes in this (obviously if you don't have a webcam it won't work) that I am not seeing? Is there a way to mitigate modifying the QR code in a better way (obviously this would be a very specific attack but unless you can somehow make it time sensitive or somehow make it so it can't be changed*)?

Edit

Some other thoughts, in stead of a QR code (which people may not have access to a printer and you don't want to just transmit the screen or a picture of it digitally as that could easily be replaced) maybe a hash of the public key, though it does have the down side of being 160 characters for sha1 so it is long.

PGP uses a web of trust this could also happen you already know many people who most likely know people you know. You could confirm that in fact it is them (to a certain degree) by other people you both know.

While video could be altered (again highly unlikely but I don't think it would be hard, tedious yes) voice would have another issue to be faked (though this being the start of the connection may not be of benefit as they could queue up it, though it would be odd as video messaging wouldn't be synced, and somehow use audio to piece it together).

All these things take time to alter and attack, sense it is streaming it would seem resistant in that a video message naturally needs to be in sync and not delayed, if there is a long delay that could potentially be an issue. However (though I am not sure how feasible this is), computer automation could speed up tampering**.

Another though was some kind of shared secret but I think this would be weak because either it is rather public (where did we sit at the xyz game last week) or if secret enough why not just give each other your QR code...

* However any method of signing the video wouldn't work because you would just change the key as well... maybe encrypting it with the other person's public key but that still would be weak against a man in the middle attack wouldn't it?

** Computer automation is obviously rather unlikely but it could be possible for a QR code as it is meant to be computer readable, less likely for a string written on paper or voice information (as far as I am aware of).

I wouldn't consider voice or video to remain a secure means of identification for much longer.  Advances in real-time video stream editing are near enough to reality that I wouldn't build a new security system on it.

In the olden times in millennia past, you could have the computers on either end display a short MAC for both parties to alternate reading aloud one letter at a time to each other (quickly), and the lack of delay plus the sound of your partner's voice was a pretty good assurance that you weren't being MITM'ed.  But today, the technology available to a sophisticated attacker could render even that approach untrustworthy.

If you are really that paranoid, you need to physically and privately exchange some other kind of okay/duress signal, such as a specific word or phrase; right leg crossed over left; carnation or rose on the table facing right or left; cigarette or other object in the left or right hand; book face down or face up, or any of a thousand other cheesy spy tradecraft signals.  But sometimes the old standbys can't be beat.


How can i check if a public key match with a private key Is there a way to check, (with openssl command for example), if a given public key match with a private key ?

Thanks

One method works with any signature scheme and any program including OpenSSL: make a signature of a file with the private key, and check signature and file against the public key.

If the check is OK, then private and public key match (or the signature scheme is broken).

If there is some failure, then private and public key do not match (or the program is misused, incomptible with the key formats, or broken).

Example with openssl, showing Verified OK for matched private/public keys tstpri.pem/tstpub.pem; Verification Failure for unmatched keys altpri.pem/tstpub.pem.

# generate an secp256k1 private key
openssl ecparam -genkey -noout -name secp256k1 -out tstpri.pem
# extract the public key
openssl ec -in tstpri.pem -pubout -out tstpub.pem >/dev/null
# generate an alternate secp256k1 private key
openssl ecparam -genkey -noout -name secp256k1 -out altpri.pem

# create a file fil (any content will do)
echo foo >fil

# sign fil with private key
openssl dgst -sha256 -sign tstpri.pem -out tst.sig fil
# verify the signature with matching public key
openssl dgst -sha256 -verify tstpub.pem -signature tst.sig fil
Verified OK

# sign fil with alternate private key
openssl dgst -sha256 -sign altpri.pem -out tst.sig fil
# verify the signature with non-matching public key
openssl dgst -sha256 -verify tstpub.pem -signature tst.sig fil
Verification Failure


How to increment the counter value for CTR mode? I am testing CTR mode on STM32 board. I want to know how the auto increment of counter happens and what is the method to follow if I have to increment the counter manually.

Basically there are two ways:

decode the counter to be a big number in some kind of library, increase that number, then encode it back as unsigned, statically sized, big endian value, making sure you left pad with zero valued bytes when necessary;
increase the value of the right-most byte (highest index) as unsigned number, if the resulting value is zero then increase the value of the byte before that, up to the leftmost byte if required (i.e. use a bit of awkward carry-bit detection).

Probably 2 is easier and less error prone; you'd just need a single loop construct, one expression to increase the byte value and an if statement to detect the carry by comparing to 00 afterwards.


DES-encrypted cipher Suppose that you knew that a plaintext was encrypted with DES and consisted only of 16-bit Unicode letters, numerals, and punctuation marks available on a standard English-language QWERTY keyboard.  How could you use this knowledge to attack the DES-encrypted cipher?

Pure, raw DES has a key length of 56 bits, which makes it trivially vulnerable to a brute-force attack. Just try all $2^{56}$ possible keys to decrypt the message and stop when you find an English message. On average, this will happen after $2^{55}$ trial decryptions. See the Brute Force Attack section on the DES Wikipedia page for more information on how this has been done historically.

Detection of English text can be automated in several different ways, mostly using metrics that have been computed for large English corpora. Examples are the index of coincidence, letter frequency, and (more generally) n-gram frequency. Counting the number of spaces in the putative plaintext also works surprisingly well; textual documents tend to have quite a few of them.

Attacks under this model are called known-plaintext attacks. Secure ciphers are not vulnerable to known-plaintext attacks: if you replace DES with 3DES, AES, Salsa20, ... in your question, then the answer is "there is no known attack." But DES's key length is short enough to enable brute-force attacks. Note that the only attacks on DES faster than brute-force are not practical: they require an obscene amount of known (or even worse, chosen) plaintexts.


How "hard" it is to take an e'th root mod p? I know it's hard to find the $e$th root of a number mod $n=p_1*p_2$, and if it would be possible we could break RSA. But how hard it is to take an $e$th root mod $p$ where $p$ is a prime and $\gcd(e,p-1)=1$?

It is  very easy.
$gcd(e,p-1)=1$ so there exist $k,t$ where $ek+t(p-1)=1$. Let $x$ be the $e$-th root of $y$, so $x^e=y \bmod p$.

$y^k=x^{ek}=x\cdot {(x^{p-1})}^{-t}=x \bmod p$.

Also in decryption of RSA we use this method.


Exactly what RNG weaknesses endanger (EC)DSA? RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction

  One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process.  Even slight biases in that process may be turned into attacks on the signature schemes.

How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?

It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}\cdot(H(m_1)+x\cdot r) \bmod q$ and $s_2=k^{-1}\cdot(H(m_2)+x\cdot r) \bmod q$. Computing $d = \frac{s_1}{s_2} \bmod q$ one obtains $d = \frac{H(m_1) + r\cdot x}{H(m_2) + r\cdot x} \bmod q$, and so $(d-1)\cdot r \cdot x = H(m_1) - d \cdot H(m_2)$ yielding $x = \frac{H(m_1)-d\cdot H(m_2)}{(d-1)\cdot r} \bmod q$.

One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.

The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.


Will there always be 256 collisions for the output of the MD5 hashsum function for 17-byte inputs? By my math, if you are inputting all possible 17 byte values, and the output is 16 bytes long, then there must always be 256 possible inputs that will result in each output hashsum. However, looking at some rainbow tables, it seems that either this isn't the case, or (more likely) the rainbow tables were incomplete. But, some of the other research I've done says that the smallest known MD5 collision happens well beyond 17 bytes in length.

How can this be possible?

Your math is wrong — not the numerical calculation, but your interpretation of it. There are $256^{17}$ possible inputs and $256^{16}$ possible outputs. On average, there are $256$ inputs for each output. But there are no guarantees that this is the case for all outputs: it's in fact overwhelmingly likely that some outputs have more and others have fewer. For example, we don't even know whether every possible output is in fact the MD5 of a message of any length.

What you can state for sure is that there exists at least one 256-bit string $H$ such that there are at least 256 17-byte messages $M_{1}, \ldots, M_{256}$ such that for all $i$, $\mathrm{MD5}(M_i) = H$. Since we don't know any MD5 collision with a 17-byte output, we are unable to come up with an actual value for $M_i$ or $H$, we just know that it exists by the pigeonhole principle.

See also

Is SHA-256 a one way permutation when restricting the domain to {0,1}^256?
Is it theoretically possible to construct a string that contains its own hash value?
What is the MD5 collision with the smallest input values?


Simplifying Meet-In-The-Middle Attacks Considering the fact that a block cipher is a bijective function on the set of possible plaintexts, if one views the encryption of a  datum with a key $K_2$, which has been already encrypted with the same n-bit block cipher, using key $K_1$ as a single n-bit mapping $\text{F(plaintext}, K)$, is not bruteforcing through $2^n$ keys not more efficient than performing a Meet-In-The-Middle Attack (or MD-MITM, as the case may be)?

This question asked for the DES years ago. To achieve this kind of attack you need to first show that the target encryption algorithm is closed under functional composition i.e. forming a group.

The easiest might be is showing that it is not forming a group as in DES.

Although you may get one $K$ for only one block with the negiligible probability it will work for the other blocks.

Actually, we don't expect such property exists for good block ciphers. The keys, as you remember, select one permutation from all possible permutation randomly. What you are asking is a very specific cipher which is not random.

In short, It is not expected!.


Using last 64 bit of aes as hash of the message vs first? If I Generate some key K for the AES algorithm. Encrypt a message M with key K and take the last 64 bits
of the result as the hash of M.

Would there be any disadvantages?
What if I took first 64 bits of the message rather than the last 64 bits?

Short answer: neither.

I'm going to assume the length of M is 128 bits (one AES block) so we won't be talking about block cipher modes.

A hash is useful to verify the integrity of the message. It is meant to be verifiable either without (plain hash) or with (MAC) a key. In your scenario, it is neither: only someone with the plaintext can compute the hash again (in which case: why encrypt?).

With your proposed solution (either first or last 64 bits), you cannot tell if the ciphertext or plaintext have been altered. The only way would be to decrypt the message and have some way of verifying the validity of the plaintext after decryption.

What you probably want is a message authentication code.


What is the difference between signatures and VRF? For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each message. So what is the difference?

First, you need more than just a signature, because a VRF produces both an output and a proof.  To an observer, the output is uniformly distributed unless the observer also has the proof, which can be used to verify the output.

With a signature scheme and a random oracle $H$, you could use a signature $s$ on a message $m$ as a proof and $h = H(s)$ as an output: then the output $h$ is uniformly distributed if you don't know the proof, but knowing the proof $s$ you can (a) verify that $s$ is a signature on $m$, and (b) verify that $h = H(s)$.

However, that's not enough, because signature schemes do not usually guarantee uniqueness of the signature.  ECDSA signatures are malleable: if $(x(R), s)$ is an ECDSA signature, then so is $(x(-R), -s) = (x(R), -s)$.  EdDSA signatures, of the form $(R, s)$ instead, hash $R$ together with the message so it can't be changed any more than the message can, but $(R, s + \ell)$ makes another valid signature if encodable, where $\ell$ is the order of the standard base point.

Further, ECDSA and EdDSA are built out of a non-interactive zero-knowledge proof protocol that is necessarily randomized, and the signer can choose any per-signature secret randomization they want without the verifier noticing.  Standard EdDSA prescribes a particular deterministic pseudorandomization so that the signer doesn't accidentally leak the private key when signing two different messages even if they don't have a source of entropy at signing time, but verifiers can't tell if a signer uses a nonstandard randomization.  Similarly, the widely deployed RSASSA-PSS signature scheme is randomized, so it doesn't provide uniqueness either.

That said, we can still use the RSA primitive to make a VRF if we pick a deterministic RSA signature scheme such as RSA-FDH with a fixed full-domain hash.  This is what the IETF Internet-Draft draft-goldbe-vrf, currently under discussion at the CFRG, does for RSA-FDH-VRF.

We can also adapt elliptic curve signatures such as EdDSA to make a VRF, with a little more work.  I won't go into the details, but draft-goldbe-vrf has one construction called EC-VRF, and Open Whisper Systems (creators of Signal) developed another called VXEdDSA.

Further reading:

VRFs were first introduced to the literature in Silvio Micali, Michael Rabin, and Salil Vadhan, ‘Verifiable Random Functions’, Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science, 1999.
VRFs were recently presented to the IETF for standardization, by Sharon Goldberg, Dimitrios Papadopoulos, and Jan Včelák, ‘draft-goldbe-vrf-01: Verifiable Random Functions (VRF)’, Presentation at CFRG@IETF'99, Prague, July 2017.
Sharon Goldberg's group at Boston University has an ongoing practical VRF project with some references.
Some details of the constructions, and an application to DNSSEC for verifiable negative responses thwarting zone enumeration, are analyzed in Dimitrios Papadopoulos, Duane Wessels, Shumon Huque, Moni Naor, Jan Včelák, Leonid Rezyin, and Sharon Goldberg, ‘Making NSEC5 Practical for DNSSEC’, IACR Cryptology ePrint Archive: Report 2017/099.
A dialogue in five parts summarizing a use case of VRFs for DNSSEC to authenticate negative answers without enabling zone enumeration or risking forgery in the face of online nameserver compromise.

P.S.  Fun fact: RSA signatures aren't uniformly distributed even if you don't know the public key.  Since every signature will involve an integer below the modulus $n$, with enough signatures one can solve the German tank problem to deanonymize signers in practice.  Of course, you could do rejection sampling to force them below $2^{\lfloor\lg n\rfloor}$.


Encrypt HDD with keyfile and password and allow backing up the keyfile with secret sharing I want to:

Encrypt my whole HDD with a keyfile and a password (meaning that both are required to decrypt it),
Be able to back up pieces of the keyfile in several distant locations using Secret Sharing,
Be able to change the password often and easily.

Notes:

The keyfile is made of 4096 random bits and is done using dd if=/dev/urandom /keys/keyfile bs=1024 count=4,
The password is approximately 20 characters long,

To make things clear, I'll state the intended meaning of a few words:

keyfile – the randomly generated file
password – the text asked to the user and never stored in a file
key – the data used to decrypt the masterkey
masterkey – the data used to encrypt / decrypt the drive

Thoughts:

To allow “3.”, I use cryptsetup since it uses a masterkey that's encrypted with your key so I can change my key without having to rencrypt everything. I could use dm-crypt directly but it'd be much harder and would only save the space occupied by the luks headers. And I already have enough space so I don't think it's worth the trouble.
To allow “1.”, I could encrypt the keyfile with the password and use the keyfile as key but then,

If I backed the encrypted version of the keyfile, I'd have to update all backups every time I changed the password,
If I backed the non-encrypted version of the keyfile, I'd allow to bypass the password by recovering the backup.

So instead, I chose to combine the keyfile and the password.

Combination of keyfile and password into key:

I use a bitwise XOR to compute the key from the keyfile and the password. I start at the left and when one of then is empty, I just output the rest of the other one. See my C source file at GitHub.

The other option I thought of was concatenating them. But I didn't like the idea of my key having a recognizable pattern: Random data followed by text.

I therefore used the XOR because it preserves the randomness: for a given password, the distribution of a uniform distribution XORed with that password is still the uniform distribution.

Current state:

I have something that should work and if there are bugs, I probably will be able to fix them.

Questions:

Is /dev/urandom fine for my use-case or should I use /dev/random?
Some people told me that I should use a key derivation function because otherwise, the effect of the password isn't spread. But do I need the effect of the password to be spread? The way I see it, cryptsetup will already use a key derivation function on my key to increase computation time and try to spread the effect of each bit.

Feel free to criticize (constructively) any decision or assumptions I've made (for that project).

Is /dev/urandom fine for my use-case or should I use /dev/random?

Theoretically, there is no security difference as both are regarded to be cryptographically secure RNGs. Practically, you’ll want to use /dev/urandom as that is “non-blocking” since it re-uses it’s entropy-pool whenever it runs out of random data, while /dev/random may make your program “stall” if it runs out of entropy. Simpler said: /dev/random can be a bottleneck, /dev/urandom fixes the issue.

  Some people told me that I should use a key derivation function because otherwise, the effect of the password isn't spread. But do I need the effect of the password to be spread? The way I see it, cryptsetup will already use a key derivation function on my key to increase computation time and try to spread the effect of each bit.

I am not familiar with cryptsetup, and I don’t want to judge its internal workings by just taking a short glimpse at the related website… but if you’re sure it implements its own key derivation function (which I think it does as the site talks about using cryptsetup to generate dedicated key-files), it indeed wouldn’t make much sense to run that through another KDF after that. Yet, if you’re not sure if cryptsetup indeed provides a KDF (again: I am not 100% sure about that), or if you have any doubts about the quality of its KDF, I would certainly advise to opt-in for a dedicated KDF tool.

Oh, and one more thing – in case you don’t know about it…

  … I could use dm-crypt directly …

“Word on the street” has it that there are some weaknesses to watch out for when using dm-crypt. Meaning: whenever you’re thinking about dm-crypt, remember to choose your settings wisely.

(screenshot source)


How do I control an access code safely? Upon registration an user has to specify an access code of five digits. This access code is also used as a password for the encryption and decryption of certain strings.

The user types in "12345" (ACCESS_CODE).

Obviously, we don't want to save this access code on the device.

Now, when the user wants to decrypt he types in the access code, and if the code is correct, the decryption will happen succesfully.

However, preferably, I would like, before the decyrption takes place, check whether the access code is right, without saving it on the device.

How can this be achieved?

One way I was thinking is to encrypt a string "CHECKSTRING" with the access code. Then the check would be:

Decrypt the encrypted "CHECKSTRING" (ENCR_STRING) --> (DECR_STRING) with ACCESS_CODE
Check if DEC_STRING == "CHECKSTRING", then code is correct, otherwise not.

But this seems to me quite unsafe, as someone could simulate an encryption of the "CHECKSTRING" (which is known and visible in the code) for all combinations of 12345 and then cross match which code I used to obtain the ENCR_STRING.

What other alternatives are there?

So you have a secret with low entropy which you want to verify in a secure way.

This is a standard scenario in password-based cryptography (PINs are sort of a password).

What you'll do in both scenarios described below:
The user first enters his access-code (=PIN), which get buffered in the RAM. Now storage media (the device/a drive) will provide the program (processor) with a random looking string that the media stored. (This is the salt) The media supplies parameters as well. (Iteration Counts, (N,R,P)-Values, (t_cost,m_cost)-Values). Now you use a password-hashing function (scrypt/winner of PHC) using the supplied parameters, the salt and the password to derive a tag/key.

You have two ways at approaching your problem:

The straight forward way to do what you want is to get a tag generated by the PHS (password-hashing scheme), store this on first entry on the storage media (along with salt and parameters) and just check if the tag matches with what will be generated at verification-time. I wouldn't recommend this way, as it relies on your code to be bug-free.
The better way (in my eyes) would be to derive a key using the PHS, which will be used for verification/decryption. So the security of the data would strongly rely on the password and not on some authorization code. The storage media would only store salt and parameters and you'd  see that the access-code is correct as verification succeeds.


TLS Cipher Suite definitions Based off the various cipher suites available for TLS (which I am looking at here:https://www.thesprawl.org/research/tls-and-ssl-cipher-suites/), can anyone clarify if when the suite contains 'SHA', does it actually mean the orignal sha algorithm, or does it mean sha-1?

That's SHA-1; TLS uses either SHA-1, or on occasion a SHA-2 hash (and those would be listed as SHA256 or SHA384).  I've have never heard of anyone actually using SHA-0 (the hash algorithm originally proposed by NIST).


Prefixing data before encryption for passphrase confirmation? I'm encrypting data with AES, using CryptoJS.

CryptoJS returns an empty string in case the data couldn't be encrypted with the given passphrase. I'm not sure if this is intended, or happens in all libraries, but I need to know whether or not the data was decrypted successfully.

The problem is this:

if(decrypted == '') {
    // Not sure if decryption failed or if data was empty to begin with
}

Would it be okay to prefix the raw data before encryption? Like this:

Raw data:

Lorem ipsum a dolor sit amet.

Prefixed:

this-string-is-used-to-verify-decryption;Lorem ipsum a dolor sit amet.

When decrypting the data, I could simply check if it has that prefixed data in. Meaning, an empty string would only be returned if the decryption failed.

var prefix = 'this-string-is-used-to-verify-decryption;';
if(decrypted.substr(0, prefix.length) == prefix) {
    // Decrypted successfully
}

Is there something wrong with this approach? Does it create a security risk, if an attacker knows all raw data will begin with a certain text?

I originally posted this question to StackOverflow. Thought I'd remove the code parts but they are fairly easy to understand, so I'll leave them.

There is no risk if the attacker knows part of the plaintext. This doesn't help to recover the rest of the plaintext. Even if the attacker knows all the bits but one, with any decent encryption algorithm, the attacker cannot tell what the last bit is from the ciphertext.

After all, it happens all the time with known data formats. For example, if you download a web page over HTTPS, the attacker knows that the page begins with <html><head> or some such.

Note that even if you find the expected prefix, this doesn't guarantee that the rest of the data isn't corrupted: encryption guarantees confidentiality, but not integrity. You need either to use an authenticated encryption mode (which Crypto-js doesn't provide) or to also transmit a MAC of the ciphertext (encrypt-then-MAC).


Use of CBC-AES-256 to encrypt usernames I came across some code in our project that encrypts usernames (limited to 50 chars, most are less than 10) using the following parameters:

IV size is 16 bytes

Key size is 32 bytes

Algorithm is CBC-AES (256bits)

Is there a security issue because of these parameters? Why would you use CBC and not ECB with a key size larger than 50 chars? Is it dangerous to use an IV smaller than the key size? What is the proper way to encrypt usernames in a database?

EDIT:
The IV is being reused for every username. This is not good apparently. I can write a migration script and change the algorithm etc, as long as the usernames are encrypted in the end. If anyone has any suggestions on how to best do this securely that would be very helpful.

Assuming:

the objective is to protect the confidentiality of the user names from an attacker having read access to the encrypted data, the ability to add usernames of her choice, and nothing else (in particular, no access to the key, even by proxy of a computer or device holding the key, or side channel);
the IV is randomly chosen for each individual username encrypted (or re-encrypted after an edit);
the key has been randomly chosen, is not compromised, and is used only for that usage;

then the system using CBC is safe, as far as we know (this follows from IND-CPA security of AES-256 in CBC mode). Notice this is highly theoretical. If an adversary can get remote access to a PC, and unless an HSM or Smart Card is used to hold the key, you have no strong argument that the key did not leak. Even if you use such tamper-resistant hardware to store the key, you have no argument that the adversary could not use that hardware, or otherwise access the plaintext.

Using ECB, the system would be unsafe even with the theoretical hypothesis given. In particular, it would be easy, from the ciphertext, to spot:

identical usernames:
usernames identical up to the first 16 characters bytes;
with high confidence, if a username uses more or less than 16 characters bytes (which in turn could be correlated with ethnic origin).

Update: Having the same IV for every user is a classical mistake, and brings back some (but not all) of the weaknesses of ECB. In particular, it is trivial to spot identical usernames; and thus to spot if a given username is present, for an attacker able to add a user with a given username. Depending on the number of usernames an adversary can realistically add, and on the encoding used for user names (which has considerable influence on the difficulty to exactly guess a 16-byte fragment of a username), it would be more or less easy to recover a fraction (or perhaps all) of the usernames.

IMHO, simply put, there is no proper way to encrypt usernames in an online database. Problem is, whoever can use the database to get the usernames will circumvent any crypto there might be; this is not a cryptographic problem. If you only want to give the illusion of security (or, equivalently, do the best you can in an implementation running in a nondescript environment), use CBC or CTR encryption with a random IV for each encryption of a record.


Memory hard password based key derivation functions? How are memory hard functions designed for the purpose of password based key derivation? To protect against a brute force attack from a parallel machine.

What design could work well with Skein? The Skein paper (pdf) has a time hard PBKDF (basically hashing the password repeat very many times) but not a memory hard one.

Memory hard functions are designed so that the internal calculations rely on a relatively large state. The functions should not have shortcuts that allow an adversary to calculate the result without using of the state at once (at least not without incurring a very high overhead). That way it is impossible for fast hardware to be developed that does not require large amounts of memory.

There isn't one specific design for memory hard functions within PBKDF's. You can have a look at various existing designs (scrypt, Argon2) of memory hard PBKDF's for examples of memory hard functions.

Lets define 3 different methods, going from low level to high level:

Catena was mentioned specifically in the comments as it simply requires a generic hash method to function. If any secure hash function can be used then Skein should be a secure option.
KMAC by now has been defined as a secure HMAC replacement by NIST. So you could use scrypt with PBKDF2 where the HMAC is replaced by KMAC.
scrypt uses PBKDF2 as underlying CPU hard function. Simply replace the PBKDF2 function within scrypt with another CPU hard function such as Skein's PBKDF.

These are hints, providing the security proof is left to the reader.


Am I understanding AES GCM implementation correctly? I am implementing an AES cipher in GCM mode in c# and have a few questions. My code is based on the code found [here] for reference. I'll copy in the relevant portions.

I am having difficulty understand the "additional authenticated data" (AAD) of the GCM implementation. (a) What does the AAD consist of? (b) where should the AAD be stored? (c) Is it detrimental to the operation of the cipher if I leave the AAD blank?
 // Authenticated data becomes part of the authentication tag that is generated during
 // encryption, however it is not part of the ciphertext.  That is, when decrypting the
 // ciphertext the authenticated data will not be produced.  However, if the
 // authenticated data does not match at encryption and decryption time, the
 // authentication tag will not validate.
 aes.AuthenticatedData = Encoding.UTF8.GetBytes("Additional authenticated data");

I also do not understand how I am supposed to utilize the "tag" property. (a) Do I need to store the tag once it is created? (b) is the data authentication portion of GCM automatically implemented?
 tag = encryptor.GetTag();

I'm not certain how to retrieve the IV (nonce) from the encrypted data. The code I am referencing simply makes this call:
 aes.IV = GetNonce();

(a) Is this implicitly removing the first 12 bytes from the encrypted data?
If someone is actually able to answer these questions I'd be completely surprised, but it's worth a shot. Thanks

Well, I'm unfamiliar with this specific C# library, and so I can't answer questions about its API.  I could guess, but I suspect you want something better than that.

However, I can answer generic GCM questions.

1a. What does the AAD consist of?

Well, AAD is another service that GCM provides.  When encrypting messages, it is actually quite common to want to bind some context to the encrypted message; specifically so that message cannot be decrypted in a different context.  What GCM does is stir in the AAD along with the ciphertext data when generating the tag; if the decryptor doesn't have this same AAD when he decrypts, he will compute a different tag, and so the decryption attempt will fail.  Hence, this plaintext AAD is bound to the ciphertext; you need both to decrypt.

Here's one example of where you might use this: in a TLS record, you have a record type that is not encrypted, followed by encrypted data.  One of the things you might want to make sure is that an attacker cannot extract an encrypted data, and reinject it with a different record type.  In this case, you can include the record type in with the AAD; then, if the attacker does reuse the ciphertext with a different record type, the decryption will fail, and the record that the attacker modified will be rejected.

1b. Where should the AAD be stored?

That depends on what you're using it for.  You might be authenticating unencrypted data that is included with the encrypted message (as in the TLS example); in that case, the decryptor would just extract it from the message.  You might be authenticating some state that is shared between the encryptor and the decryptor; in that case, the decryptor would extract it from his database.  You might be doing a combination of both; in this case, we'd extract parts of the AAD from different places.

1c. Is it detrimental to the operation of the cipher if I leave the AAD blank?

Not at all.  AAD is a service that GCM provides for you; if you don't need that specific capability, you can just leave it blank.


TLS RSA Certificate with Elliptic Curve Negotiation When I look at Google's Public Key in Firefox I get

  PKCS #1 SHA-256 With RSA Encryption

Yet according to SSL Labs Google has

  EC 256 bits / SHA256withRSA

and supports

  TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256

How can it when the public key it uses is RSA not a Elliptic Curve one? Does Google present both an EC and an RSA public key in their Certificate file some how?

I found another link, as the purpose of this was to use both RSA and ECDSA for signing, but that, to my understanding, requires different public/private keys and therefore different certificates

See the following link https://security.stackexchange.com/questions/43360/is-possible-that-a-tls-server-send-more-than-one-certificate-to-the-client-for-t

  For signature algorithm support, there is a standard TLS extension
  specified in section 7.4.1.4.1, by which the client can tell to the
  server, early in the handshake (in the ClientHello, which is the very
  first message of the procedure), which hash functions and signature
  algorithms it supports. This allows a server who owns, for instance,
  both a RSA-signed certificate and an ECDSA-signed certificate, to send
  one or the other, depending on what the client supports. This is
  typical of how things go in TLS: the client suggests, the server
  chooses.

So it seems to support both ECC and RSA you HAVE to get the client supported algorithms early then play a 'trick' by swapping out the cert. It seems there is no way to just have it be based on the support list of ciphers where you can send multiple certs and have one be your RSA one and the other your ECC one.

EDIT

Here is another link https://security.stackexchange.com/questions/8343/what-key-exchange-mechanism-should-be-used-in-tls that confirms that the certificate and the key exchange and cert keys have to match up

  You may use a key exchange (as part of a cipher suite) only if the server key type and certificate match.


If a permutation $f$ is not one way, what can we say about $f^{p(n)}$? Consider a permutation $f:\{0,1\}^*\rightarrow \{0,1\}^*$, which is not a one-way function, i.e. there exists an efficient probabilistic adversary $\mathcal{A}$ and some polynomial $q(n)$ such that for infinitely many $n$

\begin{equation}
\mathrm{Pr}[\mathcal{A}(f(x)) = x] > \frac{1}{q(n)},
\end{equation}
where the probability is over the internal randomness of $\mathcal{A}$ and  $x$ drawn uniformly at random from $\{0,1\}^n$.

I would now like to prove that $f^{p(n)}$ is not a one way function, for any polynomial $p(n)$. Is this true for all permutations $f$ which are not one way?

My intuition was that this would be true, and that one could prove this by showing that $\tilde{\mathcal{A}} = \mathcal{A}^{p(n)}$ is a suitable adversary for $f^{p(n)}$. However, I can't get this to work. Is there a clever way to prove this, or is the statement I am trying to prove actually false?

If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.

Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for any bitstring $x$,

$$\begin{align}f(x\mathbin\|0)&=x\mathbin\|1\\f(x\mathbin\|1)&=g(x)\mathbin\|0\end{align}$$

$f$ is a permutation. It is trivially invertible for half its inputs of any fixed width, thus is not a OWP.

$f^2$ is also a permutation, with

$$\begin{align}f^2(x\mathbin\|0)&=g(x)\mathbin\|0\\f^2(x\mathbin\|1)&=g(x)\mathbin\|1\end{align}$$

An hypothetical algorithm that inverts $f^2$ starting at width $n>m$ could be used to invert $g$ at width $n-1\ge m$. With $g$ being a OWF, there is no such algorithm. Hence $f^2$ is one-way.


Additive homomorphic encryption: strict equality - handling congruence Is there an additive homomorphic encryption scheme which guarantees that if provided with

$E(v)$, $E(m_1)$ and $E(m_2)$

and $E(v)=E(m_1).E(m_2)$ then $v=m_1+m_2$

Please note this is not $v \equiv m_1+m_2 \pmod p$

To illustrate, assuming a group of order $p$, the additive version of ElGamal does not seem to match the criteria. Assuming $v=m_1+m_2$, there exists values $m'_1$ and $m'_2$ such that

$m'_1+m'_2 = m_1+m_2+k(p-1)$, $k \in Z^*$

which verifies $E(v)=E(m'_1)E(m'_2)$ due to Fermat's little theorem although $v$ is not equal to $m'_1+m'_2$

A simple numeric example is, assuming order $p=7$, a generator $g=2$, $v=4$, a shared secret $s$,

$m_1=1$ and $m_2=3$ obviously verifies that $E(1)E(3)=E(4) = 2^4.s \pmod 7 \equiv 2.s \pmod 7$

but so does $m_1=4$ and $m_2=6$ since $2^{10} \equiv 2 \pmod 7$

I think this kind of scheme can't even be construct, because the message space is always finite, thus we are always working in some kind of modular structure.

If we say that $\mathcal{M}$ has $n$ elements and that it is closed to the sum, then for all $m \in \mathcal{M}$, adding $m$ to itself generates $\{m, 2m, 3m, ..., nm, (n+1)m\} \subset \mathcal{M}$.

But by the Pigeon hole principle, at least two of those values are equal. So, let's say $pm = qm$ with $q > p$, then $(q - p)m = 0$.

Therefore, there exists this positive number $k := (q - p)$ such that $E((k-1)m) \otimes E(m) = E(0)$.

That said, what was typically done was to chose parameters in a way that the message space is large enough for the application, so that the generated values don't get bigger than the known modulus (then the decrypted value is always equal to the expected one, without being reduced).


I read ECB is bad because the same plaintext outputs the same ciphertext. Isn't that a requirement of a cipher? In the Wikipedia article on Block Ciphers, it says about the Electronic Code Block mode:

  The disadvantage of this method is that identical plaintext blocks are
  encrypted into identical ciphertext blocks; thus, it does not hide
  data patterns well. In some senses, it doesn't provide serious message
  confidentiality, and it is not recommended for use in cryptographic
  protocols at all.

How is that a disadvantage? Isn't it a requirement of a cipher that identical input produce the same output? Otherwise, how could you decipher the ciphertext if it could have been created by many different inputs?

Indeed, ECB is such that encrypting twice the same plaintext leads to the same ciphertext. Even worse, encrypting a plaintext containing twice the same plaintext block leads to a ciphertext containing twice the same ciphertext block. Either is a disadvantage because it goes against the ideal of a cipher: depriving the adversary from any knowledge about the plaintexts, with the sole exception of length.

An example of why that's a drawback is if we encipher plaintexts consisting of votes cast in an election, with plaintext N for a no vote, Y for a yes vote. With any cipher such that encrypting twice the same plaintext leads to the same ciphertext, someone intercepting the ciphertexts will see two values, and can determine each vote (assuming a single vote is known, or it is known that Y outnumbers N).

If a cipher has the property that plaintext and ciphertext have the same size for any unconstrained plaintext, then indeed (in order for plaintext to be exactly decipherable, and by a counting argument) the cipher is bound to have said drawback. Hence modern ciphers have a ciphertext larger than the plaintext (typically for symmetric ciphers: by the Initialization Vector's size at least).

Addition per comment: an example of a cipher not bound to generate the same ciphertext when enciphering twice the same plaintext would be $\operatorname{AES}$ in counter mode with key $K$

encryption:

generate a 128-bit Initialization Vector $C$ at random, using the computer equivalent of tossing a coin 128 times, and outputs $C$ as the first 128 bits of the ciphertext
while remaining plaintext length $l>0$

output the eXclusive-OR of the next $\max(l,128)$ bits of plaintext and as many of the leftmost bits of $\operatorname{AES-ENC}_K(C)$
$C\gets C+1\bmod2^{128}$ (increment the counter)

decryption:

set $C$ as the first 128 bits of the ciphertext
while remaining ciphertext length $l>0$

output the eXclusive-OR of the next $\max(l,128)$ bits of ciphertext and as many of the leftmost bits of $\operatorname{AES-ENC}_K(C)$
$C\gets C+1\bmod2^{128}$ (increment the counter)


RSA modulus (N) from public key and calculating N from p, q not equal I have a RSA public key in the form of public exponent and modulus as follows:

String exponent = "0000000000000003";
String modulus = "D8016FFDDFBA4B144B0AB13FF01968048B2FC9AA269311D11357DC8CEDCABA232BEC118D3B05AFA2406D27BFB6602B45B80E91D4F446E4A753C251EA6EB8AB8E3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D";

And also I have a private CRT key of the corresponding RSA key as follows:

String p = "F401F9E76A0E65D80AA8CF0D526D8D8747E53A3E1223B143AA73F675708ED966AB96965040907CCDF3D5C77904AA0906A6941E3A9C69AEC1F99E73E6EDB07191";
String q = "E29F25EC241F0FEDAD28B8DD1DCBABBD066F4F557467AE6A2CE4ED34F9D93257E2F8C8B6EE1F7A687E386BFEE9C20C3388385E82AFA498237FF801D283216D4D";
String dp = "A2ABFBEF9C09993AB1C5DF5E36F3B3AF85437C29616D20D7C6F7F9A3A05F3B99C7B9B98AD5B5A8894D392FA6031C06046F0D697C6846748151144D449E75A10B";
String dq = "9714C3F2C2BF5FF3C8C5D0936932727E044A34E3A2EFC99C1DEDF378A690CC3A975085CF496A519AFED047FF46815D77B02594571FC31017AAA5568C576B9E33";
String qinv = "075130A6D464E1541E92CCDF21BC4860D4E9E1BEF664CF5900A93774C67A507C13F1FAD2BEC2DCD0BEB4F2535C8175890ABA1BE851D0067B462C4876477E5DA7";

This kind of key was generated for testing purposes.

So I would like to check if it is correct and I have found out that mulitplying of p with q would give different modulus N, resp. N is different only at one half. I used the following calculation:

byte[] bp = hexToByteArray(p);
byte[] bq = hexToByteArray(q);
byte[] bdp = hexToByteArray(dp);
byte[] bdq = hexToByteArray(dq);
byte[] bqinv = hexToByteArray(qinv);

BigInteger pBI = new BigInteger(bp);
BigInteger qBI = new BigInteger(bq);
BigInteger modulusBI = pBI.multiply(qBI);

And the resulting modulus modulusBI has the following value in HEX:

0160502A518CD54E933929557FE02EC03CDB4016A007B2233BFEF8E28362AE649D5CB2860C55B86BCE5EF447C7F4160B89421517A8389DC1DA2BDC30FDE6CCB03F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D

The value is not same as original modulus N from public key, but one half of it is correct, as you can see:

Computed N :0160502A518CD54E933929557FE02EC03CDB4016A007B2233BFEF8E28362AE649D5CB2860C55B86BCE5EF447C7F4160B89421517A8389DC1DA2BDC30FDE6CCB0 3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D
Original N :D8016FFDDFBA4B144B0AB13FF01968048B2FC9AA269311D11357DC8CEDCABA232BEC118D3B05AFA2406D27BFB6602B45B80E91D4F446E4A753C251EA6EB8AB8E 3F304585DD202D8B04538EB4DD1F87D9A27E1E7B34A304396BBC38EE669E823BD03C1F43698B4B3128F3770C465CE415FD0F965F3170CED1470ED777751DE59D

The second half of modulus is correct. Why is that? Am i doing some mistake in multiplying primes p and q?


Are any block ciphers provably free of equivalent keys? There are $2^n!$ possible permutations of an $n$-bit block cipher $E_k:\{0,1\}^n \rightarrow \{0,1\}^n$, and any given key $k$ selects one of these permutations at random. Define equivalent keys as a pair of keys $k \neq k^\prime$ where $\forall P:E_k(P) = E_{k^\prime}(P)$ and $P\in\{0,1\}^n$. The probability that such a pair exists for realistic cipher parameters is very low. Can a block cipher be proven to be free of equivalent keys?

Yes, some block ciphers provably have no equivalent keys.

For a start, it's very easy to exhibit such a block cipher, by restricting the key and message spaces to something enumerable. Granted, that makes the cipher insecure.

But we can also construct such a block cipher secure under chosen-plaintext attack. Assume a secure block cipher with the same key and block space (e.g. AES-128). Note $E_k(x)$ (resp. $D_k(x)$) for the encryption (resp. decryption) of $x$ under key $k$. And define
$$E'_k(x)=\begin{cases}
0,&\text{if }x=k\\
E_k(k),&\text{if }x\ne k\text{ and }x=D_k(0)\\
E_k(x),&\text{otherwise}
\end{cases}$$
In other words, $E'_k$ is the same function as $E_k$, except possibly for inputs $k$ and $D_k(0)$, which outputs are swapped.

Notice that for any fixed $k$, the function $E'_k$ is well-defined and a permutation of the block space, including in the rare case $E_k(k)=0$, which degenerates in $E'_k=E_k$. Hence $E'$ is a block cipher. And it is demonstrably secure under chosen-plaintext attack if $E$ is, because access to an encryption oracle gives no efficient way to query for $k$ or $D_k(0)$.

The corresponding decryption is
$$D'_k(x)=\begin{cases}
k,&\text{if }x=0\\
D_k(0),&\text{if }x\ne0\text{ and }x=E_k(k)\\
D_k(x),&\text{otherwise}
\end{cases}$$
And since $k=D'_k(0)$, there can't be equivalent keys. For if keys $k_0$ and $k_1$ yielded the same bijections $E′_{k_0}$ and $E′_{k_1}$, then the reverse bijections $D′_{k_0}$ and $D′_{k_1}$ would be the same, hence we would have $D'_{k_0}(0)=D'_{k_1}(0)$, hence $k_0=k_1$; now by contraposition, different keys must yield different bijections, Q.E.D.


How to protect against brute force attacks in the case of a small dictionary? Sorry if I'm not using the right terminology, as I'm new to crypto.

I want to know the most effective way to protect a database against brute force attacks in the case of a small dictionary.

For instance, suppose I have a user database, and that I want to protect a certain attribute/field of my users that has a small cardinality (e.g. the field can assume one of at most a few hundred values), for instance "country". There are a small number of countries in the world, so a brute force attack would be effective even if I hashed the country field: the attacker could just hash all countries and try those hashes one by one on a given user. Worse, they could use simple statistics to make their guesses more educated.

What should I do in this case? Should I add some salt before hashing? If I store the salt and the attacker gets access to it, is the field still protected?

Edit: My question is not tied to the specific case of the column of a table. Rather, I am asking what are the algorithms to use when the dictionary size is small.

I think you're looking for column level encryption.

It allows you to encrypt specific columns in your database, in your case the cloumn "country".

Another way would be to use database encryption, which can encrypt an entire database. The main disadvantage there would be the speed, because the size of the data to encrypt / decrypt is larger than just the data in a single column.

Just be sure to store the encryption key securely. You can find more information about this topic in this post: SecuritySE - Where to store a server side encryption key.

Edit:

  My question is not tied to the specific case of the column of a table. Rather, I am asking what are the algorithms to use when the dictionary size is small.

You could simply use a symmetric-key algorithm, i.e. AES in CTR mode to protect your data. It works for both small and large data.


What informal indicators exist for estimating the computational infeasibility of cryptographic problems? When assuming a block cipher primitive is secure, or a number theoretic problem is hard, this assumption is usually based on how far we are from breaking the primitive or solving the problem using known techniques - using known algorithms and hardware.

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware? I am not asking for opinions on the matter (or for arguments that fix the algorithms and prove that the necessary hardware would be physically impossible) but for justifications based on e.g. the sociology of cryptography or economics of cryptography, using scientific (justified and repeatable) methods and based on the premise that all research is done in the context of pre-existing research.

How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?
Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?
If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?
What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?

But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware?

From a cryptographic point of view, the best answer is usually modularity: we want to design schemes which can be based on "instantiation-oblivious" hypothesis (i.e., hypothesis that we can instantiate over a large variety of objects sharing some mathematical structure). For instance, we know that the discrete logarithm problem is hard in a generic group (a group with no additional structure). Therefore, if a scheme based on the discrete log is broken on a given structure, it will likely remain secure if it is instantiated on another group, with less additional structure (notwithstanding the advent of quantum computers, ofc).

From a meta-cryptographic point of view, once a specific system is deployed, our confidence comes essentially from two considerations:

How long has the underlying problem been studied
How many people are actively doing research in cryptography (both in academia and companies)

For example, the factorization problem already has a very long history, hence it seems more likely that our understanding of it is more advanced - put otherwise, there is less chance that we missed a simple approach that would allow for fast factoring. However, the second consideration remains probably the most important one. In the 90's, it was plausible for a powerful intelligence agency (such as the NSA) to hire enough mathematicians, and to give them access to a huge computing power, so as to be competitive with what the rest of the world could do. With the evolution of cryptography in the past decades, that does not seem plausible anymore. Thousands of researchers are actively working on cryptography, hence an agency could, at best, hire a very small fraction of these researchers. I see no strong reason to believe that all the best researchers could end up working for the same agency (especially since cryptographic research is spread worldwide). Assuming that the researchers an agency can hire are sufficiently representative samples among good researchers, this implies that the probability that a cryptographic breakthrough comes from a given agency is reasonably small. The same observation holds with respect to computational power: nowadays, even an agency as powerful as the NSA cannot mount cryptographic attacks that would require way more computational power than what, e.g., Google, Apple, or Microsoft have access to.

  How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?

It is not impossible. It appeared in the past: Clifford Cock had essentially discovered  RSA five years before its introduction by Rivest, Adleman, and Shamir, while working for the GCHQ. In the 70's, the NSA had apparently already discovered differential cryptanalysis (see this post by Bruce Schneier), which could break many seemingly secure schemes, and was only 'publicly' discovered in the 90's. However, at the time, the amount of people working in this field was considerably smaller than today. Nowadays, the probability of such an event happening should probably be close to (number of people working for the agency)/(number of researchers working on area related to what the agency works on). Hard to precisely estimate, but likely small.

  Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?

Again, it is not impossible, but it requires luck more than anything else. But that was assuming the question was about finding breakthrough results on cryptanalysis of deployed schemes. In fact, other types of attacks can be found, and they seem way more likely.

the agency can find an attack, not on a primitive, but on a protocol. Due to their highly complex structures, the landscape of possible attacks in considerably increased. Unlike cryptanalysis of primitives, breaking a protocol is not about finding advanced mathematical methods, it's only about thinking about something that people did not consider before. A good example of it is the recent logjam attack, or 3SHAKE. It is not completely unlikely that some agencies are already aware of attacks of this type that have not yet been publicly revealed.
Even more likely, the agency can directly find flaws in a specific implementation (either of a cryptographic primitive/protocol, or at a higher level). Those flaws are usually devastating, conceptually very simple, and seem considerably more easy to identify than, say, a new factoring algorithm (such flaws are discovered routinely). One can think for example about the recent heartbleed. Here again, it seems quite likely that some agencies are already aware of security issues that have not been yet publicly revealed.

  If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?

If the organization is small and keeps everything it does secret, there is no way to tell. Intelligence agencies will obviously not write patents or publish papers about their most critical discoveries. However, if the organization is small, it has also a very small probability of being the one from which a cryptographic breakthrough originates.

On the other hand, if an organization is large, then there is a standard way to know what it is working on: leakages. If the organization works with many people, on sensible subjects of crucial importance, something will end up leaking - human flaws are the only one that an agency cannot cope with. This happened with Snowden, and can happen again.

  What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?

That completely depends on the particular scenario: it could be that an active attack will remain undetected, or that it will be detected with noticeable probability. In the field of secure computation, which an important and active research area in cryptography, this fact has been acknowledged by considering three types of adversarial behaviors: passive, covert, and active. Passive and active attacks are the types you already know; a protocol secure against covert adversaries can be broken by an active attack, but it is not possible to break its security without being caught (with good probability). The rationale behind this was that in practice, an important company/agency would likely want to attack cryptographic protocols, but cannot afford being caught when doing so.

If the weaknesses requires only passive attacks, and the agency is only gathering information, there is no way to tell (except internal leakages): a passive attack can be mounted offline, on the transcript of some interaction, hence there is no reason why anyone could discover about the outcome of the attack, unless that person is already part of the agency.


CTR DRBG dependent on request size? I am trying to understand the CTR DRBG specification in NIST SP 800-90A. It seems slightly different to a pure stream cipher in that the key and counter are reset after each generate call using the output pseudo-random bits. I understand that this is to provide backtracking resistance.

My question is, does this imply that the output bits produced by the DRBG are dependent on how the requests are 'chunked'? i.e.

$$
Generate(state, 8) || Generate(state, 12) \neq Generate(state, 12) || Generate(state, 8)
$$

...or have I not understood the specification correctly.

You are correct. The $Update$ function is called after each invocation of the $Generate$ function, and this does mean that chunking affects the output. Changing both the key and the nonce of an $AES-CTR$ key stream generator to uniformly selected (pseudo) random values will, of course, make the resulting key stream uniformly independent from what it would have otherwise been.

However, it might be noted that the first $8$ bits of $Generate(state, 12)$ equals the full $8$ bits of $Generate(state, 8)$.

It should be noted that a $DRBG$ is primarily to be used as a replacement for a $TRBG$ (true random bit generator). It is not designed to be used as a stream cipher (which must support chunking) or as a key derivation function (which might support chunking). In particular, the NIST SP 800-90A specification explicitly forbids instantiating a $DRBG$ with the same state twice, which by itself makes it impossible to use it as a stream cipher or key derivation function.


Does Runge phenomenon affect Shamir's secret sharing scheme? Lagrange interpolation seems to be affected by the so-called Runge phenomenon when one tries to interpolate polynomials of high degree from a set of equidistant points.

Lagrange interpolation is used in some secret sharing schemes like Shamir's secret sharing, in which the polynomial being interpolated is not continuous but defined over a finite field.

Does any of you know whether this Runge phenomenon also exists or could also affect the accuracy of the interpolation done in Shamir's secret sharing scheme?

No, the Runge phenomenon is known not to affect Shamir's scheme.

Remember, the point of Shamir's scheme is not actually to form an approximation over an interval; instead, it's to encode a secret in a randomly chosen polynomial, and then divide up clues to that polynomial so that, with enough clues (shares), someone can reconstruct the entire polynomial (and hence recover the secret).

(Now, in practice, we don't bother reconstructing the entire polynomial; instead, we just recover the coefficient that is the secret.  However, that's just a detail; we could, if we wanted to, recover the entire polynomial).

So, in terms of accuracy, the question is "do we recover the polynomial with sufficient accuracy so that we can uniquely identify the secret".  And, the answer to that is, yes, we can (because computation in Finite Fields are done precisely, with no rounding errors).


AES-256 Shift-Rows Offsets I am currently trying to implement a AES-256 cipher according to this sepcificaciton:
http://techheap.packetizer.com/cryptography/encryption/spec.v36.pdf

As well as on Wikipedia and in the document these offsets for the shift-rows operation are given (depending on the key size):

Row  128 192 256
 1    0   0   0
 2    1   1   1
 3    2   2   3
 4    3   3   4

The example for 256-Bit encryption (page 26 onwards) obivously uses the same offsets (0-1-2-3) for all key sizes:

R[ 1].s_row   d4bf5d30e0b452aeb84111f11e2798e5 (given Example)
R[ 1].s_row   d4bf52aee0b411f1b84198e51e275d30 (my calculation with 0-1-3-4)

Extracting the rows:

Row#  0-1-3-4 calculation  example calculation
 1    d4 e0 b8 1e          d4 e0 b8 1e
 2    bf b4 41 27          bf b4 41 27
 3    52 11 98 5d          5d 52 11 98
 4    ae f1 e5 30          30 ae f1 e5

So the question is: What are the correct offsets: 0-1-2-3 or 0-1-3-4? If the latter is correct (what i believe) there is an error in this document or i missed the up-to-date version since 2003 is already a while ago...

Actually, the document talks about Rijndael, not AES.

Aren't Rijndael and AES that same?  Well, not precisely; Rijndael is specified with a set of parameters that AES does not support; how example, how it works with different block sizes.  AES is defined only with a block size of 128; Rijndael supports a set of different block sizes.

That is where your confusing is coming from; the varient shift-rows are used if you have a block size of 256 bits; since AES never has a block size of 256, those shift rows are never used.


What's the difference between AES and earlier block ciphers? Is there any difference except speed and key and block size from user's point of view?

Or does AES have something that ideal block cipher doesn't have?

From a user's point of view, AES improves on DES and 3DES in at least two important aspects beyond speed and key length:

AES is a 128-bit block cipher, which makes it more secure for huge volume of data than a 64-bit block cipher is. For example, any 64-bit block cipher in CBC mode is vulnerable to a simple distinguisher attack: the adversary has a chance to recognize plaintext with all identical blocks (e.g. unused portion of a file), because the corresponding ciphertext is more unlikely to contain collisions than it is for random plaintext. That makes 3DES-CBC quite practically unsafe for 32 GiB enciphered; for 8 MiB enciphered, the advantage is already like $2^{-25}$ (fixed).
AES does not have the complementation property of DES (and 3DES), which is that $\forall K, \forall X, \overline{\operatorname{DES}(K,X)}= \operatorname{DES}(\overline K,\overline X)$; that property, while occasionally useful, is undesirable in some protocols, and from a theoretical standpoint makes DES and 3DES trivially distinguishable from a random encryption oracle.


Understanding message reversible mapping function in group G In ElGamal encryption, it says that the message M that is about to get encrypted must be mapped to its m counterpart in the group G using a reversible mapping function.

  Map the message M to an element m of G using a reversible mapping function

Can someone help me understand (and point to some explanatory source) exactly what function this could represent? Can any message be mapped in such a way even though the group G is finite?

In ElGamal encryption, the key-gen starts with a cyclic group $G$, of order $ q$, with generator $g$.

Now you want to map, $M$ into $G$. The simplest one is: if $M < q$ than map $M$ to $M$-th element in the group. If $M \geq q$ divide the $M$ into blocks. Choosing the block size is one bit less than $q$'s bit size, is easier and better.  Once you divide, map each as in the first case.

The second case is similar to what we do in the block cipher as in ECB mode. However, ElGamal is a probabilistic encryption scheme, therefore we don't need IV, but you need to use a new random $y$ for each block.

Actually, one can find more mappings, for example, the permutations. Usually, that will be costlier than the simplest one.


What are the properties of a function based on multiple iterations of a pseudo-random permutation? Let $F(S) = \text{Keccak-}f[1600](S)$.

Assuming that the length of $S$ is equal to $1600 \times k$ and if $k$ is greater than $1$, we define a function $F_{k}(S)$ as follows.

We note that $S$ is a concatenation of $k$ $1600$-bit sequences. We denote these parts by $X_1$, $X_2$, ..., $X_k$.

We choose (arbitrarily or randomly) $k^2$ different $1600$-bit sequences and denote them by $Y_1$, $Y_2$, ..., $Y_{k^2-1}$, $Y_{k^2}$. Note that these sequences are open, not secret.

Then $F_{2}(S) = A_{1} \mathbin\Vert A_{2}$, where $$\begin{array}{l}
A_1 = F(F(X_1 \oplus Y_1) \oplus X_2 \oplus Y_2)    ,\\
A_2 = F(F(X_1 \oplus Y_3) \oplus X_2 \oplus Y_4).\\
\end{array}$$

Similarly, $F_{3}(S) = A_{1} \mathbin\Vert A_{2} \mathbin\Vert A_{3}$, where $$\begin{array}{l}
A_1 = F(F(F(X_1 \oplus Y_1) \oplus X_2 \oplus Y_2) \oplus X_3 \oplus Y_3),\\
A_2 = F(F(F(X_1 \oplus Y_4) \oplus X_2 \oplus Y_5) \oplus X_3 \oplus Y_6),\\
A_3 = F(F(F(X_1 \oplus Y_7) \oplus X_2 \oplus Y_8) \oplus X_3 \oplus Y_9),\\
\end{array}$$ and so on.

Question:  if $k$ is greater than or equal to $2$, is $F_{k}(S)$ a PRF or PRP? What is its security parameter (the expected number of security bits)?

It is neither, because you're only talking about a fixed function—it's not even the right type of object to be a PRF or PRP.  Keccak-f[1600] is not a pseudorandom permutation family itself; it is a single fixed permutation.  A PRF or a PRP is a family of functions indexed by a key, such that a uniform distribution on keys induces an apparently uniform distribution on functions or permutations in some space.


GPG encrypt performance degradence for thousands receipients I plan to use GPG to encrypt a small file (32KB) for very many recipient public keys (few thousands).

I tested GPG with RSA and then ECDH public key encryptions. If RSA is very slow, with ECDH (nist 256 curve) I get (still bad -but) better results:

1K destinataries encrypt: 14sec
5K destinataries encrypt: 5m42sec

Now, my understanding was that all GPG does is to encrypt the file with a symmetric (session) key, and then encrypt the symmetric key with the public key of each recipient. Thinking that the ECDH is the bottleneck, I did an openssl speed ecdh on the machine and got:

256 bit ecdh (nistp256)   op=0.0001s  op/s=18934.7

My question is what can cause such a bad performance for 5K recipients if ECDH seems to be so quick with openssl? Is there anything else that GPG does (besides the symmetric and asymmetric encryptions) that can explain the 5m42s time?

You don't provide much information on your setup or. testing, but I'll take a stab at helping you improve the performance of your system.

Yes, ECDH is actually supposed to be less demanding than RSA in terms of demands it makes on the system, so I'm surprised at your situation and would equally love to know what caused it!

Here are some things to look at to help isolate the fault.  Might not address ECDH specifically, but need a baseline of info to at least start with:

Firstly, different version of GPG- GPG and GPG2- have different performance characteristics.  So useful to know what version you're using:

gpg --version
GPG encrypts to binary format by default unless told to use ASCII with the --armor r -a switch.  This can have performance implications.  Try the following command with and without the -a switch to see how performance is affected.  Also read the debug info which is output to see if it's puking any errors.

time gpg --debug-all --batch --yes --trust-model always -r username@userdomain.com -a -e ./gpg-performance-test.txt
Encryption is CPU intensive, so having a snappy processor improves performance.  Also check your memory:
free -m
Myself, if I had a gazillion people I needed to encrypt a message to, I'd write a script that iterates through a list of email addresses with the above command and emails the message.  And I would run top while the script was executing.  But it's possible to run a single command with multiple recipients so any of them can read the message with their secret key.  You're not clear on how you're doing the encryption.

Might be enough to help you identify the bottleneck, or if not, at least exclude what is *not causing it. If you've already identified the source of the problem, please post your findings.


Besides key and ciphertext sizes what are other advantages of elliptic curve versions of various protocols? There are elliptic curve variants of Diffie-Hellman, ElGamal, DSA and possibly other protocols/algorithms. I know that these elliptic curve variants have smaller key and ciphertext sizes which will make communications (or storage) more efficient.

  Are there other advantages to the elliptic curve variants of these standard protocols/algorithms?

Specifically I am interested in speed and power consumption, but other potential advantages like resistance to side-channel attacks are also of interest.

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash function), the computational cost of a private key operation (decryption, signature generation) is roughly $O(n^2t)$, both for the modular and the elliptic curve variants. The big-O notation hides a constant, which is about $10$: for the same $n$ and $t$, the elliptic curve variant will be 10 times slower than the older modular algorithm.

However, elliptic curves tolerate much lower $n$ for a given security level. Basically, for $t = 112$, we need $n = 2048$ for the modular algorithms, but $n = 224$ is sufficient for elliptic curves (these comparisons are always a bit subjective, see this site for details). Report the values in the formulas: even with the factor 10, the elliptic curve variant will be more than 8 times faster than the modular algorithm of comparable strength.

Another point is binary fields. When the implementation platform is a dedicated ASIC/FPGA, or even when the platform is a small CPU which does not offer a very optimized multiplication opcode (e.g. the ARM Cortex M0), then curves on binary fields give a huge implementation boost, especially Koblitz curves. It also has benefits for memory-constrained systems, see for instance this presentation. The "modular" algorithms cannot really benefit from binary field computations (it can be defined, but discrete logarithm on binary fields is easier than modulo a random prime, so a binary field variant of modular DH or ElGamal would require a $n$ twice larger, hence a four-fold slowdown).


What's the most secure way to derive a key from a password repeatably? I'm trying to write a cloud storage application where everything the user uploads is unreadable by the server, encrypted client-side before being sent.

Currently, the flow looks like this:

User inputs password
Password is salted and a 256-bit SHA-3 hash is taken
A new true-random key is generated
The password hash is used as a key to encrypt the random key and IV (AES-256-CCM)
The encrypted copy of the random key is sent to the server for storage
When the user logs in, they download and decrypt this, again with the password
The random key/IV pair is used to encrypt user files

How bad is it that I'm using a hash with a fixed salt as an encryption key? Is there a better way to do this? The problem is just that I need each password to generate exactly the same key each time, and I didn't see how to do that without a fixed salt, and indeed, a fixed IV in the encryption action.

Also, if it isn't clear why I'm using this key to encrypt another key, my thought is that the second key is significantly more random (minimum 4500 passes of PBKDF2), plus it provides the potential to change the password without having to re-crypt every single user file.

Is there a better way to do this?

Yes there is, using tools specifically designed for this problem - namely key derivation functions (KDF). Good ones include PBKDF2 and bcrypt. A more modern, better alternative is scrypt, but it's relatively new and could use some more analysis before deemed safe.

All above mentioned algorithms take a password and a salt, as well as tweakable security parameter(s). I recommend storing a randomly generated salt (at least 128 bits) for each user in the database and passing that into the algorithm. The key used for encryption/decryption is simply the key generated. I can't give a recommendation on the security parameters - you'll have to do your own research as to what makes you comfortable.

  Also, if it isn't clear why I'm using this key to encrypt another key, my thought is that the second key is significantly more random (minimum 4500 passes of PBKDF2)

You do not have to do this with a good KDF.

  Plus it provides the potential to change the password without having to re-crypt every single user file.

Do you really want this? This means that if I managed to "hack" someone once I'll be able to read his files at any point in the future. If you still want this feature I'd suggest to store a randomly generated number (on the client side) encrypted using the key generated with the KDF (your idea) in the database. Make sure to inform your users about the decoupled password/key system in laymans terms, and give them the options to re-encrypt under a newly generated key.


Statistical tests for PRNG that generates a sequence which is not binary Is there a pratical application to PRNG that generates a sequence which is not a binary one? A ternary, quaternary sequence, for instance. If so, how can we test this? Is there any alternative test suite, like NIST test suite in order to test the randomness for non-binary sequences? For example, what if I generate a sequence in modulo 255 and then use it to encrypt an image in one-time pad manner via adding the values of pixels by the generated sequence in modulo 255 ?

Randomness testing uses asymptotic properties. Thus, as the length of your input increases the effect you are concerned about will disappear.

Specifically, there is no need to convert ternary $1$ or $2-$tuples to binary. If you let $n$ increase you cover the interval $\{0,1,\ldots,3^n-1\}$ and then you convert these integers to binary, paying at most a 1 trit (Shannon's term for entropy in base 3) penalty in entropy. Since a decent ternary source should yield not much less than $$\left(\frac{\log 3}{\log 2}\right)n$$ bits or $n$ trits of entropy, there is nothing to worry about.


AES key expansion vs. a hash Is there something special about the AES key expansion algorithm that makes it secure, or it is a compromise between security and speed? For example, say with a key I expand it by taking pbkdf2(key) or scrypt(key) as the next round, and scrypt(scrypt(key)) as the round after that, until I have all of my subkeys. Would this be more or less secure than the standing key-generation method, and preferred in the case of having a machine which can perform them both in the same amount of time (impossible I know, but it's hypothetical).

Often I hear the key expansion is the weakest part of AES, but conflictingly that it was designed to prevent the use of "weak keys" which its predecessor suffered from.

Often I hear the key expansion is the weakest part of AES, but conflictingly that it was designed to prevent the use of "weak keys" which its precedent suffered from.

The terms "weak" here mean different things.

Some of the best attacks on AES have been oriented at attacking the key schedule. When these attacks were released the cryptographic community was not too surprised because the key schedule had seemed like one of the easier attack vectors from as far back as the original AES competition. If you consider the AES algorithm as a whole, the key schedule is an easier component to craft attacks against, making it a weak point of the algorithm.

However, "weak keys" as a phrase has a specific meaning. It refers to keys that, for their respective algorithms, provide abnormally poor encryption properties relative to the other keys. For example a DES key of all 0s or all 1s is considered weak. AES does not have any such weak keys, all keys are expected to perform equally securely.


RSA encryption/decryption process is not working correctly I'm trying to apply the RSA cryptosystem to encrypt a byte M=72, using predefined modulus n, public key exponent e and private key d.

(n, e, d, p, q) = (4802, 5, 59, 43, 8)

In order to accomplish that, I used the following code on Python console:

C=(M**e)%n
M=(C**d)%n
print M

the first instruction encrypts the byte as C: using the RSA encryption mathematical expression (** stands for exponentional, and % for modulus in Python programming language)
the second decrypts C to get M back: using the RSA decryption mathematical expression.

However, the output shows:

  2816

which means that M was incorrectly computed as '2816', although I'm pretty sure that all the values of n, e, d, p and q respect the RSA public key algorithm specification.

Does anyone have any idea?

The RSA definition requires $n = p q$ where $p$ and $q$ are distinct primes.
In your example $n=4802$ has a factorization as;
$$ n = 2 \cdot 7^4$$ with 10 divisors. Also, your $q=8$ is not a prime.

Here a working example for you with  fips.186-4 standard, or see $\lambda$ versus $\varphi$ in RSA;

Select two distinct random primes;  $p = 47, q = 43$
compute $n = 47*43 = 2021 $
compute $\lambda(n)=\operatorname{lcm}(p-1,q-1)= \operatorname{lcm}(62,42)= 966$
select $e$;

$e=3$;
$gcd(3,966) = 3 \neq 1$ chose another;
$e=5$
check $gcd(5,966) = 1$, ok.

$d = 773$ by $d = e^{-1} \bmod{\lambda(n)}$

As noted by Fgrieu on the comments, make sure that you are using efficient methods. For example;

For finding prime numbers probabilistic Miller–Rabin primality test, should be enough. Note that Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations.
For modular multiplication there are various chocies as  $2^k$-ary sliding window algorithm used by GNU GMP, left-to-right or right-to-left modular multiplications.
Modular inverse by the extended-gcd algorithm.

Calculating with Wolfram Alpha
One can use the highlighted text to enter at WolframAlpha with your paramaters:

$\lambda(n):$   CarmichaelLambda(2021) result is 966
$gcd(5,966):$   gcd(5,966) result is 1
$d:$            5^-1 mod CarmichaelLambda(2021) result is 773
encrypt $m=65:$ 65^5 mod 2021 result is c=168
decrypt $c=168:$ 168^773 mod 2021 result is 65

Note: if you are using textbook RSA then change CarmichaelLambda() with phi()