Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem Problem statement:
"Bob is a paranoid cryptographer who does not trust dedicated hash functions such as SHA1 and SHA-2. Bob decided to build his own hash function based on some ideas from number theory. More precisely, Bob decided to use the following hash function: $H(m)= m^2\bmod n, n= p\times q$, where $p$ and $q$ are two large distinct primes. Does this hash function satisfy the one-wayness property? What about collision resistance? Explain."
Official solution:
"Since p and q are secret, then finding the square root mod n is a hard problem. Thus this hash function satisfies the one-wayness property. On the other hand, H does not satisfy the weak/strong collision resistance property because for any m, -m would also have the same hash value, i.e., H(m)=H(-m)."
My confusion:
For the one-wayness property part of this cryptographic hash function problem, the solution says that finding the square root mod n is a hard problem since p and q are secret. If, for example, this were the asymmetric RSA encryption algorithm, then that would make sense to me because having p and q could allow you to get the decryption key, but for this hash problem, I don't see how knowing p and/or q would make it easier for an attacker to reverse that modular operation even if p and q were known.
Also, about the collision resistance property part of this cryptographic hash problem, can a file that's being tested for not being tampered with provide a negative value as an input to a cryptographic hash function?
Could someone please help me understand what I'm unclear about?
Any input would be GREATLY appreciated!

Knowing either $p$ or $q$ is sufficient to recover both of them (as $q = n/p$). So imagine we know all of $p, q$, and $n$.
The chinese remainder theorem can be phrased many different ways. In general, it states that when working mod $n$ (where $n$ is a product of distinct primes [1]), you can instead work mod each prime separately. In this particular setting, this means that instead of looking at the equation:
$$H(m) = m^2\bmod pq$$
We can look at the pair of equations:
$$H(m_q, m_p) = (m_q^2\bmod q, m_p^2\bmod p)$$
If we can "solve" one of the sets of equations ($\bmod n$ vs $(\bmod q,\bmod p)$), we can efficiently convert the solution into a solution of the other equation. The second equation will be easier to solve, so will be how we can perform a preimage attack.
In more detail, say you're given a "target" point $c = H(m)$ for some unknown $m$.
Then, we can apply the chinese remainder theorem to convert this into two points $(c_q, c_p)$ for the bottom equation (in particular, $c_q = c\bmod q, c_p= c\bmod p$).
How can we find $m_q$ such that $c_q = m_q^2\bmod q$?
There are known algorithms to do it (see Cipolla's algorithm) which do so efficiently (it looks like it is $O(\log q)$).
So, we can find $m_q, m_p$ that solve the bottom equation efficiently.
Then, we just convert $m_q, m_p$ back into $m$.
This can be computed efficiently, in particular by writing:
$$m = m_q(m_q^{-1}\bmod q) p + m_p(m_p^{-1}\bmod p)q$$
Where $m_q^{-1}\bmod q$ is the inverse of $m_q$ within $(\mathbb{Z}/q\mathbb{Z})^{\times}$, meaning is the modular multiplicative inverse.
So essentially, if we know $n$'s factorization, we can apply the chinese remainder theorem to reduce everything to the case of $\mod p$ where $p$ is prime.
Arithmetic behaves much better in this case, so we can efficiently solve the equation.

[1] One can even apply this to distinct prime powers, meaning an equation $\bmod p^2 q^3$ can be broken into two equations $\bmod p^2$ and $\bmod q^3$. It cannot be broken into 5 equations $(\bmod p, \bmod p, \bmod q, \bmod q,\bmod q)$ though.


Encryption scheme with arbitrary length message Is the definition $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi}^{eav}(n) = 1] \leq \frac{1}{2} + negl(n)$ still valid in case we have an encryption scheme  $\pi (Gen,Enc,Dec)$ with arbitrary length, and the adversary $\mathcal A$ is not outputting equal length messages?

As poncho already wrote in the comments, this isn't possible:

Basically the only way to hide the length of a message is to use a padding, which is long enough.
The adversary knows at least the encryption method and implicitly the length of the padding.
If you allow arbitrary messages, he can choose one message really short (e.g. 1 bit) and the other longer than the padding. If your encryption scheme allows arbitrary length messages, this must be possible, e.g. by a mode of operation (known from block ciphers)

You can't adapt the padding length after seeing the messages chosen by the attacker. Otherwise the information about the length might leak other information about the message again, and then you're going in circles.

edit: Oh, and again you might want to explain notation and security games in the question - even if it doesn't actually matter for this one. Writing down clear definitions might help you see problems on your own.


Correct way to map random number to defined range? Say that we have a secure random number generation that outputs 32 bit random numbers, so it's output is a true random number between 0 and a MAX.

What is the best way to map this random number to a defined range (say I want something random between X and Y) without loosing too much entropy?

Let $m = Y-X$. Generating a random integer in the $X$ to $Y$ range is equivalent to generating a random integer in the $0$ to $m$ range (if you generate $r$, then just use $r+X$). For ease of notation, I assume that the low boundary is included and the high boundary is excluded (you want a random $s$ such that $X \leq s \lt Y$).

In most cases, you cannot get a truly uniform random generation by processing a fixed number $n$ of 32-bit integers. Indeed, $n$ 32-bit integers represent exactly $2^{32n}$ possible outcomes. If $m$ is not a power of $2$, then $2^{32m}$ cannot be divided into $m$ sets of identical cardinal.

The usual method is a rejection process:

Let $u$ be such that $2^u \geq m$.
Let $t = m \times \lfloor \frac{2^u}{m} \rfloor$.
Generate $x$, a $u$-bit value (from your generator of 32-bit integers, just append 32-bit values until you reach the size $u$ or more, and truncate to $u$ bits). We have $0 \leq x \lt 2^u$.
If $x \geq t$ then loop to the previous step.
Return $r = x \mod m$.

The idea of the method is that the $2^u$ range is split into a sub-range of size $t$ (a multiple of $m$) and another sub-range (of size less than $m$). If the $u$-bit value $x$ fall in the first sub-range, then you take it modulo $m$, which yields a uniform value since $t$ is a multiple of $m$. Otherwise, you just discard $x$ and try again. With the constraints above, it can easily be seen that the probability of $x$ falling in the wrong sub-range is less then $0.5$, so the average number of invocations of the PRNG will be less than $2$ (less than two invocations for a $k$-bit integer, which may involve a lot of invocations of the underlying PRNG which produces only 32 bits at a time, depending on your parameters).

Then you have a choice, namely what $u$ to use. One extreme is to use the smallest possible $u$, i.e. $2^{u-1} \lt m \leq 2^u$. This is the choice that maximizes the average number of loops; however, it means that the final "modulo" operation is a no-operation (with $u$ as small as possible, you have $t = m$). For small parameters ($m$ is less then 32 bits), this is often an appropriate choice, because PRNG invocations are usually cheaper than integer division (if you use an efficient PRNG, such as these ones, of course).

The other extreme is to make $u$ much bigger, so that the probability that $x$ falls in the wrong range becomes negligible; at that point, you can often just skip the computation of $t$ and the test $x \geq t$, and proceed directly to the modulo operation: this will imply a slight bias, but a bias lower than what can be detected, let alone be acted upon.

See DSA, annex B.2: for each DSA (or ECDSA) signature, a new value $k$ must be generated for each signature, in the $1$ to $q-1$ range (inclusive), and it must be as uniform as possible. The annex presents the two methods, one with 64 bits of extra space ($u \geq 64 + \log q$), the other with the smallest possible $u$. Which one is preferable is a question of performance and convenience; a DSA implementation (as opposed to ECDSA) must have some code to reduce big values modulo $q$, so using the extra bits is probably simplest; ECDSA implementations, on the other hand, especially hardware implementations which work with binary fields, will probably prefer the "small $u$" method. For security, both are safe.


What does OIW stand for There seem to be many OID's that have been put in the ASN.1 tree that have the following ISO identified organization: OIW.

One example is SHA-1 (ElGamal seems to be another):

id-SHA1 OBJECT IDENTIFIER ::=
       {iso(1) identified-organization(3) oiw(14) secsig(3)
        algorithms(2) 26 }

Can anybody explain what this organization entailed? It seems to have been an OSI workshop where NIST participated with other organizations to set up standards. But there is precious little information to find on the internet.

The SHA-1 standard lists it as the "NIST / OSI Implementors' Workshop". But that seems to be little reason for it to specify SHA-1 in itself.

I'll port the contents of the link of Henrick:

  Within the United States, one key forum for profile collaboration is the Open
  Systems Environment Implementors Workshop (OIW), which is hosted by NIST. OIW
  recently expanded its domain of concerns from communications to the full range
  of Open System Environment issues (interoperability, portability, and consistency of user interfaces, parallel to the IEEE 1003.0 Guide), although no  II specific projects have been defined for OIW yet. OIW is the regional workshop for the Americas, collaborating with parallel bodies in Asia (AOW) and in Europe (EWOS). Together these groups have the authority to forward documents for approval by JTC1 as "International Standardized Profiles," which reflects the ideal status for information infrastructure specification: a coherent suite of well-defined standards adopted by the international standards community.

