Reason why “XOR” is a linear operation, but ordinary “addition” isn’t? I'm new in cryptography and try to read some articles in this field.
Many of these articles talk about non-linear S-boxes, and nothing more on what they mean by their non-linearity.

I have a simple question which I think will guide me through my problem:

why  is the XOR operation is linear, but ordinary adding (+) not‽
what is the definition of linearity?

They are both linear, but in different algebraic Groups.  Which is to say, xor is linear in any finite field of characteristic 2, while 'ordinary' addition is linear in the infinite field of the Real numbers.  Addition modulo $n$ (which is more cryptologically significant than addition over the Reals) is also a linear operation, but in the ring of integers $\mathbb{Z}_n$.

A linear function is simply one that can be accurately described by an algebraic equation (in some particular algebra or another) where none of the terms are of degree greater than 1.

So the xor of two variables can be accurately described by a linear algebraic equation in a finite field of characteristic 2.  But there is no linear equation in the algebra of $\mathbb{Z}_n$ (for $n > 2$) that can accurately describe the xor of two variables.  Conversely, the addition modulo $n$ ($n > 2$) of two variables can be accurately described by a linear equation in $\mathbb{Z}_n$, but not by a linear equation in any finite field of characteristic 2.

If none of that made any sense to you, that's OK.  You just need to read up about Abstract Algebra, and Fields, Rings and Groups.  It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.


Using a nonce as a salt for key derivation I'm currently playing a bit with PyNaCl (python binding to libsodium) and I want to use the secretbox for symmetric encryption between two parties, which means they both must know the (in my case randomly generated) nonce, so I would just send it with the ciphertext.
I derive the secret key with argon2id from a password, but this needs a salt.
So I was wondering whether it would be dangerous to use parts of the nonce as the salt, so I only have to transmit the nonce.
I don't think it would be problematic because the salt is just used to prevent rainbow table attacks etc.
I know it is dangerous to reuse a (key,nonce)-pair, but since the key is derived from both a password and the salt and the nonce is randomly generated every time, I don't see this as a problem.
Am I correct or is there a problem I'm not thinking about? Or is there a better approach? Also I'm asking more from the academic side of things and less from my implementation, that was just to explain how I came to the question.
In case there is already a similar question, please point me towards it, I did try the search but nothing really fitting came up.
Tl;dr: Is it generally cryptographically problematic to use a part of nonce for an AEAD scheme as a salt for a KDF ?

I derive the secret key with argon2id from a password, but this needs a salt. So I was wondering whether it would be dangerous to use parts of the nonce as the salt, so I only have to transmit the nonce.

Yes, the salt is used to eliminate the rainbow tables. Keep in mind that the rainbow tables can be build up to some degree. If we consider that the Bitcoin miners agree to build a rainbow table instead of mining, they can build a table the can most cover $\approx 2^{92.8}$ passwords in a year. This is not considered the case that the slowness of the password-based key derivation functions, like PBKDF2, scrypt, Argon2. If we consider that they are parametrized to slow like $2^{20}$ then the coverage is reduced to $\approx 2^{72.8}$.
Within the Kerckhoffs's_principles - that is all but the key is known to the attackers - the attackers will always choose the shortest path to achieve their target whenever they see that. If you use the nonce and send it in public, they will try to find it. If the password is not good, they will find it! However, if the passwords have good entropy like diceware or bip39 is used to generate one,  there is no problem. Keep it above 128-bit entropy then your password is safe and the derived the key. Keep in mind that, the users tend to have bad passwords. Either you should educate them about using better passwords like generated by the diceware method or enforce them on some stupid rules that cause hard to remember passwords xkcd:936. In your case, you should generate a good one beforehand. You should also put an expire date-usage for the password, too. Or better, use a randomly generated key!.

Or is there a better approach?

Use Diffie-Hellman Key Exchange(DHKE) to exchange (establish better) the keys. One should prefer the Elliptic version of that ECDH. After the key is established then use HKDF to derive the key of the required length. Remember to use all of the exchanged keys. DHKE/ECDH That will provide you the forward secrecy as long as you and your friend deleted the keys after using them.
Actually, there is already a solution in the library; Crypto_box.


PRNG with onto state update function Consider a (hypothetical) PRNG where the state update function is onto, but it is easy to find the set of preimages (so not one-way).  That is, if an attacker is given the internal state of the system, say state $s_n, s_{n+1}, ..., s_{n+m}$, the "true" previous state $s_{n-1}$ obtained by the user could be any one of multiple states in an infinite set $S$.  So the attacker knows $s_{n-1} \in S$, but assume $|S|$ is large or infinite, so the attacker must guess the "true" $s_{n-1}$ state.  Does such a PRNG exist?  And, would one be able to call such a PRNG "backtracking resistant"?

Something I am unsure of is whether such a PRNG would by default be cryptographically secure: because the state update function is onto, the "true" previous state could have been, with equal probability, any one of the states in $S$, so the previous state would almost be trivially unpredictable, implying such a PRNG would be cryptographically secure.  Where does my logic go wrong here?

The state of a stateful algorithm is its “memory”. One round of the algorithm can be modeled as a function from $S \times I$ to $S \times O$ where $I$ is the input to one round and $O$ is the output from one round. For a PRNG, $I$ would either be a singleton (i.e. no input, just a request to generate more output), or a small amount of information such as the requested output size, or some additional entropy to inject. $O$ is the chunk of pseudorandom output.

The size of the state before and after the round is the same. So for a given input, the state update function is onto (surjective) if and only if it is one-to-one (injective).

If you have a state update function that is onto but not one-to-one, it means you're working in a different model where the size of the state decreases at each round. Your PRNG would have a limited lifetime since the size would eventually shrink to near-zero (near-zero being any size where the adversary can realistically enumerate the possible states). That would limit its usefulness.

In such a case, just because the knowledge of the current state alone doesn't allow the attacker to be certain what the previous state was doesn't particularly confer any security. Security is not plausible deniability. To make a system secure, it isn't enough to make it so that the adversary cannot prove beyond a doubt that they've broken it! You actually need to make it effectively impossible to break. It is very common that the adversary has some partial information and not just the one piece of knowledge that you're focusing on. For example, suppose that in the previous round, the PRNG was used to generate 32 bytes of data, out of which 16 bytes were used as a key and 16 bytes were used as an IV, and the adversary has been able to see the encrypted message and now wants to decrypt it. The adversary knows the IV, i.e. they know half of the output of the PRNG, and they're looking for the other half which is the key. In order for the PRNG to have backtracking resistance, you need to ensure that the knowledge of the current PRNG state plus the knowledge of the IV is not enough to reconstruct the previous PRNG state. Maybe the knowledge of the current PRNG state alone is not enough, but that is not at all helpful in the actual scenario where the adversary also knows half of the output.

There are real-world PRNG where it's trivial to inverse the state update function, i.e. to find the previous state if you know the current state (and possibly the corresponding output). But by definition, they are not backtracking resistant.


Determining Involutary Keys in Substitution Ciphers How would I be able to show that a key $K=(a,b)$ is involutary for an Affine Cipher over the integers modulo n?

Similarly, is there a way to generalize the conditions for a key to be involutary for a substitution cipher?

(Involutary keys are keys for which the encryption function is equal to the decryption function $e_K=d_K$)

If $E(x) = ax+b \bmod n$, and $E(E(x)) = x$, then you need $a(ax+b)+b = x$, or $a^2x + ab + b = x$.  So any (a, b) where $a^2 = 1$ and $b(a+1) = 0$ will do it.  There are always solutions $(1, 0)$ (which corresponds to not encrypting) and $(-1, b)$.  Depending on the value of $n$ there may be other solutions for $a$.  There are only those two for $n = 26$, but there are a total of 4 solutions for $n = 36$.


DES-CBC with random IV - how big is the keyspace? Can COTS tools crack it? I've spent the night reversing the implementation of the 'Basic Text Encryptor' from Jasypt [1]. The algorithm is defined in documentation as 'PBEWithMD5AndDES'.

The implementation is this:

A random 64-bit salt is generated
The secret is generated as

secret = password + salt
for i in range(0, 1000):
    secret = md5(secret)

The first 8 bytes of the secret are then used as the DES passphrase, and the last 8 bytes of the secret are used as the IV, and used to encrypt data with DES-CBC.

Given this, am I correct in thinking the total keyspace for the implementation is 120 bits (56+64)?

I have written a proof of concept reversal in python, but I'm interested in calculating how long it would take to brute force a real key. So far I've been unable to induce hashcat into decrypting something encrypted with this algorithm, and I'm unsure if it even can.

My questions are:

Is the keyspace really 120 bits?
Am I missing something or is hashcat not capable of cracking this?
Can other tools crack it?
Is it even possible to deduce correct outputs without making assumptions on expected output (eg all output must be ASCII data, or match a file header)

Edit: To reduce any confusion, my decryptor is as follows

import base64
import hashlib
from Crypto.Cipher import DES

passphrase = "123456" # Key used to encrypt
# Salt randomly generated at encrypt-time, and stored at
# the beginning of the encrypted data:
salt = base64.b64decode("vqmy2fiCipU=")
enc_b64 = "vqmy2fiCipVBIhiAzDfvTL0301DLgTqd"
enc_data = base64.b64decode(enc_b64)
if (salt != enc_data[0:8]):
    raise Exception("Salt does not match enc_data salt")
enc_data = enc_data[8:]

m = hashlib.md5()
m.update(passphrase.encode())
m.update(salt)
result = m.digest()

for i in range(1, 1000):
    m = hashlib.md5()
    m.update(result)
    result = m.digest()

# value of result is: md5("123456" + salt) iterated 1,000 times.

key = result[:8]
iv = result[8:16]
des = DES.new(key, DES.MODE_CBC, iv)
print(des.decrypt(enc_data).decode())
# > Hello World

[1] http://www.jasypt.org/api/jasypt/1.8/org/jasypt/util/text/BasicTextEncryptor.html

Is the keyspace really 120 bits?

No. It's still 56 bits, at least when multiple blocks are encrypted. For CBC mode then you can try and decrypt a block with the key, XOR it with the previous ciphertext block you should get a plaintext block. If you did this for the last plaintext block you'll have the PKCS#5 padding to find. If that's correct then you can start looking if you can produce valid plaintext.

If only one block is encrypted then the IV acts as a one-time-pad. In that case you will have to guess the password (presuming you have the salt of course).

  Am I missing something or is hashcat not capable of cracking this?

Could be. But it would probably not be that hard for an accomplished programmer to program it in. Hashcat seems to focus on the password hash itself. Assuming the password is not too complex, guessing it may still be the best way to try and decrypt the ciphertext.

  Can other tools crack it?

Well, cracking single DES can be done by specialized hardware for sure (a list is here). Asking for resources like that is off-topic though.

  Is it even possible to deduce correct outputs without making assumptions on expected output (eg all output must be ASCII data, or match a file header)

