Game traffic encryption AES CTR + HMAC I was asked to implement traffic encryption between the game server and clients.
Currently, the traffic is not encrypted in any way, which lets players use cheats to listen to the traffic in order to obtain information about the location of the opponents.

Traffic packets are small (50-70 bytes) and the developers are not ready for a big overhead for encryption.

When the session is started, the client communicates with the server via https; and in this moment, we can send a secret key. We think that the player will not be able to get this key by extracting it from the memory or somehow else.

AES in CTR mode will be used for traffic encryption. A fast hash function with a key will be used for authentication. 4-6 bytes (not 16) will be used for the tag.

How safe is this implementation? Which hash function is better to use? Can we use the same key for both the hash function and AES?

We think that the player will not be able to get this key by extracting it from the memory or somehow else.

Forgive me, but I'm skeptical. If you really have figured out a way to do this --- and plenty of well-funded, intelligent people have tried and failed --- I'd recommend slapping a patent on it and making millions off of licensing fees.

  How safe is this implementation?

Regardless of what you end up doing, the key will probably be the weak link. Or perhaps an attacker will try to read the decrypted packets from memory instead of the key.

I'm assuming that when you say "A fast hash function with a key will be used for authentication" what you mean is that you'll be using HMAC for authentication. If you mean something else, please clarify.

Using HMAC and CTR is a sound approach. Just make sure to authenticate the ciphertext ("encrypt-then-MAC"), rather than the plaintext ("MAC-then-encrypt" or "MAC and encrypt").

The real devil is in the details, though. You've given a broad overview of your approach, not a specific algorithm/protocol, and not an implementation. Each of these two transitions has the potential to go awry. For example, will your protocol prevent replay attacks? Will your implementation generate CTR nonces securely?

  4-6 bytes (not 16) will be used for the tag.

I wouldn't use a tag this short to protect financial data, but for a game, it's probably fine.

  Which hash function is better to use?

This depends on your definition of "better". SHA-2 will probably be the most secure. SHA-1 will probably be secure enough. HMAC-MD5 hasn't been broken, but using it is generally not recommended since MD5 has been broken. On the other hand, if your definition of "better" includes performance, than using MD5 may be worth the security risk (considering the relatively low stakes of the information you're protecting).

  Can we use the same key for both the hash function and AES?

Do not do this. This may not lead directly to any obvious attacks, but key reuse in general will anger Crypto Gods because it violates a key assumption (heh) that cryptographers make when designing these algorithms. It's the crypto equivalent of not doing any bounds checking on your buffers. (And if you later switch to using something like CBC-MAC for authentication, key resuse will be come a definite problem.)

If transmitting two keys is problematic for whatever reason, you can securely derive keys from a master key by doing something like this:

encryption_key = HMAC-SHA1(master_key, "Encryption key")
authentication_key = HMAC-SHA1(master_key, "Authentication key")

A couple suggestions.

This wasn't part of your questions, but I'd recommend using a dedicated authenticated encryption scheme such as GCM (galois counter mode) instead of separate MAC and encryption algorithms (such as HMAC-SHA1 and CTR-AES). Doing so will prevent some common implementation errors while quite possibly increasing performance.
Regardless of whether you use HMAC or GCM, look into using "associated data" (sometimes called "additional authenticated data"). The idea here is that if there's data that doesn't need to be encrypted (i.e., kept secret from the players) but still needs to be authenticated (i.e., the players shouldn't be allowed to tamper with it), there's no need to eat the performance cost of encrypting it. A crypto library that offers GCM will likely take an optional argument containing a string of associated data.


Do any stream ciphers with aperiodic keystreams exist? Exactly what it says on the tin. I can imagine constructing such keystreams from:

The binary expansions of irrational numbers
Chaotic systems like the logistic map or the Lorenz attractor.
The bitmap representations of images.
Extracting the y-coordinate from equations such as $sin(x)$ or $e^x \mod 1$ every n increments.

Well, it's easy to show that any generated with a bound on the amount of internal state must eventually become periodic.  It's also easy, once we allow a generator whose internal state grows arbitrary large over time, to design a generator that never repeats (and the state growth required is actually quite reasonable).

That said, I don't know of any proposed stream ciphers that attempts to be completely aperiodic.  I suspect that it's mostly because aperiodicity is not a realistic requirement (as opposed to the nicety of being implementable within a bounded memory space).  After all, it is easy to have, even with a bounded state generator, such a large period (e.g. a period of $>10^{100}$) that we never have to worry about it.  After all, if we never generate that much output, does it really matter if it would repeat if we did?


Obtaining the key length of a columnar transposition, given a known plaintext word I'm revising for a cryptography exam at the moment and I'm having some problems with a question.

The question looks for the key length of a cipher given that the word "earthquake" appears in the plaintext.

Ciphertext:
aaatr ksams itahb netrs weurs rheti aadne ttrht eakgt snqid s

I was wondering how I use the fact that the word "earthquake" appears in the plaintext to make it easier to obtain the key length?

At the moment, I'm just using the method of looking for repeated letters in the ciphertext to obtain a possible key length.

EDIT:
Here's the actual question:

  Consider the following ciphertext, [12 marks]

  aaatr ksams itahb netrs weurs rheti aadne ttrht eakgt snqid s

  i) Provide some evidence to suggest that this is not a substitution cipher.
  ii) Determine the keylength of this cipher given that the word earthquake
  appears in the plaintext.
  iii) Hence or otherwise decrypt this message to recover the plaintext.
  iv) Historically a variant of this cipher had a very important application.
  Briefly describe the variant and the application.

Both the Vigenère and autokey ciphers are classified as polyalphabetic substitution ciphers, so the cipher in your exam is not likely to be either of those.  Rather, the phrasing of the question suggests that it belongs to the other branch of classical ciphers, transposition ciphers.

Indeed, looking at the letter frequencies of the ciphertext strongly suggests that, being similar to the frequency distribution of plain English text:

A (8) ########
T (8) ########
S (6) ######
E (5) #####
R (5) #####
H (3) ###
I (3) ###
N (3) ###
D (2) ##
K (2) ##
B (1) #
G (1) #
M (1) #
Q (1) #
U (1) #
W (1) #

The question also implies that this cipher has a key, so we're looking at a keyed transposition cipher.  The simplest one of those is probably a columnar transposition.  These come in two varieties: regular and irregular.  If this were the regular kind, the length of the ciphertext (51 letters) would be a multiple of the key length; but since the only factors of 51 are 3 and 17, neither of which seems likely for a key length, we can guess that we're dealing with the irregular type.

Now, the obvious way to try to guess the key length (even without knowing anything about the plaintext) would be to note that the ciphertext contains exactly one Q and one U.  Those letters very often follow one another in English, as in the word "earthQUake", so we can assume that they're probably adjacent in the plaintext.  So we should try to divide the ciphertext into n groups (where n is, say, between 4 and 10) of approximately equal length (since this is an irregular columnar transposition, some of the groups will be one letter longer than the others) such that the Q and the U end up at the same position within their groups.  Also, since we know the surrounding letters of the QU pair, we should check that those (particularly the Ks, of which there are only two) also end up in suitable positions.

If we try that for various values of n, we might find that dividing the ciphertext into six groups of eight and nine letters each looks promising:

aaatrksam sitahbne trsweursr hetiaadn ettrhtea kgtsnqids

Notice how the Q, U and K all line up in the fifth position of their groups.  We can now try to write these groups one per line and try rearrange them to form "earthquake" vertically:

6 kgtsnqids
3 trsweursr
4 hetiaadn
1 aaatrksam
5 ettrhtea
2 sitahbne

This is looking very promising: we almost have the word "earthquake", and the surrounding letters start to form meaningful-looking words.  However, there are a few problems left: the fifth group doesn't quite line up with the rest, and the longest groups are not all at the top as they should be.  Let's try to fix the first issue by shifting group 5 right by one letter:

6 gtsnqids
3 trsweursr
4 hetiaadne
1 aaatrksam
5 ttrhteak
2 sitahbne

Now group 6 looks misplaced, but the fix is obvious — it clearly belongs at the bottom, not at the top:

3 trsweursr
4 hetiaadne
1 aaatrksam
5 ttrhteak
2 sitahbne
6 gtsnqids

And now we can read the plaintext from top down:

thats great it starts with an earthquake birds and snakes rem