Not very helpful in itself, but this is the most concise meaning so far (it doesn't make it clear what it actually does or who it consists of at all though).


AES blocks with a counter I would like to send small separate packets of data.

I am thinking of using AES-128 or AES-256, and to add a counter as part of the plain text message.

Some clarifications:
Each message will be one block length.
The transmitter and the received are "counter synched". i.e. the transmitter sends the packet at constant time intervals (once a second), and the receiver expects the known counter on each packet.

Is it a reasonable solution?
Are there any possible security risks?
Since the plain text will not repeat itself, should I still use an IV? or can I omit it?
Should I use a MAC, or is the counter is a sufficient authentication?

1. Is it a reasonable solution?

That's hard to say; for a transport protocol - which is what you are designing - you have hardly described anything at all. Yes, a counter can be used to make messages unique as to avoid replay attacks and introduce randomness when combined with the AES key.

  2. Are there any possible security risks?

Plenty, but with the minimal description - without even a mode of operation or message description, use case, threat model etc. - it is hard to tell which ones would be applicable.

  3. Since the plain text will not repeat itself, should I still use an IV? or can I omit it?

That depends on the mode. If your messages are only one block then you could use ECB mode, which does not require an IV . Otherwise it depends on the mode of operation.

For instance, encrypting a counter in the plaintext message with e.g. AES-CTR will not result in randomizing your ciphertext; in that case you need to use an IV. For AES-CTR, every bit of ciphertext doesn't depend on any of the other bits, so you cannot rely on the message randomizing the ciphertext itself. This is also the case for most authenticated modes of operation (e.g. GCM) as they internally rely on AES-CTR mode for confidentiality.

However, if you put the counter / randomness in the first block of plaintext for AES-CBC then you would be fine, and you could use an all-zero IV.

  4. Should I use a MAC, or is the counter is a sufficient authentication?

No, a counter is not authentication. You need either a MAC or an authenticated mode of operation (assuming you require message authentication, which is commonly the case).

After the edit: sure you can use ECB mode (which is just the application of the block cipher for a single block) to encrypt a plaintext block that includes a counter.

It depends on the size of the counter if you could see the result as authenticated. If the counter is 64 bit then you get 64 bits of security, which could be enough given that you require a new counter each time. If the counter is smaller then I'd certainly make sure that you only allow one (or a few) ciphertext messages.

Furthermore, you should never ever repeat the counter for the same key. Not on restarts, for instance.

Looking at your level of questioning, you're not yet ready to create your own transport protocol. You could have a look at e.g. TLS. There is also a version for packet encryption called DTLS. Or any one of the lightweight transport protocols used for embedded applications.


Security of a security protocol for key exchange, using symmetric-key cryptography This is an exam question:

$A \to B$: Alice, $nonce_A$

$B \to A$: $nonce_B$, $E_{k_{AB}}(nonce_A \| k_1)$

$A \to B$: $E_{k_{AB}}(nonce_B \| k_2)$
Alice and Bob both compute $k_s$ = $k_1$ xor $k_2$

$A \to B$: $E_{k_s}(...)$

$B \to A$: $E_{k_s}(...)$

The protocol is based on a long term secret $k_{AB}$ shared between Alice and Bob.The session, which begins at message 4, is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents ( with $E_{k_s}(...)$ in step 4 and 5 can be anything as long as the protocol satisfy the above requirement).There does exist a flaw in the protocol, can you find it and explain why it constitute an attack on the protocol ?
I can tell that a man in the middle attack doesn't work because $k_1$ and $k_2$ are encrypted so the attacker can not know $k_s$ therefore can not continue to send messages to A and B after the authentication phase.
Another attack I can think of is when $nonce_A$ = $nonce_B$ a Dolev-Yao attacker can pose as B and send A $E_{k_{AB}}$$(nonce_A \| k_1)$ in message 3 then $k_s$ = $k_1$ xor $k_1$ = 0 then the attacker know $k_s$ then he can send message and decrypt message. But the chance $nonce_A$ = $nonce_B$ is very small so I'm not sure if it constitutes an attack.

If we assume that $E$ is just semantically secure, without providing authenticity and integrity of the encrypted message then this scheme is has a huge drawback. It would be possible for an attacker to pose himself as either A or B, or to alter any message send from A to B.

So without authenticated encryption, this scheme may protect against eavesdropping, but not against alteration of messages. Although the attacker won't be able to decrypt messages from the other party, it is possible for an attacker to create an active attack and inject garbage into the messages received by either A or B.

As indicated, many smart cards provide similar key establishment routines, but those schemes use two master keys and two session keys - one for encryption providing confidentiality (symmetric encryption) and one for entity authentication and message authentication (MAC), although a single key and authenticated encryption (CCM or GCM) may also be used for $E$.

Note that above does not constitute a full crypto-analysis of the protocol, it simply points out that $E$ should be an authenticated cipher.


RSA algorithm, relationship of the plaintext $m$ with $p$ I am studying the RSA algorithm. If for example the plaintext $m$ has some relationship with prime $p$, let's say $m$ is multiple of $p$ (where $p$ is the $p$ in $n=p \times q$). Can this give an attacker some information given we know ciphertext $y$ and public key?

So after trying a few examples with small numbers, it turns out that if message $m$ is a multiple of $p$, $m=a\times p$ then $\gcd(y,n)=p$, where y the known ciphertext. The rest is easy to compute.


Is MAC process different for symmetric and asymmetric? Message Authentication Code as far as I know works on the shared secret key. Do they work in the same way. Is there no difference between symmetric and asymmetric processes. Can anyone please explain me from message integrity and authentication perspective?

A cryptographic MAC is always symmetric By Definition.

For those interested in its security properties, one may want to know Does data authenticity always, implicitly, provide data integrity?

The tool that provides authenticity asymmetrically is known as Digital Signature. Digital Signatures are asymmetric By Definition; they guarantees the integrity, authenticity, and non-repudiation of signed messages when the correctness of the public key of the signer is guaranteed.


Why is SIV a thing if MAC-and-encrypt is not the most secure way to go? The question that I am asking is exactly what I ask in the title.

Skimming these three papers should give you an idea (which I list roughly in the order I recommend you look at them):

Rogaway, Philip.  2004.  "Nonce-based symmetric encryption."
Namprempre, Chanathip, Phillip Rogaway and Thomas Shrimpton.  2014.  "Reconsidering Generic Composition."
Bellare, Mihir and Chanathip Namprempre.  2000.  "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm"

To make a long story short, results about generic composition of encryption and authentication are very sensitive to how you define the concept of "encryption."  In a classic textbook definition, encryption schemes are defined in terms of probabilistic algorithms.  As the Rogaway paper puts it:

  Ever since Goldwasser and Micali’s landmark paper [7], formalizations of encryption schemes have usually made the encryption algorithm probabilistic or
  stateful. In this paper we investigate a different formalization for symmetric encryption: the encryption algorithm is made to be a deterministic function, but
  one of its argument is a user-supplied initialization vector (IV). Effectively, the user and not the encryption algorithm is made responsible for flipping coins or maintaining state.

The Bellare and Namprempre's famous result that encrypt-then-MAC is the only secure composition uses the classic, probabilistic framework for encryption.  But if you start from Rogaway's IV- or nonce-based definitions, as the 2014 Namprempre et al paper does, you get more nuanced results.  Some but not all versions of MAC-and-encrypt—including SIV—turn out to be secure, whereas all versions of encrypt-then-MAC are secure.  As the paper puts it:

  One might interpret our results as saying that the conventional wisdom—that Encrypt-then-MAC is the only safe GC method—is wrong, an artifact of early work having admitted sloppy schemes and considered only pE+MAC → pAE conversion. An alternative interpretation is that the conventional wisdom is essentially right, that Encrypt-then-MAC is the only safe GC method, for it works across multiple definitional settings, whereas the story becomes nuanced for other GC schemes.

  Nothing in this paper should be understood as suggesting that there is anything wrong with BN. If that paper has been misconstrued, it was not for a lack of clarity. Our definitions and results are complementary.


Tell where messages begin and end in a series of ciphertext blocks? With block ciphers, I understand that the plaintext is first broken down into the right-sized blocks, padded, and then encrypted into the same number of cipher blocks.

Once these blocks are sent over to the receiver, does this mean that (after decryption) the receiver would have to parse each block looking for the padding in order to be able to tell that the current message has ended and that the next cipherblock belongs to the next message?

Is there a way to mark somewhere how many cipher blocks a given message is, so the receiver would not have to do this parsing on every single cipher block that it receives?

Thanks.

With block ciphers, I understand that the plaintext is first broken down into the right-sized blocks, padded, and then encrypted into the same number of cipher blocks.

Actually, it's a bit more complex than that.  There are some block cipher modes (for example, CTR, CFB) that don't require any padding.  On the other hand, even if the encryption mode doesn't require padding, we usually do want to provide some integrity protection to the ciphertext (so that if someone modifies the ciphertext, we can determine that); we usually do this by dividing the message up, and generating a Message Authenticated Code for each segment (or using a Authenticating Encryption Cipher, which effectively does the same thing); this would also cause us to treat the messsage as something other than a continuous stream (even if, to the application, it might be).

  does this mean that (after decryption) the receiver would have to parse each block looking for the padding

Actually, the receiver wouldn't be able to determine if a particular block is the last block in a message.  That's because we generally allow all blocks but the last to take on any value (so that we can encrypt 128 bits per block with AES); this means that the decrypted plaintext block might take on any value; there's no way that the decryptor would be able to distinguish 'padded last block' vs 'just more data'.

Instead, we generally rely on a noncryptographic higher-level protocol to divide distinct messages.  The use of a higher level protocol means that an attacker can deduce the size of the messages (and the timing); however the cryptographical piece ensures that that's the only thing that an attacker can learn).

One example which might be illuminating is TLS; that breaks up the stream of plaintext into 'records', and individually encrypts each record.  Before each record, it includes (in plaintext) the length of the encrypted record.  Hence, the decryptor knows up front where the last encrypted block is.

This isn't the only way to mark where the start of the next record is; another way is the IPsec approach.  With IPsec, each ciphertext is placed in its own packet; hence where the ciphertext ends is easy (it's at the end of the packet).


Good challenges for a crypto competition for teenagers I'm holding a cryptography workshop for teenagers (around 16 years old) at our university. As part of the workshop, I'm planning to run a crypto competition with prizes: there will be different tasks, each one will yield points, and the winners will get sweets.

However, for the amount of time I'm planning to kill with this game, I still need one or two more challenges. So far, what I have is:

Scytale: one band with letters on it and four potential objects - find out which is the right object so you can read the message and obtain the solution.
Caesar Cipher: Find out by how much the letters have been shifted to get the solution.
A transposition cipher (one where you write the text in a rectangle and then read the columns).
One with frequency analysis (they get the frequency table for the letters and a longer text which I chose to be pretty close to at least the most frequent values).

As you can see, these are all pretty basic stuff that can be done by hand. I don't really want to do anything that would require the kids to do any programming, although I suppose I could do something like install Cryptool2 on an old computer and have that as one station, if anyone has a nice idea that requires computer assistance.

I'm hoping that, among the community of crypto experts and enthusiasts here, some of you may have experience with running such competitions for kids and teenagers, and may be able to suggest some good challenges.  If you've organized something like this before, and know some suitable challenges that I haven't already thought of, please share them!

Perhaps you could do something with Visual Cryptography.
Maybe something like:

Gather a few low-resolution images (symbols or short text phrases), perhaps a few more images than you have kids
Use visual cryptography to split each image into 2 random-looking images, and print each random-looking image on its own piece of transparency paper
Shuffle the pile of transparency papers
somehow let the kids find matching pairs of transparencies that show the original symbol or phrase.

Is there some way to let kids produce Visual Cryptography image-pairs "by hand", without a computer?

Links and further reading:

"What is Visual Cryptography"
online visual cryptography generator
"Visual Cryptography Kit"
visual cryptography example
"Visual Cryptography and Bit-Plane Complexity Segmentation"
XOR with polarized film


Getting the same two hash values for carved files I found I am doing an independent study class for computer forensics, I have to carve the images I've been given. After using scalpel I get a .wav file and .asf file both files play the same songs, and they generate the same md5 hash values. Is this because they are the same file just with .wav and .asf at the end or I am possibly doing something wrong?

It is quite practical to deliberately generate two different files with the same MD5 hash; if you were handed these files by someone else, it is possible that they did this.

However, MD5 will collide only if someone deliberately crafts the files to do so; if you modified the files somehow, then this is unlikely to happen.  Instead, it would be a strong indication that the two files are bitwise identical.


Fixed-points in block ciphers; why don't they indicate a vulnerability? I've seen a few questions here on fixed-points in ciphers, most asking about the possibility and existence. Most of the answers however pointed out that fixed points are not exactly a security threat. Googling about it didn't fetch me much. All I found was this book, which stated it well but does not go on and explain it why!