Well, other than the padding, yes, you must be able to test if the plaintext is comprehensible in some kind of way. However, if you decrypt many blocks the plaintext is likely not all that random, so you could test for that. If it compresses well, for instance, it may be worth another look (but compression is generally pretty expensive).


What is the relation between x y and r s in an ECDSA signature? I'm writing functions in C using OpenSSL and the EVP interface to interact with Intel SGX. One of those functions calculates an ECDSA (with SHA256) signature over some data.

The output of the ECDSA signature in OpenSSL is an ASN.1 structure with two integers, which I am assuming to be r and s. However, the data structure in Intel SGX that represents the signature has two values, x and y, each of fixed length 32 bytes.

#define SGX_SHA256_HASH_SIZE            32
#define SGX_ECP256_KEY_SIZE             32
#define SGX_NISTP_ECP256_KEY_SIZE       (SGX_ECP256_KEY_SIZE/sizeof(uint32_t))

typedef struct _sgx_ec256_private_t
{
    uint8_t r[SGX_ECP256_KEY_SIZE];
} sgx_ec256_private_t;

typedef struct _sgx_ec256_public_t
{
    uint8_t gx[SGX_ECP256_KEY_SIZE];
    uint8_t gy[SGX_ECP256_KEY_SIZE];
} sgx_ec256_public_t;

typedef struct _sgx_ec256_signature_t           <----- this structure
{
    uint32_t x[SGX_NISTP_ECP256_KEY_SIZE];
    uint32_t y[SGX_NISTP_ECP256_KEY_SIZE];
} sgx_ec256_signature_t;

I need to somehow convert the r and the s returned by OpenSSL's libcrypto to the x and the y used in Intel SGX. What is the relation between these parameters in the context of an ECDSA signature?

Yes, those encoded values are $r$ and $s$.

The ASN.1 integers are signed big endian values while the two fixed sized values are unsigned big endian. So the value field may be identical or it may not, if:

the value is equal to or larger than $2^{256 - 1}$: encoding this as signed big endian value will result in an additional byte at the left set to 00 to avoid it being interpreted as a negative value;
the value is smaller than $2^{256 - 8 - 1}$: encoding this as signed big endian value will result in fewer bytes.

To convert back and forward between the ASN.1 structure you need two functions: I2OSP and OS2IP, also specified in e.g. RSA PCKS#1.

You can follow the mathematical construct of course, but basically you need to do the following (where $n$ is the minimum required size in bytes to encode the order $N$, i.e. the key size in bytes). The reason to do it this way is that you likely are handed rep(i) - the unsigned big endian encoding of i rather than the number itself.

I2OSP(i, n):

if len(rep(i)) is two larger or more than n then error;
if len(rep(i)) is one larger and the leftmost byte isn't 00 then error;
if len(rep(i)) is one larger and the leftmost byte is 00 then skip this byte and return the rest of rep(i) as answer;
if len(rep(i)) as unsigned integer is identical to n, then copy rep(i);
if len(rep(i)) is smaller than n then left-pad with zero's until the representation is the same size as n.

OS2IP(i)

You may want to skip initial zero bytes of rep(i) and then left-pad with one zero byte in case the result would be interpreted as negative number (i.e. the most significant bit is set, or the initial byte value is 0x80 or higher).

Usually however this kind of functionality is included in big integer libraries.

Unfortunately the BN library of OpenSSL is internalized so you may have to operate directly on the encodings like above.

The ASN.1 encoding is a SEQUENCE of two integers, DER encoded, as follows:

30 LC 02 LR rep(r) 02 LS rep(s)

LR and LS are the size of the following unsigned integer representation, a single byte. The value of LR and LS may differ of course.

LC is usually a single byte length encoding of everything that comes next. However, if the encoding of r and s combined is over 128 bytes then a two byte encoding needs to be used: 81 LC. This is only the case for 521 or 512 bit curves though, so you can almost ignore it :)

I'll let you have the fun to implement it. Finding a BER/DER parser/generator would be recommended though.


How can I introduce a new method of encryption to the world? The cryptography algorithm I designed is a completely new algorithm and has no similarity to other existing algorithms. But because I am an ordinary person, I have no facilities and the ability to introduce this algorithm except through my website http://twincodesworld.com.

Given the fact that there are no absolutes, this algorithm may also have weaknesses that would affect its validity. Therefore, the website was created solely for testing this algorithm, so that the algorithm will be publicly released if approved by experts in the field. But despite repeated attempts and correspondence with reputable technology websites, nobody was willing to help me. Please guide me and help inform this.

because I am an ordinary person, I have no facilities and the ability to introduce this algorithm

Typically people write a paper and submit it to a journal. If it's any good and indeed "has no similarity to any other existing algorithms", it will definitely cause a stir. Most methods that you and I can come up with, have been thought of and are either used in modern encryption or were discarded for good reasons.

  this algorithm may also have weaknesses that would question its validity

That's a good thing to acknowledge! I remember when I invented my first encryption algorithm: I thought it would be unbreakable as long as it remained closed source (it'd be licensed to banks and stuff). I was super naive as a kid :)

Note that my personal story ended with me putting it up on some forum for security experts and someone breaking it despite not having the algorithm.

  the website was created solely for testing this algorithm

On your website, I do not see the algorithm. How are we going to test and validate it?

  the algorithm will be publicly released if approved by experts in the field

If you really want to do it that way, you can find and pay said experts to vet your idea. I'd advise you to just post it publicly and see if anyone can pick it apart. Only if there are no glaringly obvious flaws, you might want to have some experts look at it. And actually, if it's indeed good and new, experts will probably be attracted by themselves.

  despite repeated attempts and correspondence with reputable technology websites

Wait, crypto experts typically do not reside on technology websites. You'll be wanting to contact consultants and show them green stuff that they can use to exchange for bread and cheese at local stores.

  nobody was willing to help me.

They might have recognized that you are at the wrong address, or if you weren't, they'll have gotten many requests from rookies that wanted to validate their neophyte algorithms. Many rookies go down this path of (1) self-inventing things that are stupid and (2) not knowing how to publish. Myself included. I'm not saying that you are a rookie, but it's just likely that you are and people will often not find it worth their time to look at.

Crypto is seen as a hard field because it is indeed hard to do properly. It's not something that comes to you while in the shower, but typically requires years of study. By then, you will have seen how others published their work, so you'll know how to publish. Also, others might have seen your name already if you've been active in the field, which also gives you more credibility to start with.

  Please guide me and help inform this.

Release the algorithm and ask some hacker friends to take a go at it for fun.

And optionally, write a paper and try to get a journal to publish it. This should get it reviewed by others from the field.

By the way, having a bounty (as it's called; it's not a bonus) is nice. It'll definitely attract people to look at it. Just be prepared to pay out!

It's a little off-topic (your question is "how to introduce to the world", not "is it secure"), but if I may comment on your video and challenge:

Looking at the video, you're not entering any password. From that I assume that the key material is either (1) hard-coded in the program, (2) written into the output file or (3) does not exist (i.e. the algorithm is the key material). In case of option 1, that's bad practice; option 2 means it's just not encryption (it's encoding); and option 3 means you've violated Kerckhoff's principle.

On the other hand, I'm happily surprised to see that your challenge file has good entropy. When turning the ascii decimals into binary, ent gives me 7.93 bits/byte (for 3099 bytes of binary; testing with 3099 bytes of /dev/urandom I get 7.94 bits per byte). It's at least of better quality than what I invented when I was younger :).


Would a HMAC digest make sense in an RSA / ECDSA signature? When MD5 and SHA1 were broken there was, each time, a scramble to upgrade software and certificates to remove the offending algorithm. However, in each case, the HMAC variant of each hash function was not affected. In fact, unless I missed something, HMAC-MD5 is technically still secure.

In the context of signing data at rest using RSA or ECDSA, where performance is not the critical factor, would it make sense to use HMAC-SHA256 instead of plain SHA256 for the digest function in order to avoid a similar situation in future?

Something like this: $s = k \mathbin\Vert S(k \mathbin\Vert H(m,k))$ where $S$ is some asymmetric signing operation such as RSA or ECDSA, $k$ is a randomly generated key, $H$ is HMAC-SHA256.

If we view HMAC as a message authentication code or a PRF, this doesn't quite make sense: the security property for a MAC or a PRF assumes that the forger doesn't know the key, but you've given them the key $k$ in the signature.  But you have the right intuition that there is something here.

While a signature scheme in terms of $H(m)$ requires $H$ to be collision-resistant, a randomized signature scheme in terms of $H(r, m)$ requires $H$ to have only the much more modest property of enhanced target collision resistance, eTCR, which even MD5 may still exhibit.  So yes, what you suggest does seem to improve security in the face of unkeyed collision attacks on hashes like MD5 and SHA-1.

Obviously, if you're looking to be compatible with an existing system that uses ECDSA and can't be modified, the idea won't help you.  But modern signature schemes like EdDSA use it as part of the design, and you can always adapt an existing signature scheme to use it—NIST even standardized it in NIST SP 800-106, Randomized Hashing for Digital Signatures.  HMAC might work for the purpose too.

If you want more details, there's a lot of history here, so buckle up, buckaroos, for some story time!

Early history: Rabin signatures and the importance of hashing.
The first secure signature scheme in history, due to Michael O. Rabin[1], took a public key to be a pair $(n, b)$ of integers and a signature on a message $m$ to be a pair $(s, u)$ of an integer $s$ and a bit string $u$ such that $$s\cdot(s + b) \equiv H(m, u) \pmod n.$$  The signer, of course, knows the secret factors $p$ and $q$ of $n = pq$, in terms of which computation of square roots modulo $n$ is cheap, particularly if $p \equiv q \equiv 3 \pmod 4$.  The hashing and randomization served two purposes that Rabin articulated:

Allow the signer to vary $u$ until $H(m, u)$ admits a solution to the equation at all in $s$.
Reduce the probability that the signer accidentally reveals distinct square roots $s \ne s'$ of a common square, which would reveal the factorization of $n$.

We might also add a property that Rabin may have felt too obvious to state:

Compress long messages and destroy any structure, like integer perfect squares whose integer square root could be used to forge signatures.

It's unclear whether active attacks exploiting collisions were considered at this time, but provided that $H$ is collision-resistant, Rabin's scheme remains secure today by the modern standard of existential unforgeability under chosen-message attack (EUF-CMA), assuming suitable parameter sizes.  In fact, $H$ may not even need to be collision-resistant, but it's not clear that anyone noticed this until Schnorr a decade later.  Soon after Rabin, Hugh C. Williams[2] (paywall-free) showed how to efficiently compute squaring-type signatures deterministically with tweaks when $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$, obviating the need for randomization to achieve purpose (1).