(Ps. If you don't recognize the reference, listen to this.)

I do have to admit, however, that if there's some simple shortcut to reliably determine the key length without (mostly) solving the cipher, I'm not aware of it.

Edit: I did think of one shortcut: if the keylength were less than 6, the sixth letter of "earthquake", Q, would have to line up with one of the earlier letters of the same word, and thus follow it in the ciphertext.  Since the only Q in the ciphertext follows an N, which is not found in "earthquake", the keylength must be at least 6.  We can also see that keylength 6 does look plausible (the pairs EU, AA, RK and TE are all found int the ciphertext), while 7, 8 and 9 are impossible (neither RE, EK nor EE are found in the ciphertext).  Alas, this method doesn't let us conclusively rule out keylengths of 10 or more, even if they do seem a priori unlikely.


Mutual keys protection/wrapping Is there a known risk in having two keys wrapping each other?

Let's say, an adversary has access to both AESkey1(key2) and AESkey2(key1).

Does it make it much easier for him to recover the keys?

If I understand you correctly, you're asking, given C1 = AESK1(P1) and C2 = AESK2(P2), whether it is possible to obtain P1 or P2 in the case where K1 = P2 and K2 = P1. The answer is no, it is not.

There are no known cryptographic attacks that are made easier by having the ciphertext of two keys that are mutually encrypting each other. Obviously, it does allow an attacker to discovery both keys after having discovered only one of them, since they would be able to decrypt the second key once they know the first. Any cipher which becomes weaker when encrypting certain kinds of plaintext (whether known plaintext, all zeros, or even a key used by another cipher) would be considered badly broken. A strong cipher like AES does not have this problem as long as the key is secret and chosen randomly.


MTI/A0: modular arithmetic or elliptic curves? In the Handbook of Applied Cryptography (Menezes, A. J.; van Oorschot, P. C. & Vanstone, S. A.) Protocol MTI/A0 key agreement (algorithm 12.53) described as $\mod p$-protocol. The survey Overview of Key Agreement Protocols
(Ratna Dutta and Rana Barua) describes MTI/A0 as elliptic curve-protocol.

Unfortunately I have no access to original MTI article. How MTI-protocols were described originally?

It is quite simple to convert MTI/A0 into an elliptic curve method. An implementation is here.


Sending TLS messages with out encryption using openssl code Is it possible to send messages over TLS with out encryption?

If so which cipher suite is needed for this?

Yes, there are a number of TLS cipher suites that don't include any encryption.  These cipher suites are not normally used by OpenSSL, but they can be explicitly requested e.g. using the -cipher option to the OpenSSL tools.

Specifically, the suites offering no encryption and/or authetication are found under the NULL and aNULL cipher classes.  The openssl ciphers manual page describes them as:

  "eNULL, NULL:
  the "NULL" ciphers that is those offering no encryption. Because these offer no encryption at all and are a security risk they are disabled unless explicitly included.

  aNULL:
  the cipher suites offering no authentication. This is currently the anonymous DH algorithms. These cipher suites are vulnerable to a "man in the middle" attack and so their use is normally discouraged."

To get a list of the cipher suites included in the NULL class, run openssl ciphers -v NULL.  For me, the returned list looks like this:

ECDHE-RSA-NULL-SHA      SSLv3 Kx=ECDH     Au=RSA  Enc=None      Mac=SHA1
ECDHE-ECDSA-NULL-SHA    SSLv3 Kx=ECDH     Au=ECDSA Enc=None      Mac=SHA1
AECDH-NULL-SHA          SSLv3 Kx=ECDH     Au=None Enc=None      Mac=SHA1
ECDH-RSA-NULL-SHA       SSLv3 Kx=ECDH/RSA Au=ECDH Enc=None      Mac=SHA1
ECDH-ECDSA-NULL-SHA     SSLv3 Kx=ECDH/ECDSA Au=ECDH Enc=None      Mac=SHA1
NULL-SHA256             TLSv1.2 Kx=RSA      Au=RSA  Enc=None      Mac=SHA256
NULL-SHA                SSLv3 Kx=RSA      Au=RSA  Enc=None      Mac=SHA1
NULL-MD5                SSLv3 Kx=RSA      Au=RSA  Enc=None      Mac=MD5

To see if a specific server lets you connect to it using one of these suites, run:

openssl s_client -connect host:port -cipher NULL

Of course, for most services, this should cause the cipher suite negotiation to fail, like this:

$ openssl s_client -connect www.google.com:443 -cipher NULL
CONNECTED(00000003)
3073382600:error:14077410:SSL routines:SSL23_GET_SERVER_HELLO:sslv3 alert
handshake failure:s23_clnt.c:724:
---
no peer certificate available
---
No client certificate CA names sent
---
SSL handshake has read 7 bytes and written 139 bytes
---
New, (NONE), Cipher is (NONE)
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
---


Do any cryptography algorithms work on numbers besides primes? I know prime numbers are important for several algorithms and protocols. Are there any algorithms and protocols that don't require primes?

Yes, very large primes, and I know my question is quite broad. I guess this is equivalent to asking if there are other very hard one-way math functions besides those based on primes. that don't rely on the fact that composites of two large primes are easy to create but hard to factor.

I don't think you should call them one way math functions. If RSA was one way then it wouldn't be possible to create RSA (only) encryption. More information here. RSA relies on a trapdoor function and traveling back without "a stair" is expected to be a hard problem. ECC also relies on primes to be secure, so it would also be affected.

Factoring and the RSA trapdoor function is already threatened by quantum cryptography. So generally you can simply look at post-quantum cryptography. So yes, there are problems that don't rely on primes for their security. Lattice based crypto is one of the most promising theories. Within this problem space a promising algorithm seems to be Ring-LWE. This is an algorithm based on the idea that . You can read a story about lattice based crypto here; as a writer you'll love the way it is written. So with regards to scientific research the impact would probably be minimal. A host of new students should be thought harder to learn primitives, but otherwise we already have replacement algorithms and protocols.

Being able to factor numbers won't affect most common symmetric primitives. So stream ciphers, block ciphers and hash functions would not be affected. Neither would any algorithms build from those such as message authentication codes (MAC), deterministic random bit generators and the like.

So what would be affected? Basically signature schemes used for authentication and non-repudiation. Asymmetric encryption (including hybrid encryption) and key agreement would be affected as well. That means that without RSA and ECC the whole PKI infrastructure would break down until an alternative such as lattice based crypto could be introduced.

So impact on the security landscape would be huge. Smart cards contain keys build on RSA and ECC. In general many quantum resistant algorithms have large memory requirements as well, so it may not be a simple task of replacing cards with new cards. SSL/TLS uses PKI for authentication, so the whole PKI eco-system would have to be renewed. A lot of hardware security modules (HSM's, devices used by e.g. banks and certificate authorities used to keep their keys secure) do not have any asymmetric primitives other than RSA or ECC. Embedded systems would need to be upgraded.

Basically if you currently would introduce an algorithm that would allow us to factor some numbers, the effect would be that the large institutions would try and migrate to other numbers still thought to be secure. There would certainly be a panic and a lot of speculation if those numbers would actually be secure. It would probably take some 3-5 years before we could completely migrate away from our current infrastructure to something that would not rely on prime numbers. The reluctance to move away from SHA-1 should be considered a strong warning about the resistance to change by the security industry.

This is one reason why NIST is already moving away from ECC crypto, even though quantum computing is still in its infancy.

Anyway, enough information to write a story about, although that story would be more a story about mayhem in the security world than a story about some genius coming up with a new algorithm to try and avoid it. That's what I would speculate to happen anyway.


Creating unique keys with md5 The project I'm working on requires me to find a way to create a unique key based on data stored in a table. The table in question consists of x columns and y rows.

In order to create the key I want to hash the data using md5 in the following way:

"|" || md5[(x_1,y_1)]  || "|" || md5[(x_2,y_1)]  || "|" || md5[(x_n,y_1)]  || "|"

My question is: How can I calculate the chance of duplicate keys for different data using this method?

Given: I know the amount of columns (x), I know the size of the data in the columns, I know the amount of rows (y).

The idea comes from this video: https://www.youtube.com/watch?v=fNrs7C86nkI

In the video he says he will do "the math" later but this is not in the video.

If I understand your question correctly, you want to generate a short value $v(T)$ from a table $T$ such that if $T_1$ and $T_2$ have the same size and the same elements in each corresponding cell, then $v(T_1) = v(T_2)$, and if the tables have different sizes or different elements then $v(T_1) \ne v(T_2)$.

What you need for that is two ingredients:

A unique representation for tables.
A cryptographic hash applied to said unique representation.

“Unique representation” means that distinct tables have different representations. For example, if your table cells don't contain the character |, then | + T[0,0] + | + T[1,0] + || + T[0,1] + | + T[1,1] + | (where + is string concatenation) is a unique representation of a 2x2 table, and the representation generalizes to arbitrary-size tables with no collision. However, if your table cells can contain the character |, this representation is not unique: you cannot distinguish T[0,0] = a|, T[1,0] = b from T[0,0] = a, T[1,0] = b.

If you can't assume anything about the content of table cells, a convenient and secure method is to take a cryptographic hash of each cell independently, and build the hash of the table by hashing a string made up of hashes. (This is a special case of a Merkle tree.) Don't forget to include the table geometry in the representation. One way to do that is by putting the number of lines and columns at the beginning of the string:
$$v(T) = H(m + \mathtt{|} + n + \mathtt{|} + H(T[0,0]) + H(T[1,0]) + \dots + H(T[m,n])$$
where $+$ is concatenation, $m \times n$ is the table size, numbers are represented in decimal and hashes in hexadecimal. Another possible representation is to hash a row by hashing the concatenation of the hashes of the cells in that row, and hash the table by hashing the concatenation of the hashes of the rows.

Moving on to the question of how likely duplicate keys are, there are three cases to consider. Suppose that $H$ is a $k$-bit cryptographic hash.

All the data is essentially random. In this case, the chance that two tables have the same hash is negligible as long as you have significantly fewer than $2^{k/2}$ entries in the list of tables. This figure comes from the birthday problem. For example, a 128-bit hash lets you have several billion billion entries before the chance of a collision becomes high; with a billion entires, the probability is less than $10^{-18}$.
An attacker can choose some of the contents of the table, for example one of the fields is a free-form string, and the objective of the attacker is to craft two distinct tables with the same hash. This is an attack on the collision resistance of the hash. Breaking collision resistance can allow an attacker to inject a harmless record into your database, then substitute a bad one for it. When it comes to attacks, you can no longer reason in terms of probability, because attackers don't behave randomly. MD5's collision resistance is broken: there are cheap ways of generating strings with the same MD5 and with some content in common. Hash trees may be fine, but that depends on the exact structure of your data. So you must use another hash. SHA-256 is the standard hash nowadays.
An attacker wants to craft a table with the same hash as another table that is already in the database and not chosen by the attacker. This is harder than the previous attack; it's an attack on second preimage resistance. MD5 is not broken in this respect; however it would be a bad idea to use it because there is a risk that the attack on collision resistance could be improved to an attack on the second preimage.

TL;DR:

Encode the data in your table such that the representation is unambiguous.
You can take a hash of each piece, then take a hash of a sequence of hashes and other data: such hash trees are fine.
Don't use MD5. Use SHA2-256 (or SHA2-512).
If implemented correctly, not only is the probability of a collision too small to worry about (it's less than the probability that your processor will flip a bit at the wrong time), but better than that, there is no possibility for an attacker to arrange a collision.


How to calculate the entropy of passwords? Here is a cartoon about password entropy. http://xkcd.com/936/

I dont quite understand how the entropy is calculated in the cartoon assuming they are calculate correctly. But in general, I dont have much idea about how password entropy is calculated.

First of all: Entropy is a property of the process generating a password, not a property of an individual password.

Random passwords

Apart from that, the basic idea is the following: Say you have the password aeLuboo0 that contains lower-case chars, upper-case chars and numbers. Then under the assumption that you have choosen every character uniformely from all possible characters, there are in total

$$(26 + 26 + 10)^8 = 218340105584896$$

many passwords that can be generated in the same way as your concrete password has been generated. The entropy in bits is now the number of bits you need to have approximately the same number of possible bit-combinations. That is:

$$\log_2((26 + 26 +10)^8) = 47.633570483095$$

Hence the assumed process that generated your password aeLuboo0 can generated as many different equal likely passwords, as different numbers can be represented by $47.63$ bits. The entropy of the password can be assumed to be at $48$ bits.

Non random passwords

The cartoon has the example of a word, that has been taken from a dictionary and then mutated to get the actual password. The idea of entropy is the same again (heavily simplified): Guess the number of different words your theoretical source dictionary and multiply it by the number of possible mutations the get a total count of passwords that can be generated in this way. Now find the $\log_2$ of this count to approximate the entropy.


Risks of full length KCV (components and full keys)? We have to comply with third-party security requirements for the loading of 3DES keys. I'm a little confused about the reason behind why Key Check Values (KCVs) can't be full length. As KCV are hashes, I'm wondering what the security implication and risks are?

The usual (or at least traditional) blockcipher KCV is not a hash but rather the truncated encryption of zero; see How to obtain KCV from the key and KCV and compatibility with block cipher modes of operation

If 3DES (TDEA) key components K1,K2,K3 (i.e. single-length) (or their shares) are checked separately, a full-length (64-bit) check value on a 56-bit key component is practical to bruteforce, with small chance of ambiguity. Similarly for AES-128 where block size equals key size, if 2^128 bruteforce were practical you would be unlikely to get more than a very few candidate keys, which in most situations is a break. For a double-length or triple-length 3DES key, the key is longer than a (full) data block, by 48 or 104 bits; the former is probably safe and the latter definitely so.


Is there an outdated or insecure hash algorithm thats output can be easily reversed back into the input? I'm looking for a hash algorithm thats output can be reversed back into the input in a reasonable amount of time (a day or less) using a decent consumer computer. If anyone has any information on this, it would be very much appreciated.

Edit: After reading some of the comments and answers on this post, I feel I should clarify: I'm looking for a hash algorithm where it is relatively easy to reverse a hash into an input that is one byte larger than the hash. For example, if the hash output is 32 bytes, and the input was 33 bytes, I'd like to know if there's a hashing algorithm where it's possible to reverse the output into the input in a situation like this.

Depending on what you want to do, maybe you can take a cryptographic hash function and truncate it. Adjust the length of the truncation to how much effort you want the preimage calculation to be. This is a valid way to create a proof-of-work mechanism. For example, if you want to require a party to perform about $2^{m+n}$ operations where $2^m$ is the estimated cost of hashing a very short string, then:

Generate a random $s+n$-bit string and calculate its hash $h$.
Send the hash $h$ and the first $s$ bits of the string and request a preimage.
Read back a string and check that its hash is $h$.

(The salt length $s$ needs to be sufficiently long to prevent pre-computing possible inputs.)

With any cryptographic hash function in good standing, and even with most of the ones in bad standing such as MD5, the fastest way to find a preimage is brute force searching among all $n$-bit strings.

If proof-of-work is not what you're after, then maybe you can use a non-cryptographic hash, for example a CRC. In general, hash functions that aren't specifically designed to be cryptographic hashes have a low probability of accidental collision (but it's easy to craft a collision deliberately), and they're easy to invert.

Of course, “inverting” the hash will find a preimage, not necessarily the string you started with.


Why was Vaudenay's original padding oracle attack not exploitable on TLS 1.0? Reading Password Interception in a SSL/TLS Channel that was released in 2003:

  At Eurocrypt’02, Vaudenay presented vulnerabilities in padding schemes used for block ciphers in CBC mode. He used a side channel, namely error information in the padding verification. This attack was not possible against SSL/TLS due to both unavailability of the side channel (errors are encrypted) and premature abortion of the session in case of errors.

In Vaudenay's 2002 paper:

  TLS v1.0 (also) provides an optional MAC which failed to thwart the attack: when the server figures out that the MAC is wrong, it yields the bad_record_mac error. However, the message padding is performed after the MAC algorithm, so the MAC does not preclude our attack since it cannot be checked before the padding in the decryption.

it continues:

  The reason why the attack is not so practical is because the padding format error (the decryption_failed error) is a fatal alert and the session must abort.

Now, how bad is this? Bad padding leads the section to break OK, but 1 out of 256 times the padding will be correct and one byte of plaintext will be recovered. This should be enough, and in the same manner of BEAST-style attacks more bytes could be recovered by shifting the payload so that the byte of a cookie we want to recover is always the LSB. I fail to understand why these people thought this was not exploitable.

To add to this, it looks like Canvel, Vaudenay and others actually knew about this but didn't know this was fully exploitable:

  As pointed out in [17], the attack could have still worked in order to decrypt only the rightmost byte with a probability of success of 2−8. It can also be adapted in order to test if x ends with a given pattern.

Although they later add:

  This does not work either against TLS for another reason: because error messages are not available to the adversary (they are indeed encrypted and indistinguishable).

How is an error, even encrypted, indistinguishable? I'm guessing it would be a short message compared to a long normal response.

It's a question of attack model. Vaudenay places himself in a model where the attacker is "outside", and trying to work out the password that a human user enters in a Web site (or another similar password-protected protocol). Both client and server systems are honest and truthfully run the TLS protocol; the attacker can inspect and alter packets, but that's all. Chosen Plaintext Attacks are out of scope.

In that model, in case of repeated errors, the human user will consider things too fishy, and will not persist. Moreover, most alterations meant to check an hypothesis on the last byte of a block also mangle the previous bytes in the record, which contain the MAC, so the ultimate observable behaviour, from the attacker's point of view, is unchanged: an (encrypted) alert record is sent by the server, and the connection is aborted (so we are not talking about the difference between a short error message and a long non-error message, but about two error messages, who have the exact same length).

The 2003 paper "fixes" both issues:

It targets the case of an email client that automatically connects to an IMAPS server, every minute, and will try again and again even if connections abort; the errors are also silently ignored.
The difference between failure modes ("bad padding" vs "good padding but bad MAC") can be worked out by the attacker by measuring the server's response time.

Retrospectively, we may note that the problem about the alert message not being known can be avoided when the padding has the size of a full block and the receiving side does not check padding byte contents, as is nominally the case with SSL 3.0. Also some TLS 1.0 implementation did not check padding byte contents.

Around 2010, researchers made some sort of "mental breakthrough" in which they realised that CPA were a valid model in a Web context. This began with padding oracle attacks on ASP.NET, in which the attacker sits on the sending side, and wants to unravel the "viewstate", an encrypted blob that the server adds to a Web page in order to offload state information storage on the client. This is not a TLS attack, but it still demonstrates the "extra powers" awarded to the attacker: the attacker controls the connection and can decide to try again, repeatedly, with no supervision by a human victim; and he gets access to error messages.

Then, in 2011, the BEAST attack demonstrated an attack which was not about padding (though it was still about CBC in TLS), with a CPA model in a Web browser, and targeting a secret value sent automatically by the client (the cookie). From that point, researchers began to really believe that CPA with low success rate per connection were really practical in a Web context.

The padding oracle attack, Vaudenay-style, combined with BEAST-like attackers using hostile Javascript, to form the Lucky Thirteen attack. In the mean time (and thanks to Vaudenay's 2003 article), TLS libraries had adapted their code:

The same alert message was sent, whether the failure was on the padding or the MAC (also, that error message was not necessarily made available to the attacker).
The MAC was still computed even in case of bad padding, so as to have a constant processing time.

Yet, there was a small remnant of a timing leak, because the MAC computation time depends on the size of the plaintext, which is not exactly equal to the size of the ciphertext, because of the padding. If padding found upon decryption was incorrect, then the library had to choose some pseudo-padding length, which would leak a bit of information. The Lucky Thirteen attack uses that small leak, in a CPA model with hostile Javascript.

Modern TLS libraries implement really constant-time processing which removes this last timing leak, thus making TLS 1.0 CBC cipher suites safe again (but TLS 1.2 with AEAD suites is still largely preferable).

Summary: it took researchers a decade to understand that the Web offered a practical CPA setup. This entailed recognising that Javascript was not only meant to animate a dancing squid on a Web page, but was powerful enough to trigger many silent connection attempts; and, crucially, that each such connection could be made to include a secret value which, while not being the actual human-entered password, was still juicy enough to warrant some attacking effort.


IPSec vs SSL : Similarities and Differences I am studying SSL and IPSec. I can pretty much nail down the "very high level" differences and similarities between the two, but am struggling to find a "lower level" (but not too deep) look.

This may seem like a dumb question, but do SSL and IPSec use different key schemes and algorithms from another to establish contexts? Or am I overthinking this and does one not even use these at all?

Best

but do SSL and IPSec use different key schemes and algorithms from another to establish contexts?

Well, given that, by IPsec, you mean only AH and ESP (that is, RFC4301-4303), well, the obvious answer is that IPsec doesn't mandate any way to generate keys, select algorithms, or to establish contexts.  All that is assumed to be done by some other protocol (which might be IKEv1, IKEv2, GDOI, manual configuration or possibly others), and exactly how that is done is not IPsec's concern.

TLS (which is the name I prefer to SSL; you shouldn't be using SSLv3 and you really shouldn't even consider SSLv2) has embedded in it an authentication and key establishment protocol, which spells out exactly how things ought to be done.

Of course, as for how they do encryption and decryption, there are some differences.  Some of these differences are design decisions (TLS has traditionally done 'MAC and then ENCRYPT', while IPsec does 'ENCRYPT and then MAC'); on the other hand, a lot of the differences are due to the fact that they're addressing different problems:

TLS is over a reliable transport (typically TCP), while IPsec is over an unreliable transport (IP, which can drop and reorder packets).  What this means is that TLS keeps context between the sender and the receiver and updates that state (such as the sequence number); with IPsec, all that needs to be made explicit (as there is no guarantee that the receiver will get same packets in the same order that the sender sent). [1]
IPsec was designed specifically to protect IP traffic; hence it has a bunch of rules built in with IP in mind; for example, how fragments are processed, how it interacts with IP MTU, how packets interact with the security policy database, how DSCP bits are handled, how ECN (Explicit Congestion Notify) is handled.  In contrast, TLS was designed to protect a byte stream, and it makes no assumptions about what that byte stream means.
IPsec was always envisioned to be security gateway-friendly. That is, it was always expected that one use case for it would be a router in the middle that accepts plaintext packets (say, from your local office LAN), and sends them off encrypted through the internet (perhaps to another security gateway in a different location).  Of course, you could also use IPsec in an end-to-end fashion; both usages were considered in its design.  In contrast, TLS was always envisioned to be end-to-end; that say PC that generates the plaintext was expected to be the one encrypting it.  Now, you can design a TLS security gateway (and most certainly, people have); it is significantly less clean because of design choices behind TLS.

[1]: If you look at DTLS (which is also over an unreliable network), you will see that they modified the protocol to somewhat more like IPsec (such as explicit sequence numbers, and explicit record contexts (DTLS calls them epochs, IPsec relies on SPIs for that)


How many bits to flip in an RSA public key to do signature forgery? Scenario: Alice wants to verify a signature from Bob. Alice knows Bob's RSA public key (e, n). However, Alice is getting the data, the signature of the data and the public key from an attacker Eve. Assume the signature is compliant with PKCS# v1.5.

Now I know trivially Eve can generate an RSA key pair and signs the data herself and send the fake public key and fake signature to Alice. But I am going put a constraint on Eve. Eve cannot generate whatever key pairs she likes. Even has to flip the (e, n).

My question: What is the least number of bits she needs to flip in (e, n) such that she can forge the signature?

NOTE: she can either generate a signature from Bob's private key or she can generate a signature from some other private key she can compute from the corrupted public key or whatever attack she can come up with. As long as she can convince Alice the signature is from Bob.

If Eve can find an $n'$ that is prime (and $n'-1$ is relatively prime to $e$),then she can easily sign any message with that $n', e$ pair.

So, the question is: what is the probability that there exists a prime $n'$ such that there is only one bit difference between $n$ and $n'$, and $n' \not\equiv 1 \pmod {e}$ ?  The answer is that it is quite good if $e > 3$, and decent even if $e = 3$. We'll assume $e$ is prime; in practice, it almost always is.

There are $log_2 n$ integers that have one bit difference from $n$ (we'll assume that Eve cannot flip bits that increase the size of $n$); flipping bit 0 will obviously yield a composite; flipping any other bit will yield an odd integer.  A "random" odd integer of size circa $n$ has a circa $2/{\log_e n}$ probability of prime; if we model each of the odd integers as "random", then we would expect around $(\log_2 n - 1) 2/{\log_e n} \approx. 2.89$ primes to be about one bit flip away from $n$; alternatively, there would a probability approximately $(1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx. 0.044$ that none of the values 1 bit away from $n$ happen to be prime.  When we include the condition with $e$, we know $n$ always satisifies the condition, and so a value with a bit flipped would have probability $1/(e-1)$ of satisfying it; from that, we can see that with $e=3$, we have an expected $1.44$ values satisfying it (hence we have a better than average chance); for $e>3$, the probability is even higher.

And, once we consider $n'$ values that aren't prime, but are easily factored (they're a large prime times a smooth number), the probability becomes much higher)


How does the split mask countermeasure work on AES? I am trying to understand the split mask countermeasure which is a masking method to avoid side channel attacks. Let's first describe the principle and then try to apply it to AES.

I found this paper which analyses this method. First, I will quote the presentation of the split mask countermeasure which is given in the second section:

  Let $S$ be an S-box with input $x$ and output $S(x)$ implemented as a
  lookup table. The split mask implementation of $S$ consists of a
  masked table $S′$ and a mask table $M$. These tables are defined as
  follows: \begin{equation} S'(x \oplus n) = S(x) \oplus r_x,
 \hspace{1cm}\\ M(x \oplus n) = r_x \oplus m \hspace{1cm}(1)\\
 \end{equation}

  This means that the input of the S-box is masked with $n$, and each
  output value is masked with an individual random value $r_x$. This
  gives the masked table $S'$. The set of output masks $r_x$ is also
  stored in the mask table $M$ so that
  \begin{equation} S'(x \oplus n)
 \oplus M(x \oplus n) = S(x) \oplus m \hspace{1cm}(2)
\end{equation}
   holds for every input $x$. In other words, $m$ can be viewed as the
  output mask of $S$ that is split into two shares $r_x$ and $M(x \oplus n)$, the splitting being individual for each table entry.

  The split mask countermeasure with a single mask table is claimed to
  thwart the 1-st order DPA attack. For this, the original description
  requires that $(2)$ should never be computed directly (i.e. appear
  as an intermediate value) during an algorithm execution.

The description seems clear to me except this sentence:

  For this, the original description
  requires that $(2)$ should never be computed directly (i.e. appear
  as an intermediate value) during an algorithm execution.

So how should it be computed?

So let's consider we want to encrypt a block data using AES and the split mask countermeasure. We start by generating $n$, $m$ and 256 bytes $r_x$ to compute $S'$ and $M$.

But then, when we have to apply the $\texttt{SubBytes}$ operation during the algorithm, how to proceed?

In the same paper mentioned above it is said:

  Other details of concrete implementations can be found in [10, 11, 12, 13]. In these papers the countermeasure is proposed for an optimized
  AES implementation with $8 \times 32$-bit lookup tables that are used
  to compute the S-box and the diffusion simultaneously.

but it concerns optimized $32$-bit implementation and I would like to simply implement it for a traditional $8$-bit version so it does not help me that much...

Given some intermediate data $x$ as two shares $x=x_1\oplus x_2$ take some fresh random $r$ to calculate new shares $x_1' = ((x_1\oplus r)\oplus x_2)\oplus(n\oplus r)$ [parenthesis indicating the order of evaluation] and $x_2' = n$. Now you can use $x_1'$ ($=x\oplus n$) as input for both tables.

The answer to "So how should it be computed?" is not at all. It is not needed. I think this is just a warning that it would be a problem to have (2) as intermediate value, because $m$ is kept constant for many plaintexts. Strangely enough, the inventors of the split mask countermeasures didn't realize that keeping $n$ constant for many plaintexts poses the same risks. A very short look at the paper you linked to, gave me the impression that it will expose this weakness in later chapters.


So please help to decrypt this message

This would appear to be an RSA encrypted message, using a 4096 bit RSA key.  Assuming that the key was generated properly, then it is infeasible to recover the plaintext using only the message and the public key; sorry...


Is it possible to unpad a file that is not padded I used "AES/CBC/PKCS5Padding" to encrypt some files. But I did not provide any identifier to detect if the file is encrypted or not. Now one way to detect if a file is encrypted or not, that I can think of, is to try to decrypt it and see if there is a padding miss match.

Now my question is,
Is it possible for some random file to match the padding scheme?

Yes, it is quite possible that after decryption, a file that was not encrypted falsely appears to be encrypted with correct padding.

For a file of random byte length, there is probability 1/16 (6.25%) that its length is that of a valid encrypted file, and then there is probability just below 1/255 (≈0.392%) that after decryption, the last block ends with 01, or 0202, or 030303, or 04040404...

All in all, nearly one random file (of both random length and content) out of 4080 would wrongly pass the test.


can session key be be used as digital signature? if two communicating parties share a (symmetric)  session key, k.

When one of the party wants to send a message 'm' to other, is it okay use {m}k as a digital signature?

No.  Let || be concatenation, let [E',D'] be any symmetric encryption scheme,

and then let [E,D] be given by    E(k,x)  =  0 || E'(k,x)    and

D(k,empty_string) = empty_string    and    D(k,0||c) = D'(k,c)    and  D'(k,1||c) = c .

The efficiency and correctness conditions for [E,D] are trivial.  Since E can be simulated

from E' by just prepending a zero to each ciphertext, [E,D] will be IND-CPA if [E',D'] is.

However, with [E,D], one can trivially break {m}k as an authentication

scheme by just outputting something that starts with 1.


What is the difference between a HMAC and a hash of data? On a recent question it became apparent that there's a significant difference between an HMAC of input data and a hash of input data.

What exactly is the difference between an HMAC and a hash of a span of input data?

TL;DR, an HMAC is a keyed hash of data.

A good cryptographic hash function provides one important property: collision resistance. It should be impractical to find two messages that result in the same digest.

An HMAC also provides collision resistance. But it also provides unforgeability. In order to generate an HMAC, one requires a key. If you only share this key with trusted parties, given an HMAC signature, you can be confident that only one of the trusted parties could have generated that signature.

Due to common properties of hash functions, an HMAC is not as simple as hashing the data appended to the key. This construct is vulnerable to length-extension attacks where an attacker can take a message and its HMAC signature, and use this to construct a longer message with a valid signature (thus breaking the guarantee of unforgeability).


Are collision-resistant hash functions even possible? [see description] Surely there can be no real collision resistant Hash function since hash values are of finite size which means there are finitely many of them, but there are an infinite number of messages we could hash, which means (using the pigeon-hole principle) that some messages must lead to the same hash value.

Collision resistance relates to how difficult it is to find a collision, not the total lack of collisions.  In other words, a hash function $H(x)$ is collision resistant if and only if all attackers given reasonable computational resources (probabilistic polynomial algorithms) have only a negligible chance of finding two messages, $m_0$ and $m_1$ such that $H(m_0)=H(m_1)$.

Note that this is not an information theoretic type of security - an attacker given unlimited computational resources will always be able to find a collision (or as many collisions as desired).  It is possible to get information theoretic security from something like a one-time MAC (where even an unlimited attacker has only a negligible chance of devising two messages with the same MAC tag), but that relies on a secret key used only once, whereas in a hash function nothing is secret.


message with small order in RSA signature It is know that elements from $[1..N-1]$, where $N$ is RSA modulus can have different orders. So some of the elements can have very small order generating subgroup of only few elements.

Now, if the adversary for a message chooses $m$ that has small order, the adversary does not have to know the private exponent $d$ to forge the signature for this $m$, since the same signature can be produced using smaller exponent $x$ $(d \equiv x \mod ord(m))$, which can be found easier than the private exponent $d$.

Why is this not a concern in RSA signature scheme?

Update:
The cyclic attack does not depend on the order of $m$. The answer should be related to the distribution of orders for elements in $[1..N-1]$. Since the order of element divides $\phi(n)$, the choice of $p$ and $q$ should have some effect on the feasibility of this attack.

The order $o$ of an element $m\in(\mathbb Z/pq\mathbb Z)^\times = (\mathbb Z/p\mathbb Z)^\times\times(\mathbb Z/q\mathbb Z)^\times$ is the least common multiple of its (multiplicative) orders modulo $p$ and modulo $q$.

If this order $o$ is known to the attacker (or at least small enough that one can find it, e.g., by baby-step giant-step), then the attacker can factor $N=pq$ if the multiplicative order of $m$ modulo $p$ differs from its order modulo $q$: The attacker raises $m$ to the power of $\frac{o}{r}$ for all prime factors $r$ of $o$, until modulo one prime factor of $N$, but not the other, the order of $m$ divides $\frac{o}{r}$, which can be detected by $0<\mathrm{gcd}(m^\frac{o}{r}-1\bmod N, N)<N$, breaking the RSA.

So what you are asking for allows the attacker either to break RSA or to find an element $m\ne 1$ that has simultaneously the same small multiplicative order $o$ for unknown primes $p$ and $q$ given just their product $N$, which I'd expect to be a hard problem ($m$ is modulo $p$ a $(\frac{p-1}{o})$-th, modulo $q$ a $(\frac{q-1}{o})$-th power).


Authentication protocol which detects client impersonation from another machine Consider following authentication protocol.

Client ClientA knows some initial secret KeyA shared with server.
Client also knows IP of legitimate server.

Now when client wants to establish connection with server she will send KeyA to server and her ID (for server to know which key to use).

The server generates new random number Key1A and sends back to client. Now following request will only be accepted if Key1A is sent by the client along her ID. When client sends another request with Key1A, server will generate Key2Aand send to client, and etc.

Now if attacker captures say KeyAn - if she uses KeyAn, it means client will not be able to communicate with the server anymore - because the server will have generated KeyAn+1 already. And expect only KeyAn+1 which the client will not know if attacker used KeyAn already. We will detect that one client with ID clientA "died" - because ID is also sent to the server. And disable request from clientA.

Does this provide identification of client in a secure way?
If no how can I improve this protocol such that if attacker steals some secret and tries to authenticate with server instead of some client A (from a different computer though), then at least I can detect it?

There are a few issues with your protocol. Namely it doesn't protect against men-in-the-middle.

Issue #1 (mentioned by fgrieu in the comments): Assume I host one of the (many) servers all your IP packets have to travel through from ClientA to Server. If I drop the server's Key1A (or KeynA) any future request won't work and I have successfully denied your user the usage of the server. He will have to re-perform the secure initial secret exchange which is likely expensive.
While this won't break the protocol in the sense you're interested in, this is still potentially harmful as it may cost you money (by losing customers being angry about the unrelieability of your protocol) if you need to do an expensive renegotiation (which involves human interaction?) too often.

Issue #2: If I don't just drop the packet, but flip a single bit, the client will get a wrong key and the server will assume the client has been successfully broken, so your legitimate client will be angry at you and has to re-perform the secure exchange. (see issue #1)

Issue #3: If I can eavesdrop on any of the server's responses and I'm able to drop all users packets, I can successfully take over the role of the client.
You send the next valid token in each of your server's responses and if I can get my hands on that and one valid client request (for getting the ID) I can successfully use said ID and the valid token to make my own requests.
All I have to ensure is that the client won't make any requests himself until I've finished all my evil requests.
The time-frame I need may be relatively short (a few seconds or minutes maybe) and I may be very well able to pretend the server is offline for maintenance for this time-frame. Or I could just launch a packet flooding attack on the client (which probably doesn't have more than 100Mbps bandwith?).
You shouldn't rely on an attacker not being able to DoS your client just because "it's not easy", a good protocol wouldn't create this situation in the first place (and the below mitigation should fix this issue anyways), for example you could avoid sending the next valid token at all,
but cleverly use HMAC to only send derived values and thereby only send the next valid nonce.

Issue #4: If the client actually is some piece of software that should authenticate to the server, I as the (not-so) legitimate user can extract the full program state from RAM / disk drive and just copy it over to another machine to perform my evil requests from there, and maybe I even install some software (like increasing packet loss or just root-level blocking the application) to make sure the legitimate client needs some time to figure out, I stole his credentials. This will be detected, but I still have some time (minutes up to days) to make my evil requests which may cause serious harm to the system and make you lose customers / money.

I hope this points the main issues of your protocol out (if anyone finds any else, please comment / answer yourself).

Now for the improvement.

The best thing to do is: Don't roll your own crypto.

The easiest way to mitigate the issues #1-#3 is by simply using your protocol on top of server-authenticated TLS. This would mean a modified packet would never reach your client application, the server would notice (thanks to record numbers / TCP) if a key didn't reach the destination and an eavesdropper wouldn't be able to read the valid tokens (and mitm is mitigated if the client checks the certificate properly). To fully mitigate man-in-the-middle attacks, you have to deploy DNSSEC along with TLS (and maybe DANE if you're at it) which would ensure you get the correct IP from the domain name for which you know the correct certificate (and can cross-check via DANE) and would allow you to drop the "known IP" requirement.

Issue #4 can't be mitigated with a pure software solution. I can go ahead and copy the state of any program (if I'm root / admin on a PC) and continue running it somewhere else (at least for some time). You need to use a hardware solution in order to ensure that a specific PC was used for a specific client or the client will be able to just shut-down his PC and copy the app to another one (in the same network?) and run it from there. The cheapest approach to this is using the TPM many modern PCs have (and which Windows 10 will require as of july 2016 for Windows 10 logo certification of PCs)


Symmetric key as proof of ownership of a session? I have a question, or rather multiple questions that all relate to the same topic.
I am building an application with both a frontend (FE) and a backend (BE). All communication between FE and BE is protected with TLS. The BE contains an endpoint on which the frontend can register a new session. When setting up such a new session, a few things happen:

FE sends a request (TLS protected) to BE, sharing a Curve25519 public key from a freshly generated Curve25519 keypair.
BE receives this request. Creates a new Curve25519 keypair, uses HKDF to calculate a shared secret (using as input FE public key, BE private key and a salt) and ultimately create a new symmetric session key (ChaCha20-Poly1305)
BE creates a new 32-byte (256-bit) session ID and keeps it in memory together with the session key.
BE sends back the session ID + salt + public key from freshly generated Curve25519 keypair.
FE uses BE public key + salt + FE private key to calculate same secret and create the session key.

Again I want to emphasise all of the above communication (so the request + response) happens over TLS. For all future communication, FE will encrypt all requests using the session key. The encrypted request is encoded to base64, and put in a JSON request body together with the unencrypted sessionID:
{
    "sessionID": "SomeString",
    "encryptedRequest: "base64 encrypted request"
}

These requests are then send (along with the unencrypted session ID) over a TLS connection, resulting in double encryption. When BE receives these requests, it will lookup the required session key by using the provided session ID. Then, it will decrypt the encryptedRequest field and forward it to the appropriate endpoint.
Some questions I have with this setup are:

Because all requests are encrypted with the session key, can that act as a form of proof that the client is the real owner of the session ID? e.g. If the session ID somehow is stolen, it can still not be used to communicate to the backend as you still would need to have ownership over the shared secret.
How much added security does this setup give if for some reason the TLS connection is broken into? (e.g. due to MITM, or because the TLS-level encryption is broken)
Does this setup aid in API obfuscation? E.g. client-side you can install software that - prior to TLS encryption occurring - can inspect all incoming and outgoing traffic. For my application, they would only see requests that are already encrypted. Is it easy to work around this?

I'm curious about what you guys think. I've been experimenting a bit with these topics (i'm by no means a cryptography expert) and I would love to learn more.

Because all requests are encrypted with the session key, can that act as a form of proof that the client is the real owner of the session ID? e.g. If the session ID somehow is stolen, it can still not be used to communicate to the backend as you still would need to have ownership over the shared secret.

That depends. I don't see any explicit check for this defined. I also don't see any specific mention of defusing replay attacks (in both ways, as there is only one encryption key, it seems). Also, 32 bit isn't much to avoid either integer overruns or collisions, so an attacker with another valid TLS key may retry until such an ID is created.

How much added security does this setup give if for some reason the TLS connection is broken into? (e.g. due to MITM, or because the TLS-level encryption is broken)

None, as you don't perform any authentication of or after the key exchange.

Does this setup aid in API obfuscation? E.g. client-side you can install software that - prior to TLS encryption occurring - can inspect all incoming and outgoing traffic. For my application, they would only see requests that are already encrypted. Is it easy to work around this?

No, it won't aid in API obfuscation, and yes, it is easy to work around this because of 2. And if you have an unencrypted part then an attacker can do an MITM there.
Better to just rely on TLS.


Are there MD5 collisions for inputs of different length? There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length to have the same MD5 (or same hash in general). Is it correct? Is there any proof of that?

Or otherwise examples of inputs of different lengths with the same MD5?

So the problem with different-size MD5 collisions is that our collision-finding tools aren't yet powerful enough to find them efficiently.

First we need to understand the rough idea of how MD5 works, using the Merkle–Damgård construction where essentially you keep some state $s$ and some current input block $m$, combine them with a compression-function and use the output as new state $s$, with the last state effectively being the output.

Now what our current techniques can achieve is that given (arbitrary) states $s_1\neq s_2$, they can find a sequence of message blocks $(m_1,m_1',\ldots)$ and $(m_2,m_2',\ldots)$ that when fed into the hash function will yield the updated states to be the same $s_1'=s_2'$ (this is called a "chosen-prefix collision attack").

The problem is, that after $s_1',s_2'$ the messages need to be equal (including length) to preserve the collision or you'll have to re-unite the states again if you feed different messages again. This is a problem because MD5 appends the length of the processed message to the message just before feeding of to the final compression function call. In particular that means that when you use different-length messages your last blocks will differ and as it is the last block you can't just feed message blocks to make up for this difference again.

In theory you could try to defy this problem by either finding a collision on the compression function that involves this little control on the last few bytes, but practically it appears nobody has done this (yet).

However, if you are looking for a brute-force collision, which would entail about $2^{64}$ expected work and $2^{128}+1$ worst-case work, you can just have a 128-bit counter $\mathbb i$ and continually hash $\mathbb i$ and $\mathbb i\|\mathbb i$, looking for hashes which appear in both sets. Any such entry, which is guaranteed to exist after $\mathbb i$ cycled through its whole range will be a different-length collision.


Would modifying the key of an arbitrary ARX cipher make it harder to break? Consider a simple ARX block cipher in which after each block is encrypted, the key is rotated and/or XORed by some variable value. Would this make the key any more secure, or just be a waste of time? Could it somehow make the key less secure?

For example, if the key is 0101 and after a block is encrypted the key is rotated left by the last 2 bits (in this case 01). So the key for the next block encrypted will be 1010.
Alternatively, the latter 2 bits are used to seed a pseudo-random number generator, and the key is XORed with the result.

Sorry if this is a dumb question, I am very new to cryptography as a whole, and this question came to mind while going over some resources for a course I will be taking this fall.

Consider a simple ARX block cipher in which after each block is encrypted, the key is rotated and/or XORed by some variable value

It sounds like you are asking "What if we apply a key schedule at the mode of operation level?"

If the cipher is strong, then there should be no need to modify the key between invocations of the encryption function; The fact that the cipher is strong implies the adversary cannot obtain the key from plaintext-ciphertext pairs, so "more security" is not obtained by modifying the key in any deterministic way.

  Could it somehow make the key less secure?

Yes, absolutely: Assume that your publicly-known deterministic key evolution function simply outputs all $0$, regardless of input; We might say that this is a pathological example, but it's really just an extreme case of "how biased is your function" - your function could produce outputs that are more easily guessed than the input to your function.

  For example, if the key is 0101 and after a block is encrypted the key is rotated left by the last 2 bits (in this case 01). So the key for the next block encrypted will be 1010.

With this specific example, you stand to leak key bits by side channel information: The secret data dependent rotations can leak information about the operands to external observers. If an adversary can somehow cause the encryption method to be invoked at will, and they can observe timing information, then they can potentially use this to recover bits of the key.

Basically, more is not necessarily better when it comes to cryptography: You want to do exactly only what is required to accomplish the goal, and no more; Excess operations simply create more attack surfaces.


Feedback on rolling my own entropy gatherer First of all, I don't recommend doing this. This was something I created when I didn't know better and didn't have a solution available to me.

Long ago I created my own entropy gather for a cryptography project. I used a window and had the user type with the keyboard while moving and clicking the mouse. I kept the milliseconds of the timestamp on each message, as well as the X, Y of the mouse and the values of the keystrokes.

Basically in designing the method I examined  the messages and only kept the values that changed significantly (unpredictably) from message to message. For example the date, hour and minute of the message was discarded since all the messages were collected on at close to the same time.

I then created an algorithm to "stir" the pool. This just used the built in simple random number generator to shuffle the values around a user defined number of times. After the fact I wondered if this was a good idea or not.

After that I would extract numbers from the pool (removing them not to be used again) each time I needed a random value as a seed. I would warn the user if the pool got to small and allow them to add more entropy. I would stir the pool before each use and after gathering.

I know that today there are cryptographically secure random number generators built into most operating systems and development libraries, so I would discourage anyone from rolling their own solution today, but I am curious if the methodology I described was effective and if there was anything I did or didn't do that could improve it.

You should not remove any part of the pool, or do some more-or-less random selection out of it. Instead, just hash the whole thing with SHA-256. This will get you all the entropy there is to get out of the data, up to 256 bits, which is more than enough.

Once you got 256 bits of entropy, i.e. you accumulated physical measures which should amount, together, to at least that many bits of entropy, and then you hashed all of it, into a single 256-bit value, then you can use that 256-bit value in a good PRNG, which will produce as many random bits that you could wish for (i.e. bits computationally indistinguishable from true alea, which is the best you can practically hope for or actually need).

Now that's exactly what is happening behind /dev/urandom, CryptGenRandom(), java.util.SecureRandom, or whatever name your OS gives to its strong random number generator.


What prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic? Does the size of base, exponent, and modulus thwart the Giant-step/Baby-step algorithm in solving DLP using modular arithmetic or is it the use of a property of a particular prime as the modulus, or something else?

The Discrete Logarithm Problem for a fixed public prime modulus $p$ and generator $g$ of multiplicative order $q$ in $\Bbb Z_p^*$ (that is, $q$ is the smallest positive integer with $g^q\bmod p=1$ ) asks, given $y$ obtained as $y\gets g^x\bmod p$ for a random unknown $x$ in $[0,q)$, to find that $x$ (which is unique).

The Baby Step/Giant Step algorithm solves that problem with $\mathcal O(\sqrt q)$ multiplications modulo $p$, ignoring the cost of memory and memory accesses. The cost of one multiplication modulo $p$ grows slightly slower than $\mathcal O((\log(p))^2)$.

Thus what "prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic" is mostly choosing $p$ and $g$ such that the multiplicative order $q$ of $g$ is large enough: at least twice the desired security level. Say, 256-bit for 128-bit resistance.

Update per comment: The Pohlig-Hellman DLP algorithm essentially attacks each prime factor of $q$ separately. Guarding against it is obtained by insuring that at least one prime factor of the multiplicative order $q$ is at least twice the desired security level.

Further, due to yet other DLP algorithms (GNFS in particular), $p$ must be considerably larger than twice the desired security level (2048-bit $p$ should be a bare minimum nowadays).

The multiplicative order of any element in $\Bbb Z_p^*$ is always a divisor of $p-1$. Hence one way to ensure that $q$ is large and has a large prime factor is to choose prime $p$ as large as required per the above, and such that $(p-1)/2$ is also prime (that is, choose $p$ as a safe prime). It ensures $q$ is among $\{1,2,(p-1)/2,p-1\}$, and allows to choose $g$ leading to one of the two later options (both used in practice), giving a huge security margin w.r.t. Baby Step/Giant Step (or Pollard's Rho) and Pohlig-Hellman combined.

Another option is to first choose $q$ (usually as a prime at least twice as wide as the security level), and build $p$ as a large enough (thus much larger) prime such that $q$ divides $p-1$; then construct $g$ of multiplicative order $q$. That builds a so-called Schnorr group. It is used in Schnorr signature and similar, including DSA, with the advantage of shortening the signatures.


RSA encryption using multiplication Generally in RSA we encrypt as $m^e \pmod n$. Will RSA work if we replace the power by normal multiplication? $E = (m \times e) \mod n$  and decryption as $c \times d \mod n$. What will be $d$ disadvantage if it works ?

Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only the public key (i.e. compute $d = e^{-1} \text{ mod } N$). Hence this scheme is completely broken.

Note that this scheme only works if $e$ and $N$ are coprime otherwise no $d$ such that $e*d = 1 \text{ mod } N$ exists.


Why the output length of a KDF should be the same as the underlying OWF? Quote:

  The chosen output length of the key derivation function SHOULD be the same as the length of the underlying one-way function output.

Could someone please help explain the benefits and concerns?

It would be a benefit for badly defined PBKDF's such as PBKDF2. PBKDF2 re-iterates all the iterations if you ask more than the output of the one-way function. This requires the server to perform additional calculations. The attacker however might be able to validate that a guessed password is correct without going through the same number of iterations.

This would for instance be the case if you split the output into a 256 bit key and 128 bit IV when using PBKDF2 - SHA-256 - in that order. The key would be calculated first, then the entire work of hashing is repeated for the IV. But an attacker would only need the first 256 bits to confirm a guess.

Some older KBKDF's and PBKDF's such as KDF1/2 and PBKDF1 also simply do not allow for outputting more than the output size of the one-way function.

Newer KDF's such as HKDF (a key based KDF or KBKDF) and Argon2 (a password based KDF or PBKDF) have been specifically designed to allow for more output than the one-way function. It should however be remembered that retrieving a 256 bit key from a function that can only provide 160 bits of security will not give you 256 bits security.

This might be the main reason for the given statement.

That the output size needs to be precisely the output size of the one-way function is, in my opinion, hogwash. It is perfectly reasonable to ask 512 bits of output and split it into two times 256 bits, while the one-way function only provides 256 bits of security. It is nicer to use two labels and perform a KBKDF twice, but that's not necessarily more secure.

Besides that, it is certainly completely valid to ask for fewer bytes than the one-way function provides.

Commonly the output size is a configuration parameter for the KDF. But you might want to consider to use the most up to date KBKDF or PBKDF if you ask for more bits than the one-way function provides. As long as you don't fool yourself with regards to the key strength provided by the KDF, you should be perfectly safe (at least in theory: specification / implementation failures and catastrophic breaks of KDF's are not covered by this insurance).


Storing email addresses in plain sight What would be the best approach for storing a list of hardcoded email addresses in plain sight (in a public JS file or such)?

The site is pretty low-key, for a small community of friends. Starting out, I'd like to just hardcode some email addresses as hashes, which would then be checked against a users input to check that they are an invited member of the site.

Rather than creating an api with authentication etc, I'd prefer to keep it all in the front end. The 'account' would only be used for tracking user and guiding them to the right resources. Nothing financial, or sensitive.

I understand I could use an MD5 hash, though I hear this would be easily cracked?

If you have or just want to have just the email address for authentication then you could store a password hash as value in the public JS file. You could for instance use PBKDF2 with salt and relatively high iteration value. Basically, if you do that, you treat the email address as a passphrase.

However, please keep in mind that an email address is really easy to guess, and therefore an adversary could just try email addresses and try to get to the same hash in an offline attack. It's unlikely that the iteration count / work factor will be a prohibitive measure. However, your friends could use a complex mail address if they would wish (e.g. Google allows to use address+something@google.com as alias for address@google.com) and be more secure.

MD5 - or any other cryptographically secure hash - is not secure for password hashing by itself.

Another issue is that adversary can change the code in the client and skip any verification that takes place in there. So your security should at least be partially implemented at a different place than the page anyway.
Generally you'd try and secure your system starting at the server. For that however you do need code execution on the server. If the server can e.g. store the hash, and limit the amount of tries, then you're already much more secure.

If the system is for sending messages then you could also put some verification / security at the receiver of the messages if the server is unavailable to you.


Can libsodium's X25519 encryption construction be generalized? It is my understanding that libsodium's sealed_box is based on X25519, a Diffie-Hellman function: By combining the X25519 key agreement with a symmetric cipher and having a recipient derive the symmetric key, a message can be constructed that can only be decrypted by making use of the X25519 private key.
Can this construction be generalized to other Diffie-Hellman functions (ECDH with other curves, or the ordinary non-EC Diffie-Hellman)?

Yes. The general construction is called IES (Integrated Encryption Scheme), most often practiced as ECIES (elliptic curve IES). The principle is the same: use the “key agreement” primitive (DH, ECDH, X25519, …) to construct a secret that is shared by two parties, each of which knows both sides' public keys but only their own private key. The shared secret is then used to derive a secret key for symmetric authenticated encryption.
I don't know if libsodium's crypto_box conforms exactly to an official ECIES standard (there are many) in terms of how it formats the data. ECIES standards have a lot of options in terms of the group (DH group or EC curve), on what data is included in the derivations, and on the freshness of parameters (e.g. ephemeral vs multiple-use keys). Depending on these options, the resulting constructions may have different properties in terms of nonce-misuse-resistance, resistance to a compromise of the private key, resistance to side channels, etc. But the basic principle of hybrid encryption constructed on top of a key agreement is the same.
Some reading on how the details of how IES is done influences secondary security properties:

Neil Madden, Public key authenticated encryption and why you want it (Part II) — “Option 2: Authenticated Encryption from Diffie-Hellman” ff.
A short discussion of ECIES vs. crypto_box for zcash


Is a Feistel structure based cipher IND-CPA? Using the format of the "game" to establish if a cipher is IND-CPA secure:

The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger.
The challenger selects one of them at random and encrypts it with the symmetric key and gives cipher-text C.
The adversary has to guess which message was encrypted based on C with a probability greater than 1/2 for the cipher-text to be distinguishable.

If the challenger is using an encryption algorithm only based on Feistel structures, would it be possible to always correctly identify, which of the messages the challenger encrypted?

If the challenger is using an encryption algorithm only based on Feistel structures, would it be possible to always correctly identify, which of the messages the challenger encrypted?

No, it will not always be possible to have any such distinguisher, even if we assumed that the attacker had infinite computing resources (!); all we need to assume is that the attacker has a bound on the number queries he is allowed to perform.

We can take advantage of the well-known fact that Feistel structures can implement any even permutation (possibly with a truly huge number of rounds; however the question didn't introduce a bound on the number of rounds); hence it would be possible for a well-chosen set of Feistel structures to produce any even permutation with equal probability.

And, given an attacker that is bounded to no more than $2^N-2$ queries, it is impossible to distinguish a random even permutation from a random permutation.


Cracking WWII-era codes - code found on a pigeon's leg in Surrey A recent BBC article entitled WWII code 'may never be cracked' posted a code:

AOAKN HVPKD FNFJW YIDDC
RQXSR DJHFP GOVFN MIAPX
PABUZ WYYNP CMPNW HJRZH
NLXKG MEMKK ONOIB AKEEQ
WAOTA RBQRH DJOFM TPZEH
LKXGH RGGHT JRZCQ FNKTQ
KLDTS FQIRW AOAKN 27 1525/6

According to the article the code was found on the leg of a pigeon in a chimney in Surrey a few weeks ago.

Do we have enough information about WWII-era codes (presuming that is when it comes from), such as the one above, to figure out what these long-forgotten codes might say?

EDIT: This was discussed on slashdot.

A problem with this message is that the image in a press release from GCHQ differs slightly from one in a New York Times article, although the paper, with its tears looks the same.

The image below shows the two side by side, the one on the left from the NY Times and the right from GCHQ. There is a slight difference in the style of writing, i.e. more sloping to the right in the GCHQ image. There are also some word differences: word 7 is GOVFN from GCHQ and FOVFN in the other.

That the message was found in Bletch***ing***ley, Surrey may be a bigger clue.


Forward Security of Symmetric Encryption Schemes with LFSR based PRNG Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?

Once an attacker knows $2L$-bits of an $LFSR$ of length $L$ with unknown taps, they can use the Berlekamp-Massey algorithm to construct your LFSR. If the taps are known, then only $L$ bits are required. Therefore your PRNG based on a single LFSR will fail. They were popular but anymore.

LFSR's has no next-bit security. From previous known states, the next bit is exactly can be found.
More generally, an attacker that knows the current state, they have more power than predicting the next outputs, they know the next states of your random number generator.
LFSR's can be run backward, which will reveal the previously generated random numbers. Once an attacker accesses the system, they will able to decrypt the previously encrypted messages. See the Double ratchet which is used by Signal.


Is there any implementation of scrypt that allows a specific limit on memory? The answerer has commented that scrypt's memory use is "only a function of r". $\:$ However, he has

not addressed my argument that it also depends on N, in one of my comments from over 5 days ago.

I had somehow gotten the impression that scrypt offered a separate memory-factor in addition

to its main work-factor. $\:$ However, the (original?) scrypt paper does not have such a parameter.

  Do any implementations of scrypt offer a way to limit

  its memory usage without that limiting its runtime?

Looking at that paper, I see that there would be an obvious way to do so: in the definition of

ROMix (on page 6), add an input M and replace the instances of N in steps 2 and 7 with M.

Alternatively, one could replace those two Ns with max(M,N) and replace

the N in step 6 with max(N,(2*N)-M), or with something similar to that.

Deﬁnition 4: The key derivation function scrypt is deﬁned as
  scrypt(P, S, N, r, p, dkLen) = MFcryptHMAC SHA256,SMixr(P, S, N, p, dkLen)

  The limits on the size of p and dkLen exist as a result of a corresponding limit on the length of key produced by PBKDF.

  Users of scrypt can tune the parameters N, r, and p according to the amount
  of memory and computing power available, the latency-bandwidth product of the
  memory subsystem, and the amount of parallelism desired; at the current time,
  taking r = 8 and p = 1 appears to yield good results, but as memory latency
  and CPU parallelism increase it is likely that the optimum values for both r and
  p will increase. Note also that since the computations of SMix are independent, a
  large value of p can be used to increase the computational cost of scrypt without
  increasing the memory usage; so we can expect scrypt to remain useful even if the
  growth rates of CPU power and memory capacity diverge.

Source.

This SO answer elaborates on the factors more clearly.

  $N$: General work factor, iteration count.
  $r$: blocksize in use for underlying hash; fine-tunes the relative memory-cost.
  $p$: parallelization factor; fine-tunes the relative cpu-cost.

Source.

If you want to increase memory hardness, raise r. This will also raise execution time, so you might want to lower N at the same time.


why is FPGA suited for Cryptography applications? FPGA is suited for acceleration of algorithms that can be pipelined, or for network acceleration (in-line processing).

Why is FPGA suited for cryptography / security applications? For example AES, SHA... what features of those workloads makes then adequate for FPGA?

The answer is simple. When you have a job to be done you choose toolkit which would accomplish it in a fastest possible way.CPUs are usually multi-tasked they would be running your OS beside running your cryptographic toolkit. Also, colloquially speaking, FPGA circuits can be designed for partcilar sort of computaion in hardware reaching a far higher efficiency in terms of energy utilization and performace.

So it is not that FPGAs have some special features that CPUs lack. Its just a matter of specialization in circuits construction for a specific task. ex. SHA.


New Improved Probabilistic version of RSA On the 2nd page of "New probabilistic public-key encryption based on the RSA cryptosystem" by Roman'kov (PDF), at last it says Alice can find "f" of order "l" with least probability of (1-1/l). I cannot understand how they came up with this probability.
Can anyone help me with this.

The paper is rather sloppily written, however it can be changed into the correct statement.

The statement in the paper is:

  She takes randomly elements $f \in F^*_p$ and checks whether or not $f^{2x}=1$. With probability at least $1 − 1/\ell$ she finds $f$ of order $\ell$.

As written, that's wrong.  However, if we modify it to:

  She takes a random element $f \in F^*_p$ and computes $g = f^{2x}$; if $g \ne 1$ (which will happen with probability $1 − 1/\ell$), then $g$ will be of order $\ell$.

Then it is a correct statement (and is the standard way of generating random elements of order $\ell$).

There are a number of places in the paper like this; places where, as written, it doesn't make much sense, but if you know your number theory, you can deduce what the author actually meant.  I suspect that this can be modified to make a secure cryptosystem; however whether it does have any advantage over RSA (and whether it's actually safe for multiple users to use the same modulus and different exponents) is far less clear.


How exactly would someone crack a private key passphrase? Lets say for a PGP/GPG pair with a passphrase.

Typical ways include

Dictionary attack
Common modifications of dictionary words
Concatenation of dictionary words
Brute force


How does DSA provide non-repudiation in proving a document was properly displayed (not altered or displayed incorrectly)? I am building an iOS app that allows the user to sign a document served to them by a web server. So that page of the app simply has a document in the top pane, and at the bottom pane, a place to sign with your finger.

So, I want to use DSA to allow this app to sign that doc and have the non-repudiation property. But a colleague brought up what seems to be a critical flaw.

If I send the iOS app a document, the user can still cryptographically sign it (with the signature bitmap and timestamp) using their private key, but we might actually be displaying some other document. In a sense, the crypto doesn't actually provide any assurance that the signer was looking at the document in question when he signed -- he could have been looking at a picture of Mickey Mouse. It just proves that we had that document in RAM, and that the user signed something.

So clearly it's easy to tell using DSA if someone mistakenly sent you a digitally signed picture of Mickey Mouse instead of a contract. But what if the problem was at the view/display layer, and in point of fact, the correct document was in RAM, and just displayed incorrectly? (For example, say I had some horrid bug that would randomly replace pixels on the screen with pictures of Mickey Mouse at the OS layer?) Then, we would send a seemingly valid signature of the seemingly appropriate contract, while the user in reality had been looking at Mickey.

I'm trying to get my head around how the crypto solves this problem. I'm sure it's something trivial but I'm having so much trouble figuring it out. Any thoughts would be very much appreciated. If this is one of those "nature of the beast" type trust questions, how does Adobe's implementation in PDF provide non-repudiation?

I'm trying to get my head around how the crypto solves this problem.

It doesn't. You need to trust the platform you use to do the signing.

For instance, my bank has replaced the "signature" generation device that I previously used with one that displays the actual transaction, so I don't have to trust the information on the computer screen that much.


Where can I get information on how to implement AES? I want to write AES from scratch without using the built in libraries of java. I know there are hundreds of AES programs (and websites) out there but I can't seem to find a site that gives me the details I think I would/should need to write my own Java program.

I know that AES has S-boxes like DES has. Were would I look for them? Also, I would like more info on the AES "counter mode".

The AES standard is reasonably clear, and (theoretically) sufficient to implement the AES itself. For block cipher modes of operation (including counter mode), see NIST Special Publication 800-38A.


How to pass an arbitrary signature to a certificate I am trying to sign certificate (X509) using secret sharing. That is shareholders combine their signatures to produce the final signature which will be in this case the signed certificate. However practically from my understanding only one entity can sign a certificate. Therefore I want to know:

which entities or data of the x509certificate are actually taken as input to the signing algorithm?
Ideally I want this data to be signed by the shareholders and then the final combination will be passed to the X509certificate as valid signature.
Is this possible?
How could it done?
If not are they other alternatives?

I'm not quite sure if I understand you correctly.

As far as I understand it, you want to produce a threshold signature on the hash value of an X.509 certificate. It is not sure if you require a distribute key generation of the private key, or you are in possession of the signing key and distribute shares of the key to all stakeholders.

1) Actually, in case of X.509 certificates you sign the hash value of the certificate fields.

2&3) Yes this is possible by using any threshold signature and using the hash-then-sign paradigm. You may look here for a related question.

4) Either run a distributed key generation or generate the keypair for the signature scheme and distribute the shares of the private key to the stakeholders (put the public key in your (self signed) CA cert). Then, to sign an X.509 certificate, compute the hash value and run the distributed signing algorithm on it. Integrate the resulting signature in the X.509 certificate.


Are there cryptographic schemes that mask as unencrypted traffic? Are there cryptographic schemes that make encrypted traffic look like unencrypted traffic?

Well there is Steganography like Richie said in the comments it is essentially the art of hiding messages. This being said it is not comparable to any encryption algorithm (like AES) security wise. Though there are tools for steganography which requiere keys so they encrypt data before they hide it but this is not the essence of steganography since steganography is only about hiding the message.

If you are looking for a way to hide your messages this would be sufficient, if you want to properly encrypt it you can do that before hiding the message.

If you're looking for only an algorithm which mutates a text to a different text i'm afraid your out of luck. a home brew of a pseudo random pad where you make the key in such a way the words change like this:

plaintext: Welcome
key: kkdbnma
cipher text: Goodbye

Though this is insecure, it might be fun to play around with but it is not to be used in real life situations!

EDIT:
as pointed out Robert NACIRI there is also the use of subliminal channels as described by this wikipedia article. As it suggests it hides messages inside normal communications, read it through for examples and a better sense of how this works. It's quite interesting.


Measure Strength of Mix Mode Modular Arithmetic based Confusion Layer Strength of sboxes is generally measured by different properties eg non linearity, fixed points etc. If confusion is provided by Mixed Mode Modular Arithmetic (eg as in IDEA), how to measure the strength of this type of confusion layer? Also, my sample mixed mode modular arithmetic based confusion layer takes 64 bits input and generates 64 bit output.

The same principles (linear and differential cryptanalysis being most prominent) apply to Mixed mode confusion layers, though in general you may be limited to experimental analysis since the theory of such mappings is not so developed, being a mix of different algebraic structures.

If you have to do experimental cryptanalysis  a $64\times 64$ confusion layer will clearly be too large to experimentally compute exhaustive linear approximation tables, or whatever other tool you are using.

One specific innovation by Havard Raddum (see springerlink or his site at researchgate he will probably gladly send you a pdf) in his 4 round cryptanalysis of reduced IDEA-X/2 (a weakened variant) was to include "multiplicative differentials", after all you can apply differential cryptanalysis to any group.

If you focus on the $16\times 16$ substructures operating on "words" you can isolate the groups used in IDEA. However, this is quite difficult as well since a distributive law between the three group operations namely

$16$ bit XOR
Addition modulo $2^{16}$
Multiplication modulo $2^{16}+1$ where the all zero element is treated as the modulus $2^{16}+1.$

does not hold. Nor do the designers ever use the same group operation in a contiguous manner.

You may find reading Raddum's paper interesting since he makes a stab at treating multiple groups in a differential attack. Then you can see the papers which cited his.


Can zksnark prove DLP? Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?

final_exp_gadget<>() of libsnark could be a practical example to tune for DLP.
The idea is, "final exponentiation" is a part of Ate pairing, that is verified as a part of check_e_equals_e_gadget<>(), which stands for Groth16 verification equation.


DTLS vs direct use of AES. What are the threats unique for direct use of AES instead of DTLS? For regular traffic in mesh network (between Internet of Thing devices) customer decided to use one of two options:

DTLS PSK ciphersuite - DTLS based on pre-shared symmetric key
or direct use of AES - customer wants to minimize traffic between sleepy devices (battery should be alive for several months)

Questions:

What are the additional threats of second option (AES) that do not exist for first option (DTLS-PSK)?
How to mitigate these threats (say using AES in CBC or another mode and change IV, etc)? Not reinventing DTLS protocol manually and not with the same overheads as DTLS has.

There is mandatory requirement to share symmetric key between IoT devices within mesh network for regular traffic. This key fits for both options. (First joining of new device will use DTLS-PAKE - I mentioned this just in case - this is not important for this question).
Let's specify DTLS-PSK mode more exactly  - I'm going to use mbedTLS crypto library with define MBEDTLS_TLS_PSK_WITH_AES_128_CCM_8 is specified in cipher suite. Where CCM is mode for block ciphers that provides both authentication and confidentiality.

You appear to be quite familiar with the issues you face already, but I'm going to answer your question as literally stated nevertheless.

AES is a block cipher, so it needs to be used in a mode-of-operation in order to provide proper privacy (IND-CPA).

AES is a block cipher, so it needs to be used in a mode-of-operation in order to provide proper integrity (IND-CTXT).

Even with a good mode-of-operation (like AES-CCM), you don't get protection from replaying, reordering, and dropping of messages. For this you need a stateful mode-of-operation. What should this state be? It could simply be a number, but it doesn't necessarily have to be. In any case, this state needs to be managed and synchronized correctly between the two communicating parties. Can be tricky.
But in addition to this, you also need a choice of policy: do you allow messages to be dropped, but not reordered? Do you allow messages to be reordered, but not replayed? Do you allow some messages to be replayed/reordered within some window of acceptance? ...and so on, for any complicated combination of the above. Suffice it to say, getting this right can be subtle.

DTLS gives you all of the above. The question is, can you do it better? In theory it is certainly possible. But in the end you would probably end up with something which is very close to DTLS anyway. However, now you would have to implement all of this by yourself, giving you all of the problems associated with implementing cryptography that you are probably well aware of.
Ultimately, if DTLS gives you all of this out-of-the box, then trying to come up with something that replaces it strikes me as having a high risk of introducing problems and for relatively little reward. Thus, why not simply use DTLS? Or even better, use something built on top of (D)TLS which is explicitly designed for the IoT domain (like E4)?