My thoughts (from an attacker's perspective)

If I find out that the block that I captured is a fixed-point, I know the pText as well as eText for this key. So it'd certainly help me crack it faster (both chosen-plaintext-attack and chosen-ciphertext-attack). Additionally, I know that the number of keys that result in such a fixed-point are very few. So maybe there is a way for me to get the possible keys given the fixed-point.

My assumption was that it'd be easy for the attacker to find out that the captured block is a fixed-point because it retains all of the original message's pattern. Also I assumed that the relation from fixed-point to key is quite obvious.

So it seems this attack is not considered a threat because my assumptions are wrong (one or both). What am I missing?

Intuitively, the reason fixed points are not a problem is the same reason that zeros in a one time pad are not. Because the transform is supposed to be random, a ciphertext that looks like plaintext could be that plaintext... or it could be any other plaintext. With proper encryption they are all equally likely.

  If I find out that the block that I captured is a fixed-point, I know the pText as well as eText for this key.

Yes, but how would you find out that it is a fixed point? By knowing that the plaintext and ciphertext blocks are equal. I.e. this is not additional information.

  Additionally, I know that the number of keys that result in such a fixed-point are very few. So maybe there is a way for me to get the possible keys given the fixed-point.

The number of keys with that particular fixed point depends on the key and block sizes. E.g. with AES-256 you'd expect about $2^{128}$ keys with any fixed point you want. In the case of AES-128 it is true that a fixed point would likely be unique to one or two keys. However, there is no way to exploit that knowledge.

If you know $E_k(x)=x$, you can iterate all keys testing for that. But you can do the same if you know $E_k(x)=y$ for some other $y$. So the fact that it is a fixed point does not make key recovery any simpler, unless the internal structure of the cipher is somehow weak with regard to this fact.

So...

  My assumption was that it'd be easy for the attacker to find out that the captured block is a fixed-point because it retains all of the original message's pattern.

That assumption is wrong, because there are supposed to be many other blocks that produce patterns that aren't in the original message. The probability that $D(x)=x$ should not be higher if $x$ has patterns.

  Also I assumed that the relation from fixed-point to key is quite obvious.

It is not at all obvious. There could be a relation, but that should be considered a weakness in the cipher.


1:1 algorithmic shuffle of massive numerical space For a personal project I'm currently tinkering on, I'm looking for a function which has the following properties:

For any number X in the range 0..MAX, there is a 1:1 random mapping with another number Y in that range.
As long as the key/algorithm remains the same, that mapping should
not change. For every X, there is one and only one Y, and for every
Y there is one and only one X.
Small changes in X should generate massive changes in Y.
Calculating X -> Y should be computationally simple, even for extraordinarily large values of MAX.
Calculating Y -> X should be (effectively) impossible, as should guessing the key.

In non-numerical terms: I'll be encrypting chunks of data (think 4096 bits, maybe more), and expecting an equally-sized unique output chunk for every possible input chunk. Every chunk will always be the same size.
Arbitrary values of X will be converted to Y quite often. End users will be able to choose their value of X at will and see its corresponding Y, across a vast numerical range. Cryptography is not my strong suit, but from my reading this translates as "the algorithm would need to be resistant to chosen-plaintext attacks". The users should never be able to calculate Y -> X, as that would spoil all the fun (to say the least).
A simple visual, for MAX=8:

X
Y

0
7

1
6

2
5

3
4

4
1

5
0

6
3

7
2

So it should be criminally easy to start with X=2 and calculate Y=5, but it should be essentially impossible to guess X=6 from Y=3 without brute forcing.
There were several promising answers here, but it was unclear how secure any of them actually would be given the conditions: https://stackoverflow.com/questions/16398843/unique-int-to-int-hash
My strong preference would be to use an existing and battle-tested encryption algorithm for this, and preferably one which exists in OpenSSL or some other library I can just plug into from Rust, but I've had trouble knowing the right vocabulary to search for what I want (I'm far from new to programming, but very very green in cryptography). It seems from my reading that block ciphers are what I'm looking for, but I have been thrown off by all the talk of IVs and counters and am unsure if CBC/CTR/etc actually work for what I'm trying to do (or if what I'm trying to do is even possible).
Any pointers in the right direction would be greatly appreciated!

There are three major options available to you, depending on the available preferences and guarantees, ordered in descending order of generality:

Format-Preserving Encryption is a class of encryption schemes that can accept arbitrary input spaces and then produce ciphertext from that input space as output. A classical example would be encryption of credit card numbers to encrypted ones that are still accepted by the database solution validating their format.
Wide Block Cipher Modes, e.g. EME* take a bit string of arbitrary length and then compute a keyed pseudo-random permutation on them, their original intended use was disk encryption where you can't store additional authentication data but want to maximize your chances of detecting modification by randomizing the data sector if the ciphertext sector is changed.
Traditional Symmetric Encryption, e.g. CBC mode with a fixed nonce / IV. Note that these suffer from the isuse that changes at bit position $n$ affect at most a constant amount of bits in front of $n$ and at most all bits following $n$ which seems to not be the avalanche effect you're looking for.

If you're wondering, the recommended baseline block cipher for the above constructions is AES.


What is the Discrete Logarithm Problem in (Z/Zp) in the DSA? Literature on the DSA (e.g. Gupta 2014) agrees that the security in DSA relies on the difficulty to solve two distinct discrete logarithm problems (DLP):

One is the DLP in prime-order ($q$) subgroups of $\mathbb{Z}_p^*$ for which the most efficient algorithm is Pollard's rho method. I understand this is basically calculating the private key $x$ given the corresponding public key $y$ for $y=g^x$ mod $p$, and to avoid this we choose a large enough $q$ (e.g. 160-bit).

The other DLP is said to be in $\mathbb{Z}_p^*$ itself, to which the Number Field Sieve algorithm would apply; but I am uncertain what the meaning behind this second DLP is, i.e. what is the exact calculation that we try to do here, and how would it affect the security of digital signatures that are based on subgroups, not the overall $\mathbb{Z}_p^*$?

My initial idea was that it is because the domain parameters are in $\mathbb{Z}_p^*$, but I can't find online sources or literature that goes into more detail regarding this point.

What is the Discrete Logarithm Problem in (Z/Zp) in the DSA?

There is actually only one DLP in DSA. There are multiple approaches to solve it, that can be classified in two categories.

The security of DSA (as defined in FIPS 186-4 section 4) is no better (and equivalent under some models) to the difficulty of the Discrete Logarithm Problem in some Schnorr group. The problem is finding an integer $x$ solution of the equation $y=g^x\bmod p$ for given $p$ defining the group, $g$ in the group, and public key $y$ in the group.

More precisely, that group is a subgroup of $\mathbb Z_p^*$, or equivalently $(\mathbb Z/p\mathbb Z)^*$, for some prime $p$, under modular multiplication, with the subgroup generated by $g$, having as order some randomly seeded prime $q$, and as a consequence $q$ dividing $p-1$. When following FIPS 186-4, $p$ is of L bits and $q$ is of N bits, for one of of these parameters sets:

L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256

This DLP problem can be solved by two classes of algorithms:

Generic algorithms applicable to the DLP in any group of prime order $q$; this includes Pollard's rho and baby-step/giant-step; the cost of the algorithms depends mostly on parameter N (exponentially so, but only polynomialy on L).
Specialized algorithms for subgroups of $\mathbb Z_p^*$, including index calculus and the DLP variant of the General Number Field Sieve; the cost of the algorithms depends nearly only on parameter L (less than exponentially so, but more than polynomialy).


Integrity check of a binary firmware file with hash function I need to provide a mechanism that it is possible to verify the integrity of a firmware image flashed on an embedded system. The procedure should be, that if someone has doubt on the firmware’s integrity, he can read the binary image via a debug port (JTAG) and then compare it against a public available hash code.

The request came from the fact, that the product is used in a custody transfer application and must be therefore protected against tampering (only tampering detecting is enough). There should be an easy way to verify the firmware, like by comparing the hash code, printed in the manual and compare it against the calculated one, loaded from the individual device…

My first approach would be to take for this the commonly used MD5 hash function, also to make it much handier for the customer (only 16 byte or respectively 32 hexadecimal characters). But then I was remembering on some news of the last years about collisions and that MD5 or even SHA-1 are (at least almost) broken. So, I wanted to choose the latest hash algorithm with the best reputation for best future viability and therefore I tended to SHA3-224 (which implicates 28 bytes or 56 hexadecimal characters).

Some colleagues in my company said to me, MD5 should be more than sufficient to cover our needs. But I don`t think this is correct, since we have a 128 KiB Firmware image, with only about 100 KiB are used the other 28 KiB can contain "random data".
Therefore, I would say, this is more than enough to create at least one single collision with the identical programmatically functionality.

Is SHA3-224 an overkill for this purpose or is it reasonable in terms of future viability?

This appears to be an example of an xy problem.

The goal is to ensure that the firmware is not modified. The standard solution to this problem is to use a digital signature. To quote content from the previous link:

  A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it.

With a digital signature, your company (and only your company) can create a signature for the firmware that anyone can verify. If the firmware is modified, then the signature you created will not pass the verification routine.

  There should be an easy way to verify the firmware, like by comparing the hash code, printed in the manual and compare it against the calculated one, loaded from the individual device…

This is not really an "easy" way to verify - most users will not be able/willing to read the binary via JTAG.

Even if they are willing to do so, there is still a possible attack vector: Users might only check if $n$ characters of the two hashes are a match, and then naturally assume that all of the rest will be too. An adversary would in this case only have to produce a partial collision, which could be a much easier task.

It is best to refrain from relying on manual verification.

You can store in the device your public verification key and store the signature next to the firmware. When your device is started, it should be designed to automatically verify the signature before continuing to use the firmware. If the signature does not verify, then operation should be aborted.

RSA is popular* for signatures because verification can be very fast (relatively speaking). Creating a signature is not terribly fast, but since it only needs to be done rarely, it does not really matter how long it takes.

You can use a program such as SSL to create a digital signature, which can be done on any computer.

The verification routine will have to run on your device, so your developer(s) will have to incorporate that functionality in somehow. It may be possible to re-use part of an existing library rather than writing the verification routine from scratch. I would recommend using/porting the code from bearssl if at all possible.

Ideally, your company would contract this portion of development out to an experienced cryptography engineer. If it's possible, it's worth it to have to make sure that it is done correctly.

*In approximately a decade you may have/want to update the signature scheme you use due to quantum computing and NIST's post-quantum cryptography competition.


How does HTTPS transfer the symmetric key? How is the server's public key used to encrypt the symmetric key in a way so that only the sever's private key can decrypt the cipher?

  The client uses the server’s public key to encrypt the symmetric key and send it securely to the server, and the server uses its private
  key to decrypt it. Anyone can encrypt using the public key, but only
  the server can decrypt using the private key.

That depends on the cipher suite. If the master key is encrypted at all then it is usually encrypted using RSA, which can be identified by ciphersuites starting with RSA_. This requires that the certificate that contains the public key allows encryption.

An other way to establish the master secret is by using Diffie Hellman key agreement. This usually is ephemeral-ephemeral key agreement; DHE_ or ECDHE_ ciphersuites. The ephemeral-static key agreements (DH_ and ECDH_) require certificates containing a Diffie-Hellman public key and these are rare.

Nowadays many certificates only allow authentication, not encryption. They are used together with the aforementioned DHE_ and ECDHE_ ciphersuites. In TLS 1.3 the RSA_ ciphersuites are discontinued as they do not provide forward security: if the private key is ever obtained by an adversary then all the data of all the TLS sessions becomes available to that adversary.

Note that there are even other ways of authentication possible. The method of using RSA encryption is mainly used for older versions of SSL and TLS. So that description you have is 1. completely over simplified and 2. outdated. Read the TLS 1.2 specification if you want to know more.


Where can I find test vectors for ciphers? While implementing ciphers and hash functions, I often face a problem: where to find test vectors for it; so that I can guarantee my program is working correctly. It is generally a tedious job to find test cases.

Currently I am trying to gather test vectors for several ciphers and hash functions; including (but not limited to):
RC4, all ciphers from eStream, DES (round-wise, if possible), 3DES, AES, …

To avoid looking in the wrong places: Where can I find test vectors for ciphers?

For a head-start, I put test cases of RC4 (correct me if I am wrong):

Key        (255, 255, 0, 255)
Keystream  23, 0, 135, 229, 197, 74, 253, 202, 72, 83, ...
Key        (0, 0, 0, 255, 127, 31)
Keystream  40, 172, 142, 137, 101, 124, 164, 50, 0, 172, ...

Related:

Test vectors for PRESENT algorithm?
Where are the ChaCha20 test vectors/examples?

For any of the algorithms approved by NIST you can usually find the test vectors in the Cryptographic Algorithm Validation Program (CAVP)  - for instance for 3DES in appendix B and AES in appendix C. Test vectors are usually found in one of the appendixes or later sections of the documents.

For any others you should first look to the standard documents, preferably RFC's - for instance for RC4. If the standard documents do not contain test vectors then take an addition look at the company or organization; they often would have a separate document with test vectors. Some standards, such as the PKCS standards may also be referenced or copied by other standards, so if you cannot find it in one document you may want to look for copies. In general, cryptographic competitions require the submitter of proposals to include test vectors.

If you cannot find it that way you will have to rely on Google, or a forum such as this one. Or you could take a reference implementation and test your implementation against that. If that is not available, try and generate them yourself from the leading implementation.

Official test vectors are not always available, even in this day and age. If they are, they may not be complete in the sense that they would cover all possible code paths. Never just test against test vectors and think your implementation is sound or secure if they succeed; provide good coverage and remember to test your own corner cases.


Do Carmichael's and Euler's totient functions in RSA generate the same keys? Starting with the same primes $p$ and $q$ to generate $n=pq$, will Carmichael's totient function and Euler's totient function give the same public key ($e,n$) and private key ($d,n$) in RSA encryption?

If not, are there specific types or range of primes $p$ and $q$ that result in the difference?

THANK YOU!

There is no standard definition of "same" when applied to cryptographic keys.

There is a precise definition of equivalent keys: keys which always yield the same effect when used for their designated usage, e.g. encryption, decryption, signature generation or verification. For example, in DES, low order bits of key bytes play no role, thus 0123456789ABCDEF (in hexadecimal) is a key equivalent to 0022446688AACCEE, if the later is considered valid. In TEA, 0123456789ABCDEF0123456789ABCDEF is equivalent to 8123456709ABCDEF8123456709ABCDEF.

In RSA, Carmichael's and Euler's totient functions generate equivalent keys, even though (in the variant of RSA where the private exponent $d$ is generated from the public exponent $e$) the resulting values of $d_\lambda=e^{-1}\bmod\lambda(n)$ and $d_\varphi=e^{-1}\bmod\varphi(n)$ often are not equal. Example:$$\begin{align}
n&=5\times11=55\quad&e&=3\\
\lambda(n)&=\operatorname{lcm}(4,10)=20\quad&d_\lambda&=7\\
\varphi(n)&=4\times10=40\quad&d_\varphi&=27
\end{align}$$

In the (original) variant of RSA where the public exponent $e$ is generated from the private exponent $d$, we'd often have different $e_\lambda=d^{-1}\bmod\lambda(n)$ and $e_\varphi=d^{-1}\bmod\varphi(n)$.

Note: we do not even have a universally accepted definition of equal keys. Are two DES keys represented as 16 characters 0123456789ABCDEF and 0123456789abcdef equal? Does LF vs CR/LF matter in RSA keys as PEM files?


AES ECB deterministic encryption to perform Private set intersection There are two parties, and each has a list of plain-texts. My end goal is to assign indices to unique plain-texts across both parties. My present approach is the following.

Both parties perform a Diffie-Hellman key exchange to generate a secret key (which is the same for both workers).
Then they encrypt the plain-texts using AES in ECB mode using the secret key.
The set of encrypted plain-texts is brought to my local machine. (Note that I bring a set, thus each encrypted text returned by a given party is unique.)
I compare them and assign unique indices to each of them.

The deterministic property of ECB mode, plays an important role here, as it helps to compare similar plain-texts encrypted with the same key.

But I understand (after reading multiple answers about it) that ECB mode has many weaknesses. For example, two plain-texts longer than 16 characters, having the same characters after the 16th character will have the same ending block in the encrypted text. The same logic applies to the first 16 characters as well.

I want to know, if there are other ways in which I can extract information about the plain-texts of both parties, by analyzing the encrypted texts returned by them to me.

And is there any other more secure way to achieve my end goal?

Yes, there is a more secure way to achieve your goal. For uniqueness you can use SIV mode with a static nonce. SIV mode first calculates a MAC over the plaintext and then uses that as IV to the mode of operation. This means that identical plaintext will result in identical ciphertext, but that plaintext that only differ by a single bit will result unrelated ciphertext. That way the leakage when identical blocks are used in the plaintext is avoided. SIV has the advantage that integrity / authenticity of the message is protected as well.

SIV has the disadvantage that it requires an authentication tag to be included, to achieve the aforementioned integrity / authenticity. This authentication tag then doubles as IV vector for the internal cipher (hence the name: synthetic IV). If you for some reason does not have the space to store the authentication tag then you may need to look at Form Preserving Encryption of FPE.


Why are there $q^2$ keys for each equivalence class in Pedersen-van Heyst Signature Scheme? How do you know there are $q^2$ keys for each equivalence class in the Pedersen-van Heyst Signature Scheme? My textbook says this is "easy to see", however, I am not seeing it.

Is it because in the signature  $Sig_K(\gamma_1,\gamma_2)$, the parameters $\gamma_1$ and $\gamma_2$ are both elements in $\mathbb{Z}_q$?

I did not know the scheme, so I had to google it to find the missing part of its description - here it is, in case someone else wants it.

So, two keys are in the same equivalence class when they have the same $\gamma_1$ and $\gamma_2$, id est, when $\alpha^{a_1}\beta^{a_2} = \alpha^{a'_1}\beta^{a'_2} \bmod p$, and $\alpha^{b_1}\beta^{b_2} = \alpha^{b'_1}\beta^{b'_2} \bmod p$, with $p = 2q+1$. Note that the exponents of $\alpha$ "live" in a cyclic group of order $q$ (as I do not know how familiar you are with cyclic groups, I assume this statement is clear for the moment, don't hesitate to ask if it is not the case). If we denote by $s$ the discrete logarithm of $\beta$ in base $\alpha$ modulo $p$, we can rewrite the "same $\gamma_1$ and $\gamma_2$" condition as follows:

$a_1+ sa_2 = a'_1 + sa'_2 \bmod q$ and $b_1+ sb_2 = b'_1 + sb'_2 \bmod q$

Now it should become more clear to you: we have exactly two equations modulo $q$, and four variables ($s$ is uniquely determined by $\beta$ given $\alpha$), hence exactly $q^2$ solutions. Does that make sense to you ?

EDIT: regarding your last question, $\gamma_1$ and $\gamma_2$ are group elements, they are in the group of order $p$. Only the exponents (which correspond to the secret key, $\gamma_1$ and $\gamma_2$ being the public key) are elements of $\mathbb{Z}_q$.


Highest prime factor that is Safe for a particular scheme My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number?

Quantum computing find highest factor of size of 16 bits only( 56,153) until today  and I studied that rsa-768 in which 384 bits prime number  is factored from large number. Why different schemes takes very large prime, when even two 1000  bits prime number cannot be factored from 2000 bit large number  until today?
Thanks.

There is some confusion here. The definition of prime numbers states that cannot be factored (see Definition of prime numbers)

You seem to be talking about RSA modulus which is the product of two prime numbers (see RSA cryptosystem).

As far as keylength is concerned 768 bits is not considered safe today. Note that the keylength choice is a compromise between speed and security, basically we're trying to estimate the shortest keylength that is beyond the cryptanalytic capabilities of any attacker (that needs to stay true as long as the data is valuable). Since we base that estimate on the best publicly known attacks against the cryptosystem (namely here factoring) running on publicky available hardware we add a cushion to take into account increase in computing power, entities that know or will know more than we do.

To answer your question, new RSA public keys should be at least 2048 bits long so slightly larger than your 1600 bits initial proposal here. For further reference you can refer to the keylength website.


What's the reason for applying the hash twice when hashing with salt? One of the typical approaches to computing a salted hash is this:

hash(salt+hash(secret))

where hash is something like SHA-256 hash function - taking any size input and returning fixed size output. What's the need for the hash(secret)?

Why can't I just do this:

hash(salt + secret)

where + is simply concatenating two byte arrays?

This construction has two advantages over a plain hash of param1||param2:

It's immune to length-extensions
You can't get collisions of the form param1=A||B param2=C vs. param1=A param2=B||C.

But neither of those is relevant to password hashing, so it doesn't offer any advantage there.

The construction looks like it's inspired by HMAC:

$$ HMAC(K,m) = H((K ⊕ opad) ∥ H((K ⊕ ipad) ∥ m)) $$

But of course for password hashing one would not use such fast hashing constructions. Correct choices are scrypt, bcrypt, and PBKDF2. These have a designated salt parameter, so they don't need such an ad-hoc construction to mix salt and password.

This system has one big advantage though: You can upgrade existing hashes to it, without knowing the plaintext password. Essentially you treat $ hash(pass) $ as the new password. When upgrading an old system from a plain, unsalted hash, I'd use something like:

$ PBKDF2(LegacyHash(password), salt) $


Block ordering and security in a MAC? To authenticate a message $m = m_1 \,\|\, \dots \,\|\,m_n$ the tag $t := F_k(r) \oplus F_k(m_1) \oplus \dotsb \oplus F_k(m_n)$ is used, where r is uniform random number $(0,1)^n$ and $m=(0,1)^n$. Even though the random number is prepended to the sequence there is still a chance of reordering the message blocks which makes it insecure.

I am confused whether the blocks changed by an attacker make it insecure or not?

The usual meaning of "secure" for a MAC means that an attacker has no chance to forge a message not originally sent by the sender, without knowing the private key.

So, assume there is a message $ABCDE$ (where each letter corresponds to one $n$-bit block). This will be sent as $rABCDEt$. If an attacker captures this message, she can reorder the blocks to create a second message $rBDCEAt$, and if you look at your formula, the tag for $BDCEA$ is exactly the same as the one for $ABCDE$, thus this mangled message will still validate as authentic.

Thus, in the formal sense this proposed MAC scheme is not secure. Whether it is a problem in practice depends on what kind of data you are sending. If each block is a sub-message which makes sense of it own independent on the order of the blocks, then it might still be enough.

But as there are better MAC schemes which actually take the order of the blocks into account, use these instead.


Encrypting/Decrypting sensitive information for storage purpose I want to store account numbers and routing numbers into SQL database, and i was looking for best way to encrypt/decrypt this sensitive information. After researching i found i can use symmetric (like AES) or asymmetric (like RSA, X509 Certificate) algorithms. I just want to encrypt/decrypt the information locally
on the server and store it into SQL DB. Is it recommend to use AES with 128 bit HEX key for such purpose?
Use of asymmetric algorithms seems to be overkill since encryption/decryption will happen locally on the same server.

(Note that this information will ultimately transfer to vendor using SFTP, however during that transfer we will be using vendor provided PGP public key for encryption so vendor can decrypt it. What i am looking here is encryption/decryption for local storage)

First, you should carry out a threat analysis and determine the attack scenarios that the encryption is supposed to protect you against.  Without such an analysis, all you're doing is sprinkling magic crypto dust over your database and hoping that it will somehow protect you from any and all possible threats.  (Spoiler: It probably won't.)

For example, some more or less plausible threats might include:

a remote attacker gaining access to the database via SQL injection;
a remote attacker gaining access to an entire server, including all data and keys stored on it, via a remote code execution (and/or privilege escalation) vulnerability;
a remote attacker guessing the password to a privileged account;
an employee with physical access to the servers carelessly disposing of a disk that used to contain sensitive data;
a privileged employee carelessly copying sensitive data to an insecure or publicly accessible location;
a privileged employee maliciously accessing or modifying sensitive data; and/or
a privileged employee's workstation being infected with malware.

Encryption can protect against some of these threats, but not all of them, and the extent to which it can protect against some of those threats depends on the degree of compartmentalization (e.g. separating publicly accessible services onto dedicated servers, implementing strict firewall rules, requiring secure multi-factor authentication for all accounts, storing active encryption keys in a hardware security module, splitting inactive master keys into multiple shares and storing them in separate locations, etc.) that you're willing to implement and endure.

Of course, it's also possible that your sole proximate reason for encrypting your data is to pass a certification that requires it.  In that case, you may wish to review the certification standards and determine what they require of your encryption and what threats they expect it to counter.

Depending on your specific requirements and threat model, it's possible that your need for encryption of data at rest might be sufficiently served simply by activating built-in encryption features of your database software, or even just by storing the database on an encrypted disk.  If so, that's certainly the simplest option, even though it protects only against a limited set of attacks.

Database front-end such as CryptDB may also be useful, although again, you should carefully review their ability to protect you against the threats you've determined to be relevant while still providing the access to the data that you need.

If you must implement your own database column encryption, and if symmetric-key encryption is sufficient for your needs, I would strongly recommend using AES-SIV (or possibly AES-GCM-SIV).  If you don't need to do equality comparisons on the encrypted fields, use SIV with a unique random nonce for each field (and consider including the table and column names and the row's primary key as associated data).  If you do need the ability to compare encrypted fields for equality without decrypting them, use SIV without a nonce (but preferably still with the table and column names as associated data).

(If you find yourself wanting to do any kind of searching or comparisons on encrypted data besides simple equality comparison, I would strongly suggest reviewing your design and trying to find an alternative solution.  While there do exist various "order-preserving" and/or "searchable" encryption schemes that claim to provide this functionality, they do not — and fundamentally cannot — meet the level of security normally expected of a modern encryption scheme, as the ability to perform such comparisons unavoidably leaks information about the encrypted data.  Even nonceless SIV should be used with caution, since it leaks the equality of encrypted values.)

In some cases, e.g. if you want your server to be able to add new encrypted values to the database but not to be able to decrypt existing data once it has been added, you may want to use a public-key encryption scheme.  In particular, you will probably want a hybrid cryptosystem such as ECIES, where the public-key part of the system is used to generate and encrypt a random symmetric cipher key, and this random symmetric key is then used to encrypt the data itself.  The main disadvantages of such systems compared to AES-SIV are their extra complexity and their higher overhead costs (both in terms of processing time and storage requirements).  Their main advantage, of course, is that the confidentiality of the data is not compromised even if an attacker gains access to the public encryption key.


OTP with fixed plaintext I have just learned about the OTP, how it uses XOR, and how it's secure if the keys are random.

But what will happen when the same plaintext is used again with a new key?

$c_1 = k_1 ⊕ p$

$c_2 = k_2 ⊕ p$

$c_3 = k_3 ⊕ p$

$c_n = k_n ⊕ p$

Is this secure?

If the keys are all independent and near-uniform random, then an chosen-plaintext attacker has near-zero advantage in the IND-CPA game.

In the IND-CPA game, the attacker can ask for the ciphertexts of any plaintexts of their choice (CPA, Chosen-Plaintext Attack), and then submits two challenge messages, and, given the ciphertext for one of challenge messages, wins the game if they can tell which one (IND for indistinguishability).  The attacker's advantage is their probability above 1/2 of winning this game.  This is the standard notion of security for an unauthenticated cipher.

Of course, this only thwarts an eavesdropper who can listen but not touch the messages.  A MITM could easily transform one ciphertext into another, forging messages without raising any alarms, even if they can't learn anything about the plaintext given the ciphertext—they may know a priori what the plaintext will be and may want to replace it by something else.

So this is usually not enough security for applications that involve, say, the internet: you need an authenticated cipher for that, for example a one-time pad with a one-time authenticator appended, which is the model that AES-GCM and NaCl crypto_secretbox_xsalsa20poly1305 make practical with short keys expanded pseudorandomly into message-length pads.


Can I use `SHA (message || key)` as MAC? One should not use SHA for MAC, because knowing SHA(key || message) and message you can construct SHA(key || message || forgery) without knowing the actual key. I read somewhere that one shouldn't use SHA(message || key) as MAC. Why? Here || means string concatenation.

If you know a length-preserving collision, that is, two distinct messages $M_1, M_2$ of the same length with $\operatorname{SHA}(M_1) = \operatorname{SHA}(M_2)$, then you know apriori that two messages $M_1 || \text{Pad}(M_1)$ and $M_2 || \text{Pad}(M_2)$ (where $\text{Pad}$ is the SHA padding function) will evaluate to the same value (and hence the MAC is broken).

This immediately shows that this MAC is insecure if instantiated with SHA-1.


Can reduced-round ChaCha be used as non-cryptographic fast PRNG to produce output indistinguishable from random data? The fastest known attack against the Salsa20 family of stream ciphers requires 2137 simple operations against Salsa20/7, or 2244 against Salsa20/8. The 8-round version encrypts data at 1.88 cycles-per-byte on a Core2Duo, which is already extremely fast. As there's no real key schedule, cutting this down to two rounds should bring the speed up to 0.47 cycles-per-byte.

ChaCha is based on the Salsa core, but improves diffusion per round (quite significantly, as an attack taking 232 operations on Salsa20/6 instead takes 2127.5 operations on ChaCha6). The speed on the same CPU is equivalent. This is as fast as XorShift128+ (0.48 cycles-per-byte on Kaby Lake). Even worse for XorShift128+, the lowest bit is an LFSR, which may not be ideal for certain use cases such as Monte Carlo simulations.

This leads me to wonder, in situations where cryptographic security is not needed, could two-round ChaCha be used in place of another, fast PRNG? Would the output be indistinguishable from random data, sans cryptographic attacks?

As cypherfox had correctly pointed out during our chat, two rounds is not enough to reliably diffuse a single changed bit throughout the entire output.
My question appears to have been answered directly by Bernstein's page on diffusion for Salsa20 (note that ChaCha has better diffusion).
Quoting https://cr.yp.to/snuffle/diffusion.html

The following pictures show how quickly changes in one byte of Salsa20 input spread through the entire Salsa20 array. Here's a typical Salsa20 input array, with a superposition of 256 possibilities for the first byte in the third row:

After one round:

After two rounds:

After three rounds:

After four rounds:

…

Additionally, the paper on Salsa20's security gives an example of diffusion:

Consider computing the second block of the Salsa20 stream cipher with nonce 0 and key (1,2,3,...,32). Rather than displaying the arrays produced by the second-block computation, this section displays the xor between those arrays and the corresponding first-block arrays, to emphasize the "active" bits—the bits where the computations differ.
The Salsa20 hash function starts with a 4×4 input array who's only difference from the first block is the different block counter, as shown by the following xor:
0x00000000,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
By the end of the first round, the difference has propagated to two other entries in the same column:
0x80040001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x0000e000,0x00000000,0x00000000,0x00000000
At this point there are still just a few active bits. The difference depends on a few carries but is still highly predictable.
The second round then propagates the difference across columns:
0xedc5e0a9,0x020000c0,0x381f830c,0x304888dc
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00006000,0x800c0001,0x00000000
0x0000e000,0x01c00000,0x040000d8,0x01200f00
By the end of the third round, every word has been affected:
0x39545d5e,0x0cc160d8,0x301fb030,0xa05208dc
0xa240cc8b,0x24e0120c,0x2a030dc7,0xabeeb94e
0x39ea409b,0x0000000f,0xcf3bb828,0x1c205f6d
0xc6612ba5,0x01c06a00,0x02000018,0x6745c36b
A substantial fraction of the bits are now active, although two words still have stretches of bits that were not (and were unlikely to be) active.
By the end of the fourth round, those last two stretches of inactivity have been eliminated:
0xf5eebb6a,0x79a3e194,0x52e3644f,0x28fc33dd
0xcbfe2c2e,0xa0ce9f57,0xfa23cf02,0x2f549d35
0x2b1af315,0x7af4976b,0xa100a15f,0x86f420f1
0x2900cc14,0x8dcbf124,0x90611242,0x61fdabbe
That's just 4 out of the 20 rounds in Salsa20. In every subsequent round, there are hundreds of active bits, for a total of more than 4000 active bits. Each of those 4000 active bits interacts with carries in a random-looking way, producing random-looking differences, not shown here.

Clearly, no less than 4 rounds can be used to safely achieve full diffusion. At this point, Salsa20/4 is no longer competitive with other fast PRNG alternatives. I'll additionally update my answer with the results from Dieharder tests later, when I have time. I will also test ChaCha.


Any point using CMAC with AES-256? As we know, AES-256 is a block cipher with 256-bit key and 128-bit block size.

The CMAC message authentication code outputs tag length equal to block cipher block size - thus 128 bits with AES. And this provides an assurence that only 1 in 2^128 attempts in forgery may possibly succeed.

So is there any point using a 256-bit key as may be the case with AES-256?

Brute forcing ciphertext an offline attack, while attacking the authentication tag (the result of the CMAC-calculation) is an online attack: it requires an active oracle. That is: you can try and break the confidentiality of a message on your own PC network of computers. However, you need to send many ciphertext (including authentication tag) to a receiver to see if a guessed tag is correct or not and an invalid ciphertext is accepted (to test if a message is successfully forged). Generally you only get one oracle, and the speed of this oracle is usually limited (e.g. by networking speeds).

If an authentication tag is not accepted then that doesn't give any information to an attacker if the next message changes. This would for instance be the case if a unique sequence number is included in the messages (although usually the authentication tag is verified earlier, so oracle attacks would be possible). Furthermore, many protocols will break a session and re-establish the session keys if an incorrect authentication tag is received.

In conclusion: attacking an authentication tag is much harder than breaking a cipher, even if the order of the attack is the same. Because of this it makes sense to increase the key size even if the tag size stays the same.

If you need more than 128 bits of security is of course another question; 128 bits seems plenty as long as quantum computers are not available. 256 bit encryption should be considered for messages that require long-term protection.


Ciphertext packing for bandwidth optimization Let's say $Alice$ needs to send ciphertext $c_b = enc(m_b,k_b)$ to $Bob$ and ciphertext $c_c = enc(m_c,k_c)$ to $Carol$. For both the ciphertexts notice that underlying plaintexts are different (i.e. $m_b, m_c$).

Now imagine a single envelope needs to be sent to both $Bob$ and $Carol$ where both can decrypt and get their respective plaintexts $m_b,m_c$.

The trivial way is ($c_b | c_c$) (i.e concatenation) and use some delimiter for Bob and Carol to extract bits and decrypt respectively. But this needs bandwidth $|c_b| + |c_c|$.

Can we optimize this to use lesser bandwidth? Can such a thing exist at all?

If $m_b$ has size $n_b$ bits, then there are $2^{n_b}$ possible messages $m_b$; and they MUST be all "possible" in the eyes of outsiders (including Carol). Similarly, there are $2^{n_c}$ possible messages $m_c$. Thus, there are $2^{n_b}\times 2^{n_c} = 2^{n_b+n_c}$ possible inputs to your problem.

If you have a system that can encrypt all such inputs into a sequence of $t$ bits, then there are $2^t$ possible output messages, and, from each such message, Bob and Carol can unambiguously extract $m_b$ and $m_c$, respectively -- if they work together, they will get both $m_b$ and $m_c$, unscathed. This implies that the encryption system must be injective: if $(m_b, m_c) \neq (m'_b, m'_c)$ (the message for Bob, the message for Carol, or both, are different), then they must encrypt to a different sequence of $t$ bits. Otherwise, it would not be possible to decrypt the result unambiguously.

Therefore, $2^{n_b+n_c} \leq 2^t$. This means that you cannot do really better than concatenation, in all generality.

Now, if you suppose that your messages are "real world data" with a lot of internal structure and redundancy, then you can use data compression to reduce the size of the plaintexts. Data compression, on average over uniformly random input bits can only increase data length, but on "meaningful" data it can be quite successful. Unfortunately, data compression makes data length depend on data contents, and encryption, as a rule, does not hide data length, so compression is a recipe for data leakage.

In your specific case, you could also envision a compression scheme that exploits the similarities between Bob's and Carol's messages: split $(m_b, m_c)$ into three parts $(s_b, s_c, d)$ where $d$ is the part which is common in $m_b$ and $m_c$, $s_b$ is the part specific to $m_b$ and $s_c$ is the part specific to $m_c$. Then you can encrypt $d$ only once with a symmetric key $K$, and encrypt $K$ with the public keys of both Bob and Carol. Depending on the structure of your messages, this may save a lot of space. However, it also reveals to Carol a chunk of the the message sent to Bob; and even outsider can know how much data is shared between the two messages.


Embedding a secret private key in a homomorphic encryption system Is there a way to create a homomorphic encryption function F such that given an input it would produce an output and also cryptographically sign the input and output? More formally, an F such that: F(x, S) = y | sig(x | y), where:

x is the input
S is an optional publicly known "helper" state
y is an output of some computation
| is concatenation
sig(x | y) is a signature of x and y, with a secret private key
Anyone can verify the signature according to the public key, but no one knows the private key, and therefore no one can generate the signature without running F. Hence the signature proves the correctness of y for the given x.

Optionally, the state S can be created in an initialization phase using a secure multi party computation (MPC), so the parties could figure out the private key but only if they all collude.

The idea is that given some x, someone could run F(x) and then give { x, y, sig(x | y) } to verifiers, proving the computation was done correctly without needing the verifiers to run the computation themselves.

"Is there a way to create a homomorphic encryption function F such that given an input

it would produce an output and also cryptographically sign the input and output?"

Sure.  Just let signing key and verification key be part of the homomorphing information.

"Anyone can verify the signature according to the public key,

but no one knows the private key"

Change the signature scheme so that the signing key includes a random part,

which neither the signing algorithm nor the verification algorithm use,

and leave that part out of the homomorphing information.

", and therefore"

The part just after that quote does not follow from what's before that quote.

"no one can generate the signature without running F."

gets into parallelism-resistance without the

"generating a puzzle should take less time than solving it." condition,

and/or quantitative things that mainly apply to password-hashing.

Your stated idea would have complexity-theoretic consequences;

namely, showing that non-uniform MATIME is unexpectedly powerful.

It seems like you'd be interested in publicly-verifiable SNARGs.

(Note that they are arguments, not proofs.)


Should I calculate SHA-256 hash of a raw bytes of a token or it's hex encoding? I have a system where I should generate a secret token for a user. The presence of a token is sufficient to grant access to some user-related data.
I am generating a 4096 bit token from a cryptographically secure random number generator. Internally I'm handling the token as a string, encoded to hex. Token is hashed using SHA-256 and this is stored in the database, hex string representing the token is sent to the user and never stored.
When the user presents the hex string of the token, I calculate its SHA-256 hash and look it up.

Question is: am I sacrificing something by calculating SHA-256 of the hexadecimal encoded string vs calculating the hash of the raw byte payload? I'm writing this in Go, so I'm really calculating the SHA-256 hash of []byte(str) which converts the string to byte array.
I have this feeling I'm comparing apples to oranges to melons perhaps.
Should I perhaps get the hex encoded string from the user, convert it to byte array, hash that using SHA-256 and then use that?
Question 1-a: Do things change if it's base64url instead of hex?

The encoding doesn't change the output of the entropy source. They are reversible operations. You can use what encoding suits you, change to base64 for transmission and strong on the database, and change to byte is a good choice since, in general, the cryptographic hash functions are accepting bytes to process, so it might better to convert them bytes before applying SHA-256 so that you can get the benefit of the speed of the SHA-256. Base64 or Hex may need more time to hash the same data due to the increase in the length, that is $~3n/4$ in Base64, and $2n$ in Hex for $n$ bytes.
If the CSPRNG has good entropy then you even don't need the SHA-256, or at least 4096-bit token, hashing the output of the source is a good idea, however, if the source needs 4096-bit to produce good 256-bit randomness, there might be a problem there. This, however, really depends on your CSPRNG.


Can a PRNG be made into a CSPRNG by hashing the outputs? So I was contemplating this answer to my last question, and it got me thinking:

If I understand it right, one of the required properties of a CSPRNG is that it resists leaking information about its internal state from the outputs it produces.

So say we have a PRNG that meets all other properties of a CSPRNG (I do not yet trust myself to know what all those are), but is suspected of leaking too much of its state in the outputs.

My intuition is that we can maybe make it a CSPRNG by running its outputs through a hashing algorithm already known to be suitable for cryptography.

An example: say the PRNG has 128 bits of state, and produces 128-bit numbers as its output. If I were to, say, run it 8 times, I would have 1024 bits. Say I then feed that into SHA-512/256 or similar, and return the two 128-bit pieces of the digest as the new outputs.

So in this example I get two outputs of my new composed PRNG for every eight runs of the underlying PRNG. This might be less efficient than a proper CSPRNG, and might have washed out whatever other properties the PRNG might have had. But is it now a CSPRNG?

I suspect the answer is either "no" or "only if the original PRNG [...]" or maybe at best "the general gist is in the right direction but your specific example would not be because [...]", or some combination of those.

I also know that naive attempts to compose primitives like this without proper understanding can actually cause other problems.

It just occurred to me that some operations, like XOR and the hashing functions used in cryptography, can "destroy" information, in the sense that more than one possible input can produce the same output, while still retaining the right "randomness" properties.

That naively seems like what we need to reduce how much a PRNG's outputs reveal about its state, and I'm looking for some check if that is right or in what ways it is wrong.

And it seems like "can I turn a PRNG into a CSPRNG by running a secure hash on all of its outputs?" is a good question to explore at least some of that.

No, the question's construction is not guaranteed to turn a PRNG into a CSPRNG. In some cases, the hashing worsens the generator. In more, undesirable characteristics remain detectable after hashing. There are better methods to build a CSPRNG from a hash.

The question's construction, hereafter WBCSPRNG for Would-Be Cryptographicaly Secure Pseudo RNG, is a PRNG with the same input characteristics and state size (within a few bits depending on how that's counted) as the original PRNG. It has a period demonstrably not smaller than the PRNG by a large factor (at worse 1024/256=4) under the hypothesis that the hash behaves as a random oracle. I do not see anything else comforting that can be said unless we add some hypothesis about the PRNG.

In particular, we can devise a PRNG, with a large state and long period, such that the WBCSPRNG fails most existing PRNG test suites, when the original PRNG consistently passes them. Start from a good CSPRNG, and modify it so that after having output 1023 bits, the next bit is produced by hashing these and a zero bit, summing the 256 bits yielding $b\in[0,256]$, outputting zero if $b<128$, one if $b>128$, and the low-order bit of the hash otherwise.

Our constructed PRNG is no longer a CSPRNG, but still pass any pre-existing RNG test (no pre-existing RNG test will catch how the extra bit is generated). Yet the WBCSPRNG is biased towards zero, and most RNG test suites will detect that.

The above counterexample is maliciously constructed, and in a way that  needs to know the hash, which we could forbid. That's not good enough: a whole class of accidental defects are amplified. For example, if a PRNG has the undesirable characteristic that the first 1024-bit block of each 242-bit output block is identical, the WBCSPRNG has the characteristic that the first 256-bit block of each 240-bit output block is identical, which is likely to cause issue sooner.

The hypothesis when academically evaluating the security of a CSPRNG is that its design is public, here including the WCSPRNG's hash step and the PRNG. If the PRNG has the characteristic that a class of 1024-bit blocks are likely to appear in its output, that again can be detectable in the WCSPRNG output, after testing 4 times less bits.

The method has no practical interest as a way to construct a CSPRNG, for we do not need a PRNG to make a CSPRNG out of a hash such as SHA-512/256, and one more efficient than the question's one: we hash the seed input, set a counter to that, then to produce 256 bits of output we hash the state then increment it.


How can the Diffie-Hellman key exchange be extended to three parties? Possible Duplicate:
  Can one generalize the Diffie-Hellman key exchange to three or more parties?

How can Alice, Bob, and Charlie share a common secret key using an extended version of the Diffie-Hellman key exchange protocol?

a=3, b=4, c=5
g=2
p=5

Alice computes $A=g^a$, Bob computes $B=g^b$ and Charlie computes $C=g^c$.
$A,B$ and $C$ are published.
Alice computes $AC=C^a$ and $AB=B^a$ and Bob computes $BC=C^b$.
$AB,AC$ and $BC$ are published.
Alice computes $ABC=BC^a$, Bob computes $ABC=AC^b$ and Charlie
computes $ABC=AB^c$.
Everybody shares $ABC=g^{abc}$.

This can be generalized for any number of participants in a tree construction, however it becomes increasingly inefficient, because the number of rounds increases.


Diffie-Hellman: Recommendation of the base size? Based upon choosing a prime $p$ of recommended length and $N=2p+1$, where $N$ is also prime, and $a^2$ is not congruent to $1 \pmod N$, and $a^p ≡ 1 \pmod N$, I believe you can rely upon $a$ as having order equal to $p$.

My question is, what is a good size for $a$? And the reason I ask is because I've heard that you want the base large enough so that most of the power possibilities exceed $N$. What I'm looking for is more formal requirements or an example that provides $p, N, a$ using current recommendations.

The standard approach is to use $N \equiv 7 \pmod 8$ so that $a = 2$ has order $p$ by virtue of being a quadratic residue, e.g. in the RFC 3526 groups, chosen by the deterministic procedure described in RFC 2412, Appendix E.  Using any other groups for finite-field Diffie–Hellman raises a lot of eyebrows.

Uniform random exponents of the usual size have negligible probability of being small enough to admit their recovery by real number logarithm computations: even for $a = 2$ and $N \sim 2^{2048}$, the probability of a 256-bit exponent admitting this attack is about $2^{11}/2^{256} = 2^{-245}$ which is a technical word for ‘not gonna happen’.

Of course, you should just use a modern system like X25519 instead of finite-field DH anyway!  Faster, safer, simpler.


Is the Discrete logarithm problem suitable for this pairing scheme? Let $Ans$ be the product of two pairings : $e(g,h)^{k} \times e(g,h)^{r}=Ans$

If everybody knows only $[g,h,e(g,h)^{k}]$ but $[r,Ans]$ is not known. In the discrete logarithm problem, the user knows two values. In this scheme, the user only know one value.

Is the discrete logarithm problem suitable for this scheme or not?

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants.  We come up with:

$$a \cdot b^x = y$$

where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$.

If it is sufficient for an attacker to find a solution, he can do that easily; he can select a random $x$, and solve it for $y$; there's a solution.

If he needs to find "the correct" solution (that is, the one possible $x, y$ pair that satisfies additional criteria), he doesn't have enough information to pick out which one it is.  He might be able to if he knows what that additional criteria is; it would depend on what that looks like.


Digital identification using steganography, can it be broken? Digital identification using steganography, can it be broken?

I have read a few articles saying that using an I.D. embedded in video, audio, etc can help track down the origin of a copyright violation. OK, then they said it can't be broken, so I got that "I'm gonna do it, just to prove you wrong" feeling and here I am.

I know a little about video and images from working with the OpenCV library. I know OpenCV kind of simplifies things, but in essence an image is a matrix with each coordinate being a pixel, or rather a set of RGB values or a similar set of values representing the pixel's color.

So from what I have gathered, in steganography ia smaller piece of data is embedded through-out the image or video and is used for various purposes. Now, I am assuming that the data is spread out bit-wise within the RGB values of the image or even multiple images in a video, which could be used to identify the source of a copyright infringement. That's all fine and good, just don't tell me I can't break it.

So say in theory I was going to pirate a movie. If I ran the the video and each frame through an algorithm that would add or subtract a random value within a given range that would not distort the quality of the video beyond an acceptable amount, that should completely distort the hidden I.D. — correct?

Would reformatting the image to a format that used something other than the simple RGB values in each pixel also aid in distorting the I.D. beyond recognition?

tl;dr: That depends entirely on the watermarking scheme.

Longer version: That depends entirely on the watermarking scheme used, specifically on the perceptability and robustness of the watermark. If it's supposed to be visible and robust, degrading the quality as Dmitry Khovratovich suggested will retain the watermark but might achieve the effect he describes.

If the mark is too perceptable though it might be possible to remove it. According to Ross Anderson (read below for link):

  For example, where the mark was added by either increasing or decreasing the luminoscity of the image by a small fixed amount, this caused the peaks in the luminoscity graph to become twin peaks, which meant that the mark could be filtered out over much of many images.

Provided that original copies only differ in the watermarked regions, pauluss86's solution is the most sure-fire way to get rid of them.

The following is the answer I originally set out to write but quickly got out of context. I retain it because of some interesting background information.

There's been a question on Security.SE that discusses stenography detection in images, so that's a good place to start. But more to the point, Ross Anderson's excellent book Security Engineering has an entire chapter dedicated to copyright and DRM (links to 1st edition, 2nd edition is out). So let's take a look at that (page 711 of the 2nd ed.):

  The DVD consortium became concerned that digital video or audio could be decoded to analog format and then redistributed (the so-called 'analog hole'). They set out to invent a copy generation management system that would work even with analog signals. The idea was that a video or music track might be unmarked, or marked 'never copy', or marked' copy one only'; compliant players would not record a video marked 'never copy' andwhen recording one marked 'copy once only' would change its mark to 'never copy'.

So kind of like how the "do not track" button works in browsers. One thing jumps out though: The watermark (the 'copy' flag) has to be resilient enough to be preserved through the conversion from digital to analog, which means soft degrading (like converting to another format) would also leave it untouched. The text goes on to say

  SDMI also uses a fragile watermark that's damaged by unauthorized processing.

but it's important to note the SDMI forum no longer exists. According to the Wikipedia page linked,

  On October 15, 1999, Eric Scheirer, later a digital music analyst for Forrester Research, wrote an editorial for MP3.com titled "The End of SDMI" which declared that the group's true goal to fold the technology industry into an alliance that would guarantee the record industry's near monopoly over musical content had failed. [...] The SDMI has been inactive since May 18, 2001.


Stream cipher and block cipher usage in network data encryption Stream ciphers are usually used for streaming data encryption, such as voice, and also for low layers data encryption. For example, MACSec uses AES-GCM encryption.
In L3 ad L4 security protocols (IPSec and SSL) block ciphers are preferred (AES-CBC).

Why are stream ciphers considered to be better than block ciphers in low layer encryption and block ciphers considered to be better for higher-level encryption?
What makes voice data (which is application layer data) suitable for stream cipher? Isn't it easier to divide the voice stream into blocks and encrypt it with block cipher?

In L3 ad L4 security protocols (IPSec and SSL) block ciphers are preferred (AES-CBC).

Errr, no.  Originally, SSL used RC4 (which is a stream cipher); then CBC mode (first DES/3DES and then AES) was added.  In the latest version (TLS 1.3), they discarded RC4 and CBC mode entirely, in favor of AEAD modes (GCM and Chacha20/Poly1305).
As for IPsec, it was originally CBC mode only (first DES/3DES and then AES).  Later, they added AEAD modes, and I believe they are currently the most common.
Hence, your claim that AES-CBC is preferred is not currently accurate, and so the assumptions behind your first question is not relevent.
Your section question is still interesting:

What makes voice data (which is application layer data) suitable for stream cipher? Isn't it easier to divide the voice stream into blocks and encrypt it with block cipher?

With voice, they tend to be quite sensitive to encryption overhead; the VoIP packets themselves are quite tiny (circa 20 bytes on average, IIRC), and so a fixed amount of overhead would be a larger fraction of the total overhead than, say, in TLS.  In addition, VoIP often goes over wireless, and they are especially sensitive to bandwidth there (in large part because of power; transmitting more bytes uses more power).  What this means is that VoIP encryption protoocols (such as sRTP) are designed to minimize encryption overhead over just about any other consideration.
Hence, modes that require padding (such as AES-CBC) would be rejected outright, in favor of modes that don't (such as AES-CTR).


understanding forking lemma Every time when I read a paper that has digital signature, when it comes to prove the security of a digital signature scheme, many chances that the author will use the forking lemma.

The forking lemma says as follows:

  Let $\mathcal A$ be a probabilistic polynomial time turing machine, given only the public data as input. If $\mathcal A$ can find, with non-negligible probability, a valid signature $(m,\sigma_1,h,\sigma_2)$, then with non-negligible probability, a replay of this machine, with the same random tape and a different oracle, outputs two signatures $(m, \sigma_1,h,\sigma_2)$ and $(m, \sigma_1,h',\sigma_2')$ such that $h$ is not equal to $h'$.

This wording comes from David Pointcheval and Jacques Stern's paper on "Security Proofs for Signature Schemes".
They also give a proof to this lemma, but it's very difficult for me to read.

In order to understand what I'm saying, you can see an example of that on this paper "A Secure and Efficient Authenticated Diffie–Hellman Protocol" from page 8-9. It's a security proof about FXCR. You can download it from http://eprint.iacr.org/2009/408.pdf.

The forking lemma really puzzled me for a long time; who can give a simple way to understand it?

For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted into a key recovery attack.

The technical question is how can you make sure that the forger is going to comply to our expectations and really forge two signatures for the same randomness. Indeed, in general, nothing forces the adversary to use its randomness in a simple way. In particular, giving him the same coins and forcing changes the messages is not going to achieve the desired goal, because the adversary is allowed to mix the messages themselves into the randomness used for signing.

The key idea is to restart the adversary with the same randomness let it run without change until it generates the message $M_0$ that was signed in the first run together with its rzndomness and then force a change on the rest of the run. At this point, in a practical setting, you could imagine using a fault attack on the hash function. However, in a theoretical model, the change is achieved by changing the responses of the random oracle that models the hash function on the first query that involves $M_0$ and all subsequent queries.

When you do that, you already know the behavior of the adversary until $M_0$ is generated and hope that it will forge again on $M_0$ with the same randomness but a different hash value. This is where the forking lemma comes into play (for a general version, see Multi-signatures in the plain public-key model and a general forking lemma by Bellare and Neven http://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf). In this general version, it is a technical lemma that analyzes the behavior of an adversary that receives some random values (each taken uniformely from at set of $h$ elements) and outputs a pair of values $(J,\sigma)$ with $0\leq J\leq q$ when several runs with inputs sharing a common prefix are performed. Note that when $J=0$, the adversary is considered to fail. The result of the forking lemma is that the probability of getting two related runs with the same value of $J$ and a common prefix of length $J-1$ is not too small. More precisely, if $acc$ denotes the probability of success of an adversary on a random input and $frk$ the probability of getting two related runs as above then:
$$
frk\geq acc\cdot \left(\frac{acc}{q}-\frac{1}{h}\right).
$$

The proof given by Bellare and Neven is not too hard to follow and I would recommend reading it.


MAC attacks without knowing the key Attacks on a MAC that do not require the discovery of the key are possible.
Consider the following MAC algorithm. Let $M=(X_1\mathbin\|\dots\mathbin\|X_m)$ be a message that is treated as a concatenation of 64-bit blocks $X_i$. Then define:
$\Delta(M) = X_1 \oplus\dots\oplus X_m$
and
$C_k(M) = E_k[\Delta(M)]$
where $\oplus$ is the exclusive-OR operation and encryption algorithm is DES
in ECB mode. Thus the key length is 56 and the MAC length is 64 bits.

How would an attacker breach the system without knowing the encryption
key?

One way to try tackling simpler problems like this is by writing them out as equations and doing algebra on them.  In this case, let's take this statement from your comment with the answer:

  The opponent can now concatenate the new message, which consists of $Y_1 || \dots || Y_m$ with the original MAC to form a message that will be accepted as authentic by the receiver.

So this is saying that the following equation is true:

$$
C_k(Y_1 || \dots || Y_m) = C_k(X_1 || \dots || X_m)
$$

But is it really true?  One way we can test this is by using the laws of equations (like in algebra) to rewrite this one over and over and see if it has the same truth value as some other equation that we can independently tell is true.

By applying the definition of $C_k(M) = E_k(\Delta(M))$ to both sides of the first equation we get:

$$
E_k(\Delta(Y_1 || \dots || Y_m)) = E_k(\Delta(X_1 || \dots || X_m))
$$

And since the function $E_k$ is a block cipher, it has an inverse $D_k$, which by applying to both sides we can get this:

$$
\Delta(Y_1 || \dots || Y_m) = \Delta(X_1 || \dots || X_m)
$$

Applying the definition of $\Delta(M)$ to both sides we get:

$$
Y_1 \oplus \dots \oplus Y_m = X_1 \oplus \dots \oplus X_m
$$

So the attack that you've quoted in your comment hinges on the fact that it must somehow cause this equation to be true.  Your comment explains the attack as this (I've corrected a notational error):

  The opponent can attack the system by replacing $X_1 || \dots || X_{m-1}$ with any desired values $Y_1 || \dots || Y_{m-1}$ and replacing $X_m$ with $Y_m$ where $Y_m$ is calculated as follows: $Y_m = Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)$.

Let's try substituting that for $Y_m$ in the equation:

$$
Y_1 \oplus \dots \oplus Y_{m-1} \oplus (Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)) = X_1 \oplus \dots \oplus X_m
$$

XOR is an operation where every element is its own inverse, so $Y_i \oplus Y_i = 0$ which is the identity element.  It's also an associative and commutative operation, so in the left side of this equation we can cancel out all of the $Y_i$ terms, and we get:

$$
\Delta(M) = X_1 \oplus \dots \oplus X_m
$$

Which is nothing other than the definition of $\Delta(M)$, which we were given as a premise.  So the technique you cited is guaranteed to forge a message and its tag different from $M$.  Worse, it allows the adversary to pick any values they like for $Y_1$ to $Y_{m-1}$.

The short, intuitive summary of that is that the problem with this MAC is that the way the $\Delta(M)$ it combines the plaintext message blocks with XOR gives the attacker way too much latitude.  Given any message $M$, it's trivial for the attacker to compute $\Delta(M)$, as well as many, many ways that they can compute a message $M'$ such that $M ≠ M'$ but $\Delta(M) = \Delta(M')$.  And since the MAC is just the deterministic encryption of $\Delta(M)$, that guarantees a successful forgery.


Does Diffie Hellman guarantee secrecy? I am studying my Cryptology exam and one question I got stuck below;

  Recall the Diffie-Hellman key establishment protocol. Alice runs this protocol over
  the Internet to communicate with Bob. Assume that the agreed key after running
  the protocol is k = g^ab (mod p). Alice then computes SHA256(k) and uses this
  as the key to encrypt a message m using AES. The resulting ciphertext is then
  sent to Bob.
  a) Does this protocol guarantee the secrecy of m?

I know that perfect secrecy is if the ciphertext provides no information about the plain text. Can somebody explain the above question to me?

The problem with this question is that it doesn't establish if the keys are static or not. If the keys are both static and a static-static (2S) DH protocol is used, then yes, this could guarantee secrecy if the public keys can be trusted to be from the right party, thereby authenticating A to B and B to A. A little used option of TLS is to use Diffie-Hellman based certificates, for instance.

Otherwise you're missing the authentication step, and Mallory could perform a man-in-the-middle by establishing keys A-M and M-B by tricking A and B that they are creating a secure channel to each other. Note that this is an active attack. it only works for Mallory - who can perform active attacks, not for Eve who can only eavesdrop the communication. Therefore "no" is most likely the correct answer.