Hashing, collision resistance, and discrete log signatures.
The importance of hashing appears to have been lost on Taher Elgamal initially in his discrete-log-type signature scheme[3], which was trivially breakable as a consequence—a signature under a public key $y$ on a message $m$ is a pair $(r, s)$ of integers such that $$a^m \equiv y^r r^s \pmod p,$$ which, for example, admits the trivial forgery $(0, 0)$ on the message $m = 0$ for any public key.  ($p$ is the standard modulus and $a$ is the standard generator of some subgroup of $\mathbb Z/p\mathbb Z$.)

Not everyone neglected hashing, though, and by the late '80s the importance of collision-resistant hashing was in the air: in Claus P. Schnorr's discrete-log-type signature scheme[4], where a signature under a public key $v$ on a message $m$ is a pair $(e, y)$ such that $$e = H(a^y v^e \bmod p, m),$$ Schnorr observed that the hash function $H$ need not be collision-resistant if it is randomized, and therefore could presumably be half the length a naive composition of, e.g., Elgamal with a collision-resistant hash would require for the same security.

The NSA—ahem, I mean, NIST—recognized the importance of collision resistance in a fixed hash in the Digital Signature Standard, FIPS 186, but carefully made the opposite of every good design decision of Schnorr[5] for fear of treading upon a patent, including randomization of the hash.  They also, of course, made DSA vulnerable to bad RNGs when making signatures, over the vociferious objections of contemporary cryptographers which NIST casually brushed off[6].

Provable security and industry standardization: RSA-PSS and RSA, Inc.
Early standardization of RSA like PKCS#1 v1.5 used an ad hoc way to shoehorn a message hash into an element of $\mathbb Z/n\mathbb Z$—specifically, into a minuscule sparse subspace of $\mathbb Z/n\mathbb Z$ which is useless for studying in relation to the difficulty of computing $e^{\mathit{th}}$ roots of a uniform random element of $\mathbb Z/n\mathbb Z$, which is the RSA problem and which is presumably more closely studied than the RSASSA-PKCS1-v1_5 problem.

In 1996, Mihir Bellare and Phil Rogaway[7] studied the security of RSA- and Rabin-type signature schemes in what more closely resembles the modern framework of ‘provable security’—showing how to use a forger as a subroutine in an otherwise cheap algorithm to compute $e^{\mathit{th}}$ roots modulo $n$, or to factor $n$ in the case of squaring-type schemes.  They were able to prove that if $H$ covers the whole of $\mathbb Z/n\mathbb Z$, then forgery of signatures $s$ satisfying the signature equation $$s^e \equiv H(m) \pmod n$$ called RSA-FDH, can be used for an algorithm to compute $e^{\mathit{th}}$ roots modulo $n$.

Bellare and Rogaway weren't satisfied with the specific theorem they proved, though, because its high cost for modest success probability meant nothing in the case where you sign lots and lots of messages.  So they considered a randomized variant, a probabilistic signature scheme or PSS, with the signature equation $$s^e \equiv \bigl[r \mathbin\| H(r \mathbin\| m)\bigr] \pmod n,$$ roughly.  Randomization in PSS enabled them to easily prove a stronger theorem.*  They also observed in their proposal for IEEE P1363[8] that using $H(r \mathbin\| m)$ did not seem to rely on collision resistance of $H$.  But what was actually standardized instead uses $H(r \mathbin\| H(m))$, which is vulnerable to collisions in $H$. In particular, this was standardized in IEEE P1363 in 2000 (paywall-free; §12.1.2 ‘EMSA2’, pp. 60–61) and by RSA, Inc., in PKCS #1 v2.1 in 2002 (§9.1 ‘EMSA-PSS’, pp. 33–36).

Coincidentally, I'm sure, this was around the same time that the NSA donated ten million dollars to RSA, Inc., to encourage them to deploy the highly superior Dual_EC_DRBG to their BSAFE customers[9].  Not much later—it is unclear from the public record exactly when, but almost certainly not later than 2007—the governments of the United States and Israel exploited an MD5 collision attack[10] to forge signatures on code-signing certificates in an international incident of industrial sabotage against Iran.  Oops.

Formalizing and standardizing collision resilience.
In 1989, Moni Naor and Moti Yung introduced universal one-way hash functions or UOWHFs[11] to formalize what one would expect of randomized hashes for digital signatures: if an adversary submits $m$ up front and is then given $r$, it is hard to find $m' \ne m$ such that $H(r, m') = H(r, m)$—essentially a restricted case of second-preimage resistance.  In 1997, Bellare and Rogaway had the brilliant innovation of giving the concept a more pronounceable and memorable name, target collision resistance or TCR[12], but in spite of the rebranding the notion received little attention for a decade.

Then, in the mid-2000s, as the foundations of collision resistance were cracking at the seams, cryptographers began to seek ways around it, and dusted off old volumes of Naor and Yung and of Bellare and Rogaway.

Phil Rogaway and Tom Shrimpton comprehensively studied relations between various standard notions of security of keyed hash functions—collision resistance, preimage resistance, second-preimage resistance, etc.—and proved implications and gave counterexamples for nonimplications[13]; TCR features as ‘eSec’ or ‘everywhere second-preimage resistant’ in their work.
Shai Halevi and Hugo Krawczyk studied randomization of signatures[14], and invented an even better version of TCR called enhanced target collision resistance or eTCR: if an adversary submits $m$ up front and is then given $r$, it is hard to find $(r', m') \ne (r, m)$ such that $H(r', m') = H(r, m)$.  This is important for signatures schemes where the randomization $r$ does not naturally figure in as it does in PSS, and where the adversary therefore has latitude to control it—as in your suggested generic use of HMAC to strengthen signatures by randomization.  They proposed a generic construction called RMX[15], submitted a now-expired internet-draft to the IETF[16], and persuaded NIST to standardize it as NIST SP 800-106.

Bellare and Rogaway observed that the usual Merkle–Damgård structure doesn't guarantee TCR, which is why Halevi and Krawczyk proposed RMX.  But even though collisions have been found in, e.g., MD5 and SHA-1, there doesn't seem to be much evidence that they fail to exhibit eTCR.  So while the Merkle–Damgård structure doesn't imply eTCR, the design principle of using $H(r \mathbin\| m)$ instead of $H(m)$ in a signature has been adopted in newer schemes like EdDSA[17] following Schnorr's observation in 1989.  It seems unlikely that $\operatorname{HMAC-}\!H_r(m)$ would fail eTCR either even for $H = \operatorname{MD5}$ or $H = \operatorname{SHA1}$.

Conclusion.
Today, there is only one signature scheme that new applications should use unless they have exotic needs: Ed25519, which has this kind of collision resilience built-in by design.  Legacy applications may be stuck with signature schemes like DSA or RSASSA-PSS that have collision vulnerability built-in by design, but maybe if you're only partly stuck on legacy system—you can't use a new signature primitive because you have auditors clamoring at the door about FIPS, but you can use a legacy signature primitive in a new way—you can adapt it to be collision-resilient by randomizing it with RMX, or perhaps with HMAC, or perhaps even with the simple prefix $H(r \mathbin\| m)$.

* The role of the randomization in these theorems is a little peculiar.  Even a single bit of randomization apparently makes a difference in the tightness of the theorems about $e^{\mathit{th}}$ root schemes but not square root schemes[18], which should raise a few eyebrows about the years of effort in the provable security literature that have been dedicated to this single bit of randomization while the US and Israel were at about the same time actually exploiting collisions in MD5 to forge signatures in real standards to wreck Iran's nuclear program.


How to check that AES Matrix is MDS? I want to understand how can I prove that M matrix in AES is MDS. I know that a matrix is MDS if every determinant of every square submatrix is different from 0.

I don't get this. How much submatrix does it have? If I swap rows or columns, does that change something? Do I have to calculate the determinant in a certain mode?

My answer focuses on the AES matrix only. In general, an $A$ matrix with all submatrices having full rank generates an MDS code when concatenated by an identity matrix of the right size to form $[I|A]$, but that's really a coding theory matter.

As to the specific question, this is basic linear algebra but you need to work over the field that AES is defined over. Let the $k\times k$ matrix (like the AES mixing matrix) be
$$A=\left[
\begin{array}{cccc}
a_{1,1}&a_{1,2}&\cdots&a_{1,k}\\
 \vdots &&& \vdots \\
a_{k,1}&a_{k,2}&\cdots&a_{k,k}
\end{array}
\right]
$$

The $1\times1$ submatrices are all nonzero, they're just the entries of $A.$

The $2\times 2$ submatrices: choose any two rows or columns. you can also use the fact that the matrix is circulant to reduce the cases.

So the matrix
$$\left[\begin{array}{cc}
a_{1,1}&a_{1,3}\\
a_{2,1}&a_{2,3}
\end{array}
\right]
$$

is the same matrix as
$$\left[\begin{array}{cc}
a_{2,2}&a_{2,4}\\
a_{3,2}&a_{3,4}
\end{array}
\right]
$$
and thus has the same determinant, etc.

The $4\times$ submatrix is the whole matrix.

Row and column swaps only change the sign of the determinant and can be ignored.

Edit: You need to use the finite field with 256 elements as explained in the link below.

How to use the Extended Euclidean algorithm to invert a finite field element?

This is NOT mod 256 arithmetic.


Can you prove the existance of a PRG $G$ s.t. for each even $k$: $G(k)=G(k+1)$? In one of the exercises in [KL] Book I need to tell whether an encryption scheme is secure under an eavesdropper of only one message.

Given a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$. The encryption scheme encrypt $m \in \{0,1\}^{2n+2}$ by $c= <G(k) \oplus m_1, G(k+1) \oplus m_2>$

where $m_1$ and $m_2$ are the first and second halves of $m$.

Clearly, this is not CPA-secure. But if I could say that there exist PRGs such that for each even $k$: $G(k)=G(k+1)$ I would say that it's even not secure against an eavesdropper of only one message since the adversary can check if $m_1 \oplus m_2= c_1 \oplus c_2$ which will be true whenever $k$ is even which happens with probability of $1/2$.

So: how can I prove that such PRG exists?

@Bush - What you really mean to ask is whether there is a "Cryptographically Secure" PRG (CSPRG) that has the property you describe.  The nature of PRG's and CSPRG's remain to me a bit deep and obscure - and to some extent I think this might be intrinsic, the whole field of crypto may be embedded in this one question on the nature of pseudo-randomness; but I'll give it a go.

Let's start with the PRG.  You can find a definition here.

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution.  More precisely, if we consider a set $E$ in the image set of the PRG, then the measure of the set of points that the PRG maps into $E$ is very close to the measure of $E$.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into $E$ is very close to the fraction of the image that is represented by $E$.  In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG $F: DF \rightarrow I$.

Define a new function $G: DG \rightarrow I$, st. $G(2n)=F(n)$ and $G(2n+1) = F(n)$.

We have:

$ g(k) = F([|k/2|])$, where $[|x|]$ is the greatest integer $<= x$.
$|DG| = 2|DF|$, where $|S|$ is the number of points in the set $S$.

For a set $E$ on the image space, the number of points that map into it via $G$ is just $2x$ the number of points that map into it by $F$.  On the other hand, the domain of $G$ is twice as big as the domain of $F$.  So the measure of the preimages via $F$ and $G$ are the same.  So, if $F$ approximates the uniform distribution on $I$, then so does $G$.  Therefore, if $F$ is a PRG, then so is $G$.

While I belive the above is correct for a PRG, a CSPRG is a more restricted notion that includes the "next bit test", along with the ability to withstand state compromise. See here.

The reason we would want the next bit test in our definition is clear.  The whole point is that the CSPRG should give us a (one time) semantically secure stream cypher.  If the first few bits could give us some information about the next bit that the PRG generates, then this would give us some information to distinguish the PRG output from uniformly random.  So, given messages $m_1, m_2$ and a ciphertext $c$, we could distinguish which of $m_1 \oplus c$ or $m_2 \oplus c$ is more likely to be the output of the PRG.  That would allow us to break semantic security.

I think the restriction on state compromise, may be just an extension of this.  If we generate a key by concatenating shorter keys: $F(n)||F(n+1)||F(n+2)|| \ldots$, we don't want exposure of one part of the key, $F(k)$, to give us information about previous or later parts of the key, eg $F(k-1)$ or $F(k+1)$.

At first glance it appears to me that if $F$ satisfies the next bit test, then so will $G$.  On the other hand, If some of $G$'s state is revealed (eg, $G(k) != G(k+1))$, then we can predict a part of it's past ($G(k-1) = G(k)$) and future ($G(k+1) = G(k+2)$).

I hope that helps.  I'll be watching eagerly if someone has something to add.


Authenticate ephemeral key exchange At the moment I'm designing a crytosystem for a VPN server. One of the requirements is Perfect Forward Secrecy, but I'n not sure how to implement authentication on the ephemeral key exchange.

If both parties possess a signed public key (signed by a CA or common trusted party) and exchange this, they can verify the identity of each other through the CA's public key. To implement perfect forward secrecy, both parties have to generate an ephemeral keypair and send each other the public key. Since these keys are not signed, how can one authenticate the other to guarantee that the keys were not altered/switched? Even if the keys are exchanged over an verified channel (for example using the signed and trusted public keys) that doesn't automatically ensure the ephemeral keys were generated by the same party. Also calculating a MAC over the public ephemeral key does not lead to a secure cryptoscheme since the public key could have been created by an man-in-the-middle in the first place. Is there any way the ephemeral key exchange can be authenticated?

I think you're confusing some things here.

The usual TLS-handshake with ECDHE (which you really should use, unless you have very good reasons) has two public keys. One of them is signed by the CA, the other one is generated on-the-fly.

And before proceeding, please note: (Perfect) Forward secrecy (PFS, not security usually) only means that you don't compromise secrecy of future sessions if a long-term key is leaked, meaning PFS won't protect you against man-in-the-middle attacks if your long-term key is compromised, but very well against passive eavesdroppers.

So the usual key-exchange protocol makes use of the Diffie-Hellman protocol to let both parties agree on a common secret. The values exchanged for this sub-protocol are called public keys and if not authenticated may be subject to a man-in-the-middle attack, but the use of DH prevents passive eavesdropping, thereby yieldin the requested forward secrecy. Those public keys are also completely random (not a random bitstring though).

Now to prevent man-in-the-middle attacks each party signs their DH public keys using the key corresponding to the one in their valid CA signed certificate. If this key is leaked, the contents of future communication are not leaked unless the attacker uses a MitM attack, so PFS is preserved and MitM are prevented if the signature key is not compromised.

TL;DR: There are two public keys, one is long-term and one is short-term, the long-term one is CA authenticated and authenticates the short-term one thereby preventing MitM attacks and the short-term one yields the desired PFS property.


Which is the simplest cryptographic algorithm which is close to commercial-level security? An algorithm is simpler than another if

It is easier to explain to a noob with basic high-school math knowledge.
It is easier to securely self-implement by an intermediate programmer (Yes I know one should never 'roll their own' but this is just a metric of comparing simplicity)
Can be done by hand & paper more easily (not necessarily that it can practically be done on paper, but that it is easier to do on paper if one were to take the pains to do so)
Involves lesser steps.
Any other factors that don't immediately come to mind.

To give an example with popular ciphers, by these criteria RSA is simpler than AES.
The point of this question is maybe find out about some very clever albeit less popular/unheard of cryptographic algorithms that are at or quite close to real commercial-level security while still being incredibly simple.
To use simpler words, the requirements are much above Caesar cipher but much below AES, in terms of complexity.
A question on the most secure hand ciphers inspired this question, except there are no such limitations of not having computational/calculational power here, but similar/stricter restriction on complexity. The idea is to test the limits of simplicity that cryptography can reach while still being done right.
Perhaps symmetric ciphers would be ideal for the criteria of simplicity. However, obviously, any cipher is to-the-mark if it is simple and secure enough.
Edit 1 : The criteria listed above are in order of importance, i.e, the 1st is more important than the second and so on.

I would say MiMC is the simplest block cipher with plausible security. The idea is to cube the state, add a random constant, and repeat. This is typically done in a large prime field, but it is trivial to implement field arithmetic in any language with big integer support. Here's a Python implementation:
def mimc(x, p, k, constants):
    x = (x + k) % p
    for c in constants:
        x = (x**3 + k + c) % p
    return x

Notes:

x is the input.
p is the (prime) order of the field.
k is the block cipher key.
constants is a list of r random field elements, where r is the number of rounds. (The paper uses r - 1 constants, since adding one in the final step does nothing for security, but it doesn't hurt either.)
The authors recommend r = ceil(log(p)/log(3)).
The field must be one in which cubing is a permutation, which holds if gcd(3, p - 1) = 1.


Is there a truly safe signing algorithm? After reading this question, I'm pretty shaken up. A determined attacker with $100 in loose change can crack any RSA key in a couple of hours. After believing that these algorithms would take millions of years to brute force, I'm questioning the security of everything.

What should I move to if RSA isn't safe anymore? Are Elliptic Curve signatures likely to have a similar crack in the near future?

The signing algorithms most often used nowadays are:

RSA based signature algorithms such as RSA-PKCS#1 v1.5 and the more recent RSA-PSS (currently specified in PKCS#1v2.2)
ECDSA, which is the "Elliptic Curve Digital Signature Algorithm", which will probably become the most used one, if not already, since RSA is not as efficient in practice as ECDSA for signing purpose, while validation of signature is faster with RSA. (You can see the Crypto++ benchmarks to get a better idea of their performance)
EdDSA, which is gaining more and more traction nowadays, as it is both easy to implement and secure, plus it is even faster than ECDSA and has plenty of secure open-source code available to use it.
DSA, which has lost the battle and is now less and less encountered on the field, since it is somewhat too complicated for nothing (we use to say it's because the better Schnorr's signatures were patented, that DSA had to circumvent, which made it a too convoluted algorithm)

None of these algorithm have been definitively broken, but it is true that certain instances of them are known to be weak.

First and foremost, note that RSA with a key of 2048 bits or more, is considered secure and should be fine for the next 10-15 years.
So are instances of the other algorithms such as ECDSA with secp256k1, EdDSA with Curve25519, known as Ed25519, etc.
This basically means that the crypto we use nowadays is not easily broken, since it would require both extreme computing power and patience to break it. (As pointed out in the comments, this translates also into large costs, but estimating the costs of breaking these instances would be a question in itself. See for example this question about 256 bits security and the cost of breaking it and keep in mind that we are generally considering anything that is belove 100 bits of security as broken.)

Typically in the question you linked, the RSA algorithm is used with a 512-bit modulus, which is known to be weak, as it is said to correspond to roughly 50-bits of security.

It is also true for the other algorithm, ECDSA, DSA, etc. that if you use them on too small groups, that it is possible to break them, however RSA is probably the one algorithm which has seen the most teams trying to break always larger modulus, there are even RSA challenges which used to have money at stake (but they were discontinued in 2007).

But the discrete logarithm world (on which most other signing algorithms are based) is not left behind and there are (fewer) teams working on trying to break it too.

So, in the end, there is no need to be questioning the security of everything because RSA has been broken when used with 512-bits modulus, however if someone were to come up with a device (maybe a quantum computer) able to break RSA with 2048-bits modulus, or 4096 bits, in a reasonable (typically polynomial) time, then we should all be worried.

But there is currently a competition to try and find the so-called post-quantum primitives that will safeguard us against such things.


Where can I find open source code for Encryption Switching Protocol? The concept of Encryption Switching Protocols was introduced in CRYPTO.

I was wondering if there is any pseudo-implementation of the protocol available or can I get some insights on how to implement it?

I am one of the authors of this paper. We did not implement encryption switching protocols, and as far as I know, they were never implemented. If you plan to implement them, I will be happy to answer questions about specific points. However, I cannot really give general insights about how to implement them: it's a long paper, with a relatively large number of rather complex constructions. The first step would probably be to implement our new variant of ElGamal - good implementations of the Paillier encryption scheme, which we also use, are already available.


What are limitations of Universally Composable (UC) framework? I am beginning to read some UC framework papers, and I guess it is similar to the simulation-based security analysis. I can understand the main advantage of UC is to assist us to analyze the composable protocol. But I am wondering what are the main limitations of UC? I note that it is non-trivial to transform simulation-based security (or game-based security) into UC security. But does there exist compiler to transform form simulation-based security to UC security.

"Simulation-based security" is a very general notion. UC security is much more specific - it refers to a simulation-based security proof in the UC framework. As such, simulation-based security encompass the UC framework, which is a particular case of it, and there is no general transformation from any primitive with a simulation-style security argument to a UC secure primitive.

One of the main limitations of the UC framework is that it's strength - arbitrary composability features - also gives rise to strong impossibility results: many important cryptographic primitives are provably impossible to realize with UC-security in the plain model, hence one must rely on trusted setup assumptions, such as the common reference string model, to build protocols in the UC framework.

Arguably, a second limitation is the relative complexity of the framework, which is not so easy to understand and master in depth - although there are now countless examples of proofs in the UC model to look at, as well as simplifications of the model such as simple UC.


Signature Scheme with proof of data possession Most signature schemes first hash the data and than sign the hash. Correct me if I am wrong: The signature does not prove that the signatory was in possession of the document itself? In cases where the document hash but not the document itself is public, anyone could create a signature for the document without having access to the document data itself. Is there any well known signature scheme that gives a proof of data possession?

I am interested on any hints to existing signature schemes that provide proof of data possession at time of signature creations.

My question is if there are any existing well known/reviewed signature schemes that provide proof of data possession. I am not asking how to "roll your own".

If the document is short enough, then its ISO/IEC 9796-2 signature proves data possession, for a simple reason: in so-called total recovery mode, signature verification recovers the document as a byproduct.

ISO/IEC 9796-2 is an RSA or Rabin signature scheme, also requiring a hash. Depending on options, the "recoverable" message (that is, embedded in the signature) can be up to about $n-h-16$ bits, for $n$-bit public modulus and $h$-bit hash. For example, with 4096-bit RSA and SHA-256, the message can be up to 478-octet, embedded in a 512-octet signature.

ISO/IEC 9796-2 mode 1 is in wide use in Smart Cards. However, beware that it has a near-practical weakness allowing forgery from the signature of chosen messages. ISO/IEC 9796-2 mode 3 is functionally compatible with mode 1, and cures that. Both are deterministic, and maximize the size of the embedded message. ISO/IEC 9796-2 mode 2 is randomized, like RSASSA-PSS, which allows a stronger security argument, at the expense of reducing maximum message size for total recovery.

Independently: for any signature scheme with appendix signing a hash, including RSASSA-PSS and (EC)DSA, changing $\mathcal S_\text{priv}(\operatorname H(M))$ to $$\mathcal S_\text{priv}(\operatorname H(M))\|\mathcal S_\text{priv}(\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M))$$proves possession of $M$ as well as a static signature can do. That has the advantage of working with large messages. This is not standardized, but is a straightforward combination of standardized things.

Addition per comment: this is out of my head. However, the security argument (not proof) is simple:

$\operatorname{HMAC-H}$ is a standard Message Authentication Code construction from a hash.
A standard single-pass interactive proof of data possession is using $\operatorname{MAC}(R,M)$ where $R$ is a random challenge used as key of the MAC.
Signing that gives insurance that the signer is involved.
Replacing $R$ with the signature of the hash makes it non-interactive and invoking the signer before the HMAC could be computed, yet verifiable.

Still, a dishonest signer can offload all hashing to a third party, but that seems inevitable. And an imprudent signer hashing-and-signing any message can be abused into signing a proof of possession of something s/he did not keep (because HMAC's result is a hash).

Note: I chose this, at the price of requiring two signatures, rather than
$$\mathcal S_\text{priv}(\operatorname H(M))\|\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M)$$
because:

The security argument of the former is more straightforward.
The later succumbs if $H$ turns out not to be collision-resistant: an attacker could find $M$ and $M'$ with $H(M)=H(M')$, give $M'$ to signer, obtain $\mathcal S_\text{priv}(\operatorname H(M'))$ as part of proof of possession of $M'$ by honest signer, and turn that into a (different) forged proof of possession of $M$, when the honest signer never knew that $M$.
Involving the signer at beginning and end of preparation of the proof of possession arguably makes repudiation harder.


In RSA, given public key $(n,e)$ and $d^e\bmod n$, can we factor $n$? Given an RSA public key $(n,e)$ and the textbook-RSA encryption $c$ of a valid matching private exponent $d$, computed as $c\gets d^e\bmod n$:  can we factor $n$ ?
Assume $n,e,d$ are per PKCS#1v2.2. If that helps, additionally assume any common (or not overly unlikely) condition helping towards a solution, e.g.:

$n$ product of two large primes $p$ and $q$
$d=e^{-1}\bmod\varphi(n)$ where $\varphi$ is the Euler totient
$d=e^{-1}\bmod\lambda(n)$ where $\lambda$ is the Carmichael function
$e$ small, perhaps just $e=3$
$e$ prime
$\gcd(p-1,q-1)=2$
$q<p<2q$

Motivation is this question, which I could only partially answer.
Problem is, textbook RSA encryption is conjectured secure for random secret plaintext. Random secret implies independent of the key, except for public modulus magnitude. Independent of the key is not met when encrypting $d$. As rightly pointed there, we are in unsafe territory. And for some plaintexts dependent on the private key, that would be totally unsafe. Example: if we reveal the encryption of $p$, that is $c'\gets p^e\bmod n$, we can decipher that as $p\gets \gcd(c',n)$. Other examples: revealing the encryption of $9\,q$ or of $d^d\bmod n$ breaks the security.

We can compute the amount of $E=e^{e-1} mod(n)$ then compute $C=c^E=(d^e)^{e^{e-1}}=d^{e^e} mod(n)$. Now we can compute the secret key $d$ as below:
$C^c=(d^{e^e})^{d^e} mod(n)=d^{e^e.d^e}=d^{(e.d)^e}=d^{1^e}=d \mod(n)$


Post-Quantum Primitives' Object Sizes 1. Alternative Cryptographic Primitives

For quite a while, I've been thinking is it possible to "craft" a cryptographic primitive (like ECC) suitable for the purposes of post-quantum cryptography, and today (2017-05-20) I've came to the following conclusion:

There are two classes of primitives that may be used to construct cryptographic protocol:

Groups: whose elements are equipped with addition with each other, and multiplication only with scalars.
Rings: whose elements are equipped with addition and multiplication with them selves.

The first kind would almost certainly be vulnerable to cryptanalysis by Shor's Algorithm, because they'd most likely be cyclic.

And most primitives of the second kind would be representable with a matrix, since they're probably going to be linear. And this is exactly where we're progressing with lattice-base crypto.

2. CryptoPrimitive Size-Security Efficiency and My Question

Take ECC for example, an ECDSA signature of 192-bit security has 384*2 = 768-bit signature, therefore, it has an size-security ratio of about 4:1.

However, take the currently (2017-05-20) most efficient signature scheme BLISS, instantiated using the procedure described by Rebeca Staffas, we have a 128-bit security instance (512-A) with a signature size of about 6471 bits, that's a size-security ratio of about 50:1.

Yet, BLISS is the composition of several primitives - from sampling bimodal discrete Gaussian, to using Huffman or Arithmetic Coding.

This got me wonder, and this is my question: Is there a single primitive that offers the best post-quantum size-security efficiency, or we don't get to enjoy one such in a post-quantum world anymore?

TL;DR

Don't look for a primitive that provides the best communication efficiency. Instead, look for ones that are rich with desirable features.

Asker's confession

As the OP, I've always had a compulsive frustration that we don't get to enjoy the `perfection' and elegance that elliptic curve primitives used to provide in pre-quantum public-key cryptography. ECC operations are efficient compared to RSA; have actual exponential keysize-security relation; and quite a few other nice properties.

However, ECC isn't always a silver bullet. It requires generating system parameters in complicated ways; and certain parameters must be verifiably secure and sound - which isn't easy to achieve.

Symmetric-key analogy

It should be noted, that constructing secure and efficient primitives in symmetric-key cryptography, is no less noble an art than that in public-key cryptography.

Some blockciphers may require larger and more complex key schedule; some hash functions may require larger internal states, or more pre-computed constants, or both; some AEAD construct may run fast on some systems, but very slow on others.

Why answer my own question

The way the question requests an answer can't be say isn't "too broad" - it really is a bit too broad because I think it's quite deep.

I'd like to answer myself in a way that can inspire thinking instead of pointing people to a mis-predicted future.

What we really should look for

Communication / object size efficiency.
Computation efficiency / performance.
Interoperability.
Ability to be implemented correctly.
Ability to be implemented cost-efficient.

etc.

All these factors must be balanced.


How to determine the next number from java's Random method I understand a little how Java's Random class works.

I have two random numbers output from calls to nextInt() from a java.util.Random  object in Java. I want to determine the next number output after a third call.

The first two numbers are: $-1952542633$ and $-284611532$, how can I determine the next number given only this information?

In Java, if you do not seed the Random object, then it will seed itself. According to that same documentation, it uses a "linear congruential PRNG"...

This means it will easily be cracked if you have two values.

Such a PRNG will have an "internal state", which will change after each generation of a "random" number by applying the following linear process:

$$X_{n+1} = \left( a X_n + c \right)~~\bmod~~m$$
where we call $X_n$ the state at the step $n$, $a$ is the "multiplier", $c$ is the "increment" and $m$ is the "modulus".

Now, Wikipedia tells us that Java is using 25214903917 as multiplier and 11 as an increment and has a modulus equal to $2^{48}$.

Finally you need to know that java.util.Random won't spit all of its internal state into your random numbers: 32 bits only of the internal state are revealed by a call to nextInt().

So, we just one value, it would be hard, but since you have 2 different values, you can easily bruteforce the seed used and thus find the next value by calling nextInt with that seed.

Here is a snippet of code, which produces the correct result (I believe... This is only my fourth time trying out Java), I didn't felt like bruteforcing the bitwise AND operation to reverse it to the actual initial state, I let this as an exercise to a motivated fellow:

import java.util.Random;

public class lol {
    // implemented after https://docs.oracle.com/javase/7/docs/api/java/util/Random.html
    public static int next(long seed) {
        int bits=32;
        long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
        return (int)(seed2 >>> (48 - bits));
    }

    public static void main(String[] args) {
        System.out.println("Starting");
        long i1 = -1952542633L;
        long i2 = -284611532L;
        long seed =0;
        for (int i = 0; i < 65536; i++) {
            seed = i1 *65536 + i;
            if (next(seed) == i2) {
                System.out.println("Seed found: " + seed);
               break;
            }
        }
        Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
        int o1 = random.nextInt();
        int o2 = random.nextInt();
        System.out.println("So we have that nextInt is: "+o1+" and the third one is: "+o2+" with seed: "+seed);

    }
}

Which produces the following output:

Starting
Seed found: -127961833934689
So we have that nextInt is: -284611532 and the third one is: -1527300283 with seed: -127961833934689

And so I think your third integer would be $-1527300283$.


FHMQV-C \sigma calculation - Full Dual Exponential Challenge Response (FDCR) signature schemes- I'm studying the protocol FHMQV - C but I don't understand how two honest parties can reach the same value of $\sigma$. The paper that I'm studying is: https://eprint.iacr.org/2009/408.pdf. If you look, both values of $\sigma$ are made by different values. I can't understand how it's possible that $\sigma_b = \sigma_a$.
I need to understand which combination of $d$, $e$, and ephemeral keys are necessary to allow the node to reach the same $\sigma$ value in order to gain the same shared secret key.

Both $\hat{A}$ and $\hat{B}$ are computing the same quantity, $G^{xy+bex+yda+adeb}$, letting $\mod q$ be implicit:

$\sigma_{\hat{A}} = (YB^e)^{s_A} = (YB^e)^{x+da} = (G^y G^{be})^{x+da} = G^{xy+yda} G^{bex + beda} = G^{xy+bex+yda+adeb}$

$\sigma_{\hat{B}} = (XA^d)^{y+eb} = (G^x G^{ad})^{y+eb} = G^{xy + xeb} G^{ady + adeb} = G^{xy+bex+yda+adeb} = \sigma_{\hat{A}}$

As for $d$ and $e$, all that matters is that both $\hat{A}$ and $\hat{B}$ can each calculate $d = \bar{H}(X,Y)$ and $e = \bar{H}(Y,X)$. This is true since $\hat{A}$ sends $X$ to $\hat{B}$ and $\hat{B}$ sends $Y$ back to $\hat{A}$.

Note that $\sigma_{\hat{A}} = \sigma_{\hat{B}} = G^{s_A s_B}$, where $s_A = x + da \mod q$ and $s_B = y + eb \mod q$.


Did authentication/signature primitives fall under the Wassenaar Arrangement? I understand that under the Wassenaar Arrangement, encryption algorithms like AES were considered to be some sort of weapon. The legally allowed effective key sizes in export software were limited to something a resourceful attacker could break, presumably to prevent criminals from hiding their communications from some government.

Did authentication/signature primitives fall under such legal arrangements? I see no harm in allowing a full-strength MAC or asymmetric signature provided the encryption is weak or absent.

I don't know about MACs (keyed Hashes e.g. HMAC might fall under the definition of symmetric but that's not clear to me) but there are restrictions on asymmetric crypto as well, RSA and Diffie-Hellman are restricted to 512 bits and ECDH is restricted to 112 bits (which effectively is a security level of 56 bits, the same as the limit on symmetric crypto):

  b. An "asymmetric algorithm" where the security of the algorithm is
  based on any of the following:

  Factorisation of integers in excess of 512 bits (e.g., RSA);
  Computation of discrete logarithms in a multiplicative group
  of a finite field of size greater than 512 bits (e.g., DiffieHellman
  over Z/pZ); or
  Discrete logarithms in a group other than mentioned in
  5.A.2.a.1.b.2. in excess of 112 bits (e.g., Diffie-Hellman over
  an elliptic curve);

Source: Wassenar Arrangement Section 5. A. 2. a. 1. b (Page 87)

Edit: As dave_thompson_085 points out, these restrictions do not apply to authentication / digital signature, and only to things like key exchange.


Is there an English translation of Vigeneré's "Traicté des Chiffres"? I Googled Vigeneré's "Traicté des Chiffres": no English translations,  not even a reference to one. Perhaps someone's Google-wu is better than mine; I can't find it.

I'm slogging my way through a PDF of the 1586 edition of "Traicté Des Chiffres, ou Secretes Manieres D'escrire" by Blaise de Vigenere. The language is early Modern French and doesn't translate easily in Google Translate (the words for 'right' and 'left' back then were droict and gaulche, etc).

I'd love to read it in English. Is an English translation available?

There is neither a „modern” French edition, nor an English translation, contemporary or modern. Time to learn some contemporary French. What's the use of attempting cryptoanalysis if you can't manage the historic version of a quite common language, in this case early modern French? Your approach works like the Traicté on its own linguistic grounds, not on yours.


Do ECDH and ECDSA combined solution provide an authenticated protocol exchange solution in MCU environment? I'm working on a project in MCU (micro controller) environment with GPRS connection to exchange data securely with the cloud. The encryption algorithm has been selected to use AES.

I did some search on internet and figured out that ECDH key agreement protocol quite fits the requirements. The good news is that there are some security ICs that have built-in support of ECDH/ECDSA algorithms including secure hardware-based key storage. After digging into this further I learn that ECDH does not do authentication and thus is prone to MITM attacks. This is a very important issue that the system should address.

Can ECDSA be used to do the authentication? Will my system be secure enough with regard to e.g. MITM attacks using a combined ECDH and ECDSA solution?

Saying that ECDH does not do authentication is not entirely accurate. If you use ECDH with static, known public keys and both sides prove knowledge of the shared secret, then you do get authentication. However, with ephemeral keys you need some way to authenticate the exchange of public keys. That could be ECDSA or it could be any other authentication.

So yes, if you use ECDSA to authenticate an ephemeral ECDH key exchange, you avoid man-in-the-middle attacks. You still need some way to trust the ECDSA keys, of course.


How to find collisions in a hash function knowing its coefficent? Say I have a simple hash function where $x$ is a sequence of integers:

$$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$

where $a_1,a_2,a_3,...,a_n$ is the coefficient known to the attacker,
size of $x$ can be anything smaller than $N$.

How to find 2 different inputs that hashes to the same value, i.e $0$?

I feel like this has something to do with linear combination / euclid algorithm but I'm not sure how to proceed.

We can easily find collisions for this system.

Let $x=(x_1,...,x_n) $ be a sequence such that $h(x)=k$. For finding collision we can do this:

Select $x'=(x_1',...,x_{n-1}')$ and then compute:

  $$x_n'=({a_n}^{-1}\cdot(k-\sum_{i=1}^{n-1}a_ix_i')) \bmod N$$

Now we have  $h(x)=h(x')=k$.


Repair AES-128 decrypted file I decrypted a file which was encrypted with OpenSSL and AES-128 with the wrong password. Before I noticed it was the wrong password I removed the original file. Is there a possibility to reproduce the original encrypted file? I know the "wrong" password.

Thanks in advance.

EDIT

The only file I have is the wrong decrypted file. I tried to re-encrypt that file with the used password - the password I decrypted the original file - but that doesn't work. Is there another way to get the original encrypted file?

Based on your description, you will not be able to recover the original encrypted file.

Since you specify that you used a password and do not indicate the use of an IV, my assumption is that you did, in fact, use a passphrase rather than a secret key. When you encrypt a file with a passphrase, OpenSSL assumes that it is a low-entropy string unsuitable for use as a cryptographic key (which is assumed, for AES, to be a random 128-bit or 256-bit string). To turn the passphrase into a suitable key, it performs key stretching: a random salt is generated, and it is hashed together with the key a large number of times in order to increase the amount of effort needed for an attacker to guess the original input. The result is then used as the key.

Unfortunately, it is this random salt which prevents you from reencrypting back to the same file. If you had used a fixed key and IV (initialization vector), it would in general be possible for you to simply reencrypt the data with the two inputs you had mistakenly used, and recover the original encrypted file. However, since a random salt is used in the process to produce a key from a passphrase, and that random salt is stored in the file you decrypted, there will be no way to guess what that value was and therefore ensure you reencrypt with the same key and IV inputs.


Where does the certification come from? In the second chapter of Bruce Schneier's book Applied Cryptography, 2nd Edition, 1996, we find this:

Alice encrypts her message to Bob with KA and sends it to Trent.
Trent decrypts the message with KA.
Trent takes the decrypted message and a statement that he has received this
message from Alice, and encrypts the whole bundle with KB.
Trent sends the encrypted bundle to Bob.
Bob decrypts the bundle with KB. He can now read both the message and
Trent’s certification that Alice sent it.

I don't understand the last step. The "certification" had not been mentioned in any of the previous steps.

Does "certification" mean "a statement that he has received this message from Alice"?

Yes, it means ‘a statement that he has received this message from Alice’.

WARNING: Applied Cryptography is archaic and bad, and these days is useful only for historical research, not for learning how to use, choose, or think about cryptography.  Consider the later Cryptography Engineering by the same author instead.


Original NTRU : How to calculate the size of private key? In the original NTRU paper：NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level as an example:

I understand the calculation of the public key size: $len_{pk} = N\cdot \log(q)=107 \cdot 6=642$ bits, but why is the private key size 340 bits?

Because the entries are ternaries, you can encode them using 2 bits, which gives an encoding of size $2 \cdot 107 \cdot 2 = 428$ bits.

There are smarter way to represent things though. But for general ternary strings you can't do any better than $2 \cdot 107 \cdot \log_2(3) = 339.18 $ (though it may be painful/costly to encode and decode to such a compact size.). Maybe one could also exploit the fact that we know exactly how many $1$'s and $-1$'s there are, which decrease entropy, but encoding/decoding becomes even more costly...


Good entropy source for generating openssl keys I need to generate a CA (4096-bit RSA) and server keys for openvpn and I want them to be "top quality". Here is my plan:

gather entropy from multiple sources (saving individual files): FreeBSD Yarrow, Linux (with haveged daemon while entropy_avail is 4096), ANU QRNG, something else (e.g. wifi capture file encrypted with a random password, other suggestions)
mix all random files into a single one
use the result to seed openssl -rand [myrndfile] when generating the keys

If my plan sounds ok:

what size should the random files be?
what would be the best method to mix the files into a single one?

First off, using '-rand' is only seeding the OpenSSL RNG. It can be 1 byte or 1 TB. It's only used as a seed to get things started internally. Then, OpenSSL will use the systems entropy to actually generate the primes needed by RSA.

Further, entropy is just a measure of unpredictability in a sequence, not an actual pool of stored bits. The larger the estimation on entropy, the more likely certain things will have unpredictable behaviors, such as a sequence of random numbers.

Again though, the Linux kernel file /proc/sys/kernel/random/entropy_avail is just an estimation. When you have an entropy pool of "4096 bits", this just means that the random numbers being generated have the highest quality of unpredictability you can produce. As the entropy pool estimation drops, the confidence in the sequence of random numbers also drops. When the entropy pool is 0, the kernel will block at generating random data until the pool can be filled again. As you generate random data, it reduces the estimation on entropy. This is the behavior of /dev/random.

In other words, think of the entropy pool as a "crypto thermometer". When the meter is at "full up", the generated numbers will be very difficult, if not near impossible to reproduce, and highly unpredictable. When the meter is completely empty, generating random bits could be reproduced by a 3rd party with little knowledge of the system accurately.

So, getting to your OpenSSL key question. OpenSSL will want the kernel to keep entropy as full as possible. However, OpenSSL will seed from /dev/urandom by default. This device will still exhaust entropy, but rather than block when there is no entropy estimate, it will use a PRNG to generate the rest of the data. Keep the entropy pool filled, and the PRNG will never been utilized.

The /dev/random device on FreeBSD is a strict PRNG, and not a TRNG. As you mentioned, it uses the Yarow algorithm to generate random numbers. However, after generating 2^256 numbers, the cycle repeats, generating the exact same numbers in the exact same order as before, as is the case with all PRNGs. By comparison, /dev/urandom in the Linux kernel uses SHA1, which will generate a total of 2^160 numbers before recycling when the entropy pool is exhausted.

Now, to address your question. You mentioned that you are using haveged(8) with Linux to keep the entropy reserve full. On most systems, haveged(8) is generating about 1 MBps of true random data to the kernel, and using the ioctl() system call to increase the entropy counter. As such, generating your 4096-bit RSA OpenSSL key will have the highest quality of cryptographic strength you could ask for, and adding additional random data from other systems won't increase its strength.

The whole point of the certificate generation is to create random numbers from either your file, or from a random number generator, as noise input into an algorithm to generate very large primes. The trick is getting to those prime numbers. With an entropy pool of 4096 bits, at full up, all the time, as haveged(8) will be providing, the ability of someone to regenerate the same primes, even if they have full knowledge of your system, is highly improbable.

So, in my opinion, run haveged(8) keeping the kernel topped at 4096-bits of entropy, and just generate your certificate there using "-rand /dev/random", rather than generating a file from every system.


Can a monoalphabetic substitution cipher attain perfect secrecy? Can a monoalphabetic substitution cipher attain perfect secrecy?

Definition of perfect secrecy:

$${\rm Pr}[\,{\rm Enc}_k(m_1) = c\,] = {\rm Pr}[\,{\rm Enc}_k(m_2) = c\,]$$

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$.

Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key?  Why (not)?  What does this imply about perfect secrecy?

Ps. The hint I gave above assumes that the cipher is not homophonic, i.e. that the encryption of each character is deterministic and independent of its position or the presence of other characters in the message.  For a (possibly) homophonic monoalphabetic cipher, it may be simpler to start the argument from the other end: if you intercept the ciphertext $c = \text{"xx"}$, what can you say about the plaintext?


How to combine AES-CMACs I have a primitive that is able to generate a AES-128-CMAC from a message.

$\operatorname{CMAC}(\text{MessageAddress}, \text{MessageLength}) \rightarrow \text{result}$

I cannot change this primitive. I don't have direct access to the key, nor to the internals of that function.

Let's say that I want to authenticate a message that is split over non-contiguous chunks. How is it possible to chain calls to this primitive while not opening a breach to an attack?

For example, if $M = M_1 || M_2 || \ldots || M_n$, compute

$\operatorname{CMAC}(\operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || \ldots || \operatorname{CMAC}(M_n))$

Of course, the result is completely different than $\operatorname{CMAC}(M)$ but that doesn't matter because both sides would implement the same algorithm for signing and verification.

However, is it still secure? Would it be better to use a XOR operation instead?

$\operatorname{CMAC}(\operatorname{CMAC}(M_1) \oplus \operatorname{CMAC}(M_2) \oplus \ldots \oplus \operatorname{CMAC}(M_n))$

Any other idea?

For example, if $M = M_1 || M_2 || \ldots || M_n$, compute
$\operatorname{CMAC}(\operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || \ldots || \operatorname{CMAC}(M_n))$

If we assume that the attacker cannot find two distinct messages $M_1, M_2$ with $\operatorname{CMAC}(M_1) =\operatorname{CMAC}(M_2)$ (which he is unlikely to if the number of messages being MAC'ed is considerably below $2^{64}$), then you're good.
That is, if the attacker is able to produce a message/MAC pair that validates with this construct, then either:

He is able to construct a message/MAC pair for CMAC which we hasn't previously observed; that is $CMAC( M' )$, where $M' = \operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || ... || \operatorname{CMAC}(M_n)$ which he has not previously observed, or

He finds a collision $\operatorname{CMAC}(M_i) = \operatorname{CMAC}(M'_i)$ (and reuses a top-level CMAC he has observed)

(Note that this initial analysis does not consider the possibility of an interaction between the bottom-level and top-level CMAC's, where the attack has actually observed the message $M'$ in one of the bottom level MACs; a full proof would need to address that)

Would it be better to use a XOR operation instead?
$\operatorname{CMAC}(\operatorname{CMAC}(M_1) \oplus \operatorname{CMAC}(M_2) \oplus \ldots \oplus \operatorname{CMAC}(M_n))$

That's far worse; consider the MAC of the message $M_2 || M_1 || M_3 || M_4 || ... || M_n$


Finding missing bits mathematicaly in a DLP situation Here is a DLP exercice

$g = 51234,\; h = 90403 ,\; N = 311 \cdot 359 = 111649$.

Define $r$ as the smallest positive integer with $g^r \equiv h \pmod N$.

Define $s$ as the smallest positive integer with $h^s \equiv g \pmod N$.

(Here, $r=33497$ and $s=27663$ ).

Questions:

If one looses some bits of $(r,s)$ can they be recovered? (do not use brute-force attack)

In other words: with the following information:

$\quad g=51234,\; h=90403,\; N=311 \cdot 359 = 111649\\
\quad r=3@497,\; s=276@3$

how can one recover the missing digits '$@$' ?

Editor's note: It emerged this is part of a complete problem.
The original statement is ambiguous about the minimality of $s$, has a typo in the value of $N$, and uses $\mathrm{gr}$ and  $\mathrm{hr}$ where there is now $r$ and $s$, per the notation in this answer.

I suppose (for simplicity but it can be generalized I think) that the missings bits of $r$ and $s$ are the least significant bits. So, we have:
$$
\begin{array}{lll}
r = r_12^u + r_0&\text{with}&g^r \equiv h \pmod N \\
s = s_12^v + s_0&\text{with}&h^s \equiv g \pmod N,
\end{array}
$$
with $r_0 < 2^u$ and $s_0 < 2^v$ unknown.

Using the relation between $g$ and $h$, we can get the following relation:
$$
h^{rs-1} = 1 \mod N.
$$
The order of the multiplicative group $\mathbb Z/N\mathbb Z$ is $\varphi(N)$. Given the factorization of $N$, as in your example, this value is known and there exists $k\in\mathbb Z$ such that:
$$
rs - 1 = k \varphi(N).
$$
Let's call $x$ and $y$ the unknown part of $r$ and $s$ and we look at the precedent equation mod $\varphi(N)$ to get rid of $k$ and we have an equation in two variables:
$$
(r_12^u +x)(s_12^v + y) - 1\equiv 0 \mod \varphi(N).
$$
If the size of the unknwown part of $r$ and $s$ are not too big, then the Coppersmith technique in two variables (using lattice) may be used to recover those part. Lot of information here.


Key Size for Symmetric Homomorphic Encryption Over the Integers In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2.

Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$
Encrypt A Bit m: $c = pq + 2r + m$
Decrypt A Bit c: $m = (c \% p) \% 2$
Homomorphic XOR: $result = c + c'$
Homomorphic AND: $result = c * c'$

Note that when encrypting a bit, $q$ is a random number to help hide the key, and $r$ is a small noise value to turn breaking the encryption into a "learning with error" problem.  $N$ is effectively the number of bits in the key.

In the second to last paragraph on page 1, the paper suggests these values to make the above secure:
$r ≈ 2√N$
$q ≈ 2N^3$

However, the font used is rather unfortunate and I can't tell if the paper means the way i wrote it above, or the way I wrote it below:
$r ≈ 2^{√N}$
$q ≈ 2^{N^3}$

Is anyone able to understand which way it should be?  Also, I'm kind of curious where these specific values for security came from, if anyone is able to shed light on that.

Edit:

Later in the paper, on page 5, it talks about how to calculate some parameters for the public key implementation:

  γ is the bit-length of the integers in the public key
  η is the bit-length of the secret key (which is the hidden approximate-gcd of all the public-key integers),
  ρ is the bit-length of the noise (i.e., the distance between the public key elements and the nearest multiples of the secret key), and
  τ is the number of integers in the public key

  These parameters must be set under the following constraints:
  • ρ = ω(log λ), to protect against brute-force attacks on the noise;
  • η ≥ ρ · Θ(λ log^2 λ), in order to support homomorphism for deep enough circuits to evaluate the “squashed decryption circuit” (cf. Sections 3.2 and 6.2);
  • γ = ω(η^2 log λ), to thwart various lattice-based attacks on the underlying approximate-gcd problem (cf. Section 5);
  • τ ≥ γ + ω(log λ), in order to use the leftover hash lemma in the reduction to approximate gcd (cf. Lemma 4.3).
  We also use a secondary noise parameter ρ′ = ρ + ω(log λ). A convenient parameter set to keep in mind is ρ = λ, ρ′ = 2λ, η = O˜(λ^2), γ = O˜(λ^5) and τ = γ + λ. (This setting results in a scheme with complexity O˜(λ^10).)

It never explains what ω is.  Is that some commonly known notation?  How did the "convenient parameter set" come from those formulas?

Also, what exactly does it mean when they say that using that parameter set results in a scheme with complexity O˜(λ^10)?  Does that mean that the attack against the encryption has that for complexity?  I'm wondering about the case where maybe increased speed is desired, even at the cost of decreased security, to understand what to change to get those results.

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$,  not $N$.

With regard to the parameters, it is common practice to describe them using the asymptotic notation. $\omega(\cdot), \Theta(\cdot)$ and $\tilde O(\cdot)$ are instances of this notation. $\omega(g(n))$ denotes a function that dominates $g(n)$ asymptotically; that is, $f(n) = \omega(g(n))$ means that $f(n)$ is asymptotically greater than $g(n)$. For example, a linear function (e.g., $f(n) = n$) dominates a logarithmic function (e.g., $g(n) = \log n$), since, asymptotically, it grows much faster; thus, $n = \omega (\log n)$. $\Theta(g(n))$ denotes a function that, also asymptotically, can be "sandwiched" between $k_0 \cdot g(n)$ and $k_1 \cdot g(n)$, for some real values $k_0, k_1 > 0$. Finally, $\tilde O(n)$ is like the traditional Big-O notation but ignoring any logarithmic factors.

Therefore, these parameters are actually functions of the parameter $\lambda$, since they vary when $\lambda$ varies, although they are not expressed as functions. The expressions given are only a way of specifying how to choose them according to $\lambda$.

Also note that these expressions are somewhat "abusing the notation", since these asymptotic "functions" are actually sets of functions. Therefore, when you see something like $\rho = \omega(\log \lambda)$, it actually means $\rho(\lambda) \in \omega(\log \lambda)$. Anyway, this is a fairly common convention that simplifies the reading.

Knowing this, you can deduce your own example values for the parameters. For example:

$$\rho = \omega(\log \lambda) \to \rho =  \lambda$$
$$\eta \geq \rho \cdot \Theta(\lambda\log^2 \lambda) \to \eta = \lambda \cdot (\lambda\log^2 \lambda) = \lambda^2\log^2 \lambda $$
$$\gamma = \omega(\eta^2\log \lambda) \to \gamma = \eta^2\lambda = (\lambda^2\log^2 \lambda)^2\lambda = \lambda^5\log^4 \lambda$$
$$\tau \geq \gamma + \omega(\log \lambda) \to \tau = \gamma + \lambda = \lambda^5\log^4 \lambda +\lambda $$
$$\rho' = \rho + \omega(\log \lambda) \to \rho' = \rho + \lambda = 2\lambda$$

As you can see, this gives a result that is consistent with the part that says:

  A convenient parameter set to keep in mind is $ρ = λ$, $ρ′ = 2λ$, $η = \tilde O(λ^2)$, $γ = \tilde O(λ^5)$ and $τ = γ + λ$. (This setting results in a scheme
  with complexity $\tilde O(λ^{10})$.)

When it says that the scheme has complexity $O(\lambda^{10})$, I guess it means the time complexity.


What does it mean to be simultaneously hardcore? In this paper the term "simultaneously hardcore" is defined as:

  "We say that a block of bits of $x$ are simultaneously hard-core for a one-way function $f(x)$, if given $f(x)$ they cannot be distinguished from a random string of the same length."

Could somebody give me an example of something that is simultaneously hardcore and something that is not?

Also, what does it mean to be hardcore vs. simultaneously hardcore ?  Is it possible to be hardcore but not at the same time?

This terminology is quite confusing and I would really appreciate it if somebody could break it down to concrete, simple examples.

Hard-core bits are related to one-way functions.

For some intuition on what hard-core bits are, consider a one-way function $f$. SInce it's a one-way function, it's hard to invert: that is, if I select a random $x$ in the function's domain and give you $f(x)$, you cannot find a $x'$ such that $f(x) = f(x')$ with non-negligible probability in probabilistic polynomial time (this is the definition of a one-way function).

So, intuitively, there is "something" about $x$ that is hidden from you in $f(x)$. If you knew everything about $x$ from $f(x)$, you would know what $x$ was. So, there is something that $f$ hides about its input. That something is a "hard-core predicate".

A hard-core predicate is itself a function. Let's say we have a hard-core predicate for $f$ called $\mathsf{hc}$. Since it's a predicate, $\mathsf{hc}$ returns exactly one bit.  So, given $f(x)$, you cannot determine the value of $\mathsf{hc}(x)$ with non-negligible probability (over $1/2$, which you can always get by guessing) in probabilistic polynomial time. In essence, $\mathsf{hc}(x)$ represents something about $x$ that you do not know given $f(x)$ — that is, $\mathsf{hc}$ is a bit related to the input that $f$ hides from you. Another way of looking at it is that $\mathsf{hc}(x)$ is indistinguishable from random (in PPT and all that business). To see this, consider if you were given $f(x)$ and $\mathsf{hc}(x)$. Since you cannot compute $\mathsf{hc}(x)$ from $f(x)$, by definition, you should not be able to distinguish it from a random bit.

Note that a hard-core predicate is a single bit. Instead of a single bit, the paper wishes to talk about multiple different bits each being hard-core simultaneously. So, simultaneously-hardcore bits are a natural extension of hard-core predicates into strings that are multiple bits in length. To be explicit, let $h$ be a hard-core function for $f$. Then, given $f(x)$ for a random $x$ in $f$'s domain, an adversary cannot compute $h(x)$ in PPT. The paper you've linked frames $h$ as being indistinguishable from random, which is equivalent.


What is the difference between RCCA and CCA2? Well, I know it's easy to tell CCA1 from CCA2, but I failed to find the difference between RCCA and CCA2.

What is the difference?

Informally, CCA2 does not permit any kind of modification of ciphertexts, while RCCA permits some alteration as long as it does not alter the original message. For example, think of a publicly randomizable encryption scheme, that is, a scheme that permits to alter the original randomness used during encryption.  CCA2 would consider these ciphertexts as invalid, while RCCA would accept them.

In the indistinguishability game (IND), this difference is translated in the restrictions to the use of the decryption oracle in phase 2. In CCA-2, the adversary is not allowed to ask for the decryption of the challenge ciphertext $c^*$, while in RCCA, if the adversary asks for the decryption of any ciphertext that decrypts to the challenge messages $m_0$ and $m_1$, he will only receive a special symbol $\mathsf{test}$.


Understanding the length b used in MD5 I am trying to understand MD5 hash algorithm from the link http://www.ietf.org/rfc/rfc1321.txt

At first I was not able to understand padding of MD5. Then I asked a question in this link: To understand a fact related to padding in MD5

From this answer I can understand padding. Now I have faced another problem: to understand the second step of MD5.

I am trying to understand the second step from the same link: http://www.ietf.org/rfc/rfc1321.txt

But I have failed to understand a sentence and a phrase as before.
Here is the phrase:

  A 64-bit representation of b

what does 64-bit representation stand for?

Here is the next sentence:

  In the unlikely event that b is greater than 2^64, then only
     the low-order 64 bits of b are used.

what does lower-order bits mean?

Can anyone explain the above phrase and sentence with better clarity?

what does 64-bit representation stand for?

It's the length (in bits) of the hashed message, expressed as a 64 bit binary value (in little endian order).  If you hash a 1 character message, $b=8$ (as 1 byte == 8 bits); this would be represented as the 8 bytes 08 00 00 00 00 00 00 00 (the 08 is first, because in little-endian order, you place the least-significant part first)

  what does lower-order bits mean?

The length of the the $b$ field within the padding is 8 bytes long; if you were to hash an extremely long message (one $2^{61}$ bytes or longer), it might be the case that $b$ wouldn't fit in an 8 byte field.  In that case, what you place into the field is the lowest 8 bytes into the field; another way to express this is that you place the value $b \bmod 2^{64}$ into the padding field.

On the other hand, $2^{61}$ bytes is an enormous amount of data; it is approximately the amount of data that flows over the internet globally in a day.  It is quite unlikely that you (or anyone else) will ever compute an MD5 hash on that much data; you can in practice ignore this sentence.


How did they factor RSA-704? I don't understand the 'Wiedemann algorithm' works.
Can someone explain the factoring of RSA-704 in an easy way?

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas.

The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure:

Preparation phase: find a adequate representation of the desired structure and choose a smoothness basis, i.e. a set of small elements.
Phase I: Find many multiplicative relations between elements of the smoothness basis. Simple example: $2\cdot 3 = -1 \pmod{7}$. You need more equations than the number of smoothness basis elements.
Formally taking logarithm of all multiplicative relations, we get linear relations between logarithms of small elements.
Phase II: Perform linear algebra. Here the details vary between Dlogs and factoring. For Dlogs, finding a non-zero kernel element modulo the group order directly gives the logarithms of the small elements. For factoring, you search instead for a kernel element in the transposed system modulo 2. This correspong to finding a product of the initial relation where all elements will appear with an even exponent.
Phase III: Conclude the computation. For Dlogs, this is the individual logarithm phase. For factoring, we extract from the above linear relation two elements whose squares are equal, say $A^2\equiv B^2\pmod{N}$, with probability $1/2$, the gcd of $A-B$ and $N$ yields a non-trivial factor of $N$. If it does not work, try another relation.

The Wiedemann algorithm is an iterative method for the linear algebra phase. Usually, when working modulo $2$, block Wiedemann is used. This method allows to compute many relations (as many as the block size), after computing a sequence of matrix by vector block product. The reason for using this approach (or Lanczos method) for solving the system is that it is much faster and much more efficient in terms of memory than Gaussian elimination for the large linear systems that are involved.

With NFS, some of the details become mathematically quite involved. For this reason, I will just add a few more points.

Preparation phase: $N$ is represented by finding two polynomials $f$ and $g$ of relatively small degrees and small coefficients with a common root $R$ modulo $N$. Most of the time, one of the two polynomials is linear. On the linear side, the smoothness basis contains small prime numbers. On the other side (algebraic side), the smoothness basis contains degree one ideals of small norm.
Multiplicative relations generation. Take an element $a+bX$ and send it to $a+bR$ on the linear side and to the ideal generated by $a+b\alpha$ ($\alpha$ a complex root of the polynomial defining the algebraic side). If both side completely factor into elements of the smoothness basis, you get a relation.
Linear algebra and square root. This becomes more difficult than in the general case, because to get a relation $A^2=B^2$ it is not only necessary to have even exponent on the ideal side, you also need to make sure that the resulting value is a principal ideal. This is done by adding multiplicative characters in the relation matrix before the linear algebra step.

Hope that helps.


Fully Homomorphic Encryption over the Integers - perform an operation on an encrypted data In Fully Homomorphic Encryption scheme represented here Fully Homomorphic Encryption over the Integers
In the Evaluate process (see section “3.1 The Construction” of the paper):
$$Evaluate(pk, C, c1, \dots , ct):$$
Now…

If I want to do some operations on an encrypted data, should I convert that operation to a binary circuit, then do the operation, and re-encrypt the final result?

If I have this simple binary circuit below, how could I evaluate the process?

What is the data that will be passed to the Input A and input B?

And how can I determine the number of addition and multiplication operations that will be used?

I did not understand how to do it from the Paper.

It's actually straight-forward; we'll assume that all the inputs are either encrypted versions of 0, or encrypted version of 1; then:

We can replace an AND gate with just an FHE multiplication of the two inputs:

$$AND(x,y) = x*y$$

Where $*$ is our Homeomorpic multiplcation operation.  This obviously evaluates to an encrypted 1 if both of the inputs are encryped 1's; and an encrypted 0 if either of the inputs are encryped 0's
To replace an exclusive or gate, we encrypt the constants 1 and -1, and then compute:

$$XOR(x,y) = x*(1 + (-1 * y)) + y*(1 + (-1 * x))$$

Where + is our homeomorphic addition operation, and 1 and -1 stand for our encrypted constants.
To replace an or gate, we take our encrypted 1 and -1 constants, and compute:

$$OR(x,y) = 1 + -1 * (-1 + x) * (-1 + y)$$
To replace a NOT gate (that doesn't appear in your circuit, but does come up in others), we compute:

$$NOT(x) = 1 + -1 * x$$

It is easy to see that, in all cases, if the inputs are restricted to encrypted 0 and encrypted 1, the result is either an encrypted 0 or an encrypted 1 (and which will be the logical result of the operation).  Obviously, things can be simplified somewhat if our FHE operation includes a subtraction operation.

As for the number of operations used, we just translate each gate and count them up.  On the other hand, this construction is really a proof that just addition and multiplication suffice to be complete operations (that is, given just those two operations, we can compute anything); when you look at operation count, it turns out to be quite inefficient.


How can scrypt be improved to counter GPU mining I know scrypt was designed to lessen the GPU/ASIC advantage.

We now have litecoin as a real-world example of this. However, it hasn't worked out perfectly.  Most coins are mined by GPUs, although the advantage is probably smaller than it would have been with SHA-256.

I wonder how the future for scrypt and newer generations of this approach looks like:

Are there alternatives being developed?
Are there specific issues exposed by Litecoin that could be addressed?

I believe scrypt is designed to be scaled to be both memory hard and cpu hard by explicit design.

As a result, most implementations of scrypt will require you to input a desired cpu difficulty as well as a desired memory difficulty. On a gpu, where each core has very little memory, it would be trivial to see that, unless gpus gain a great deal of memory in the near future, you can crank the memory difficulty up to the point where it will be barely tolerable for a cpu let alone a memory-light gpu core.

Simply, scrypt doesn't need to be improved, it just needs to be utilized in a manner that will achieve the desired results. Even if you look now, you will see that scrypt is doing a superb job at preventing a serious rise of hashing rate with the advent of the ability to use gpus as the rate is currently measured in kh/s per second rather than mh/s on the same devices.