How Far Ahead of Academia Are Government Agencies? This is a soft question regarding comparisons between government security services (eg, NSA or GCHQ) and open-source research (e.g., academia). Hopefully it's on-topic for this site!

In essence, my question is the following.

  How far ahead (if at all) of of open source (specifically academic) research are governmental agencies?

There are some various thoughts I've had on this matter.

NSA is the largest employer of mathematicians worldwide, and their primary focus is on security. So not only do they have an incredibly large number of people, but they're also very focused. On the other hand, cryptography departments at universities (that I'm aware of) don't seem to be particularly large.
We now get onto the actual people who do the work. For example, to start at the base level at GCHQ you need a 2:1 in a three-year maths degree. (I'm from the UK, and don't really know any comparison with American GPA.) In comparison with university faculties, these will all have doctorates as a minimum, and university researcher places (at least in UK universities I'm aware of) are very competitive.
At a first glance, this suggests that the standard of researchers in general is much higher in academia. Of course, one has to be careful: not everyone wants to do a PhD for starters; moreover, a lot of people may not want the job-insecurity of post-docs, and prefer to move into a more secure (likely higher-paying) job outside of academia. Furthermore, continuing from the first point, these people then spend all their time working on this stuff, with large amounts of resources (including many other people around).
As an example, when DES was replaced with AES, instead of developing AES themselves, the NIST set a challenge to other researchers. The NIST then chose the best of these (supposedly, anyway; many people have apparently legitimate claims that the most secure wasn't chosen, but instead the one the the NIST 'liked' the best).
I have heard that RSA was discovered some 8 (or maybe 3?) years before it was public, but that this was at a time when there was comparatively little open source research into such topics.
Finally, a lot of what secret agencies do is, well, secret!

Basically, there seem to be arguments for many points, and I was wondering if anyone has more insight than I do!

Very related (but not the same) is this question: How can we reason about the cryptographic capabilities of code-breaking agencies like the NSA or GCHQ?; that question is more about some specific things (eg symmetric ciphers).

To be clear, I know this question isn't definitively answerable without high-up knowledge of governmental affairs, but I feel some approximations should be possible.

Of course, none of this addresses private companies (eg, Google). These employ a lot of people, likely(?) with higher entry requirements than NSA/GCHQ (see above on why that doesn't give a clear cut implication) and also have lots of money; moreover, there's likely(?) less bureaucracy.

If any of my above claims are wrong, please do point them out! I'm not very knowledgeable in the world of cryptography. I'm a maths PhD (discrete probability), but have interest in this stuff.

Disclaimer: This post is possibly opinion based.

How far ahead (if at all) are governmental agencies of open source (specifically academic) research?

This question is impossible to answer. By definition, this require a knowledge of the state of research in such agencies which is definitively something they want to be kept as secret...
thx to @fkraiem:

However one can get a feeling of it by considering the followings:

Academic research is usually founded by companies or government agencies.
e.g. for the Gimli paper:

This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO) and project number 645421 (ECRYPT-CSA); the Austrian Science Fund (FWF) under grant P26494-N15; the ARC project NANOSEC; the Belgian Fund for Scientific Research (FNRS-F.R.S.); the Technology Foundation STW (project 13499 TYPHOON), from the Dutch government; the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005; and the U.S. National Science Foundation under grant 1314919. “Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

In the case of important projects, academic research is paired with companies with huge computing power (Google, Microsoft Research...) e.g. SHAttered:

This result is the product of a long term collaboration between the Cryptology Group at Centrum Wiskunde & Informatica (CWI) - the national research institute for mathematics and computer science in the Netherlands - and the Google Research Security, Privacy and Anti-abuse Group. Two years ago Marc Stevens and Elie Bursztein, who leads the Google's anti-abuse research team, began collaborating on making Marc's cryptanalytic attacks against SHA-1 practical by leveraging Google expertise and infrastructure.

Sure such companies may? still not have the computing power of NSA, but the minds in there are definitively on par with such agencies.

I would also advise this to have a look at this: The Moral Character of Cryptographic Work by Phillip Rogaway [paper] [Usenix Talk], specially at the founding part (p. 36). We see a increase in the number of project founded by military agencies.
WARNING: this is a personal assumption, you may chose to disagree with it.
Knowing their missions (cf quote bellow) we can somewhat deduce that their level of research is most likely on par with academic work (why would you heavily fund something that would be bellow your current level of comprehension?)
e.g. for Defense Advanced Research Projects Agency (DARPA) :

The genesis of that mission and of DARPA itself dates to the launch of Sputnik in 1957, and a commitment by the United States that, from that time forward, it would be the initiator and not the victim of strategic technological surprises.
source.

Their goal are the following:

fund academic research
but most importantly know what you are currently researching on! $\Leftarrow$ This is information they want!

TL;DR:  I believe they are on par with current academic research.


A possible error in the book So I have been reading this book called "Implementing SSL/TLS using Cryptography and PKI" While going through it, this snippet of code got me baffled

    static void compute_key_schedule (
    const unsigned char *key, int key_length, unsigned char w[ ][ 4 ] ) {
    int i; int key_words = key_length >> 2;
    unsigned char rcon = 0x01; // First, copy the key directly into the key schedule
    memcpy( w, key, key_length );
    for ( i = key_words; i < 4 * ( key_words + 7 ); i++ ) {
        memcpy( w[ i ], w[ i - 1 ], 4 );
        if ( !( i % key_words ) ) {
            rot_word( w[ i ] );
            sub_word( w[ i ] );
            if ( !( i % 36 ) ) {
                rcon = 0x1b;
            }
            w[ i ][ 0 ] ^= rcon;
            rcon <<= 1;
        }
        else if ( ( key_words > 6 ) && ( ( i % key_words ) == 4 ) ) {
            sub_word( w[ i ] );
        }
        w[ i ][ 0 ] ^= w[ i - key_words ][ 0 ];
        w[ i ][ 1 ] ^= w[ i - key_words ][ 1 ];
        w[ i ][ 2 ] ^= w[ i - key_words ][ 2 ];
        w[ i ][ 3 ] ^= w[ i - key_words ][ 3 ];
    }
}

The text says that in case of 128-bit key, round constant is shifted every 4 iterations (of forming single word of key for key schedule), making up total of 10 shifts, but at 8th shift, the round constant would be 0, and AES mandates that whenever it overflows, you should XOR it with 0x1b. So I get it that's why we did that if (i%36) rcon = 0x1b It makes sense, but if key_length is 192-bit, it would be problematic, since at iteration 36, it will pass the check if ( ! ( i % key_words)) and would proceed to change rcon to 0x1b, though there won't be any overflow at all! (I believe that key would be 0x10 at that time this shift will occur in case of 192-bit).

So it just doesn't makes sense to me and I wanted to know if there is something I am missing out on. At first I thought maybe it's necessary to rotate it every 4 iteration irrespective of key size but reading text and reading rest of code, I don't think that was an intention ever. Thanks a lot!

The question's code works for AES-128 and AES-256, but indeed does not for AES-192, for the reason pointed in the question.

Yes changing if ( !( i % 36 ) ) into if((!(i%36)) && (key_words == 4)) as suggested in comment by the OP is enough to make it (and the rest of the code) pass the example of appendix A.2 and C.2 of FIPS 197 (as well as A.1, A.3, C.1, C.3).

Reminds me of the book Security for Computer Networks by D.W. Davies (not the same Davies) and W.L. Price (May 1987 edition), which has a typo in the last constant for S4 of DES, causing failures for some test vectors. That drove me nuts for a while in the late 1980s. From that point on I implemented crypto on the basis of the standards.


Question about hashing passwords with PBKDF2 I am new here and new to encrypting and securing passwords, so please forgive me if this question is not posted to the right location or if my question is bad.

I have been working on a web app in Java that requires a username and a password. Through my research, I discovered that I need to salt and hash my password in order to make sure it is secure when I place it in a database.
 So far, I am leaning towards using PBKDF2 with SHA512, but bcrypt is still on the table.
 I came across this post about using PBKDF2 for encrypting passwords: http://howtodoinjava.com/security/how-to-generate-secure-password-hash-md5-sha-pbkdf2-bcrypt-examples/
 The example seemed to show what I needed to do as far as hashing and salting my passwords, but I was concerned with using a colon to create a split between the iterations, salt, and password.
 Wouldn't that just give clues to someone who would try to hack my database as to how I was hashing my passwords?
 I know the author of the article was demonstrating how to verify the password using the split method, but I'm thinking this isn't the best method of encryption and verification
 What I am hoping for is if someone could take a look at this and let me know if there is a better way (or example) to use PBKDF2 for password hashing and verification. If there are links or other questions that could be suggested, that would be awesome.
 Also, I am open to hearing others thoughts on which algorithm I should be using because there is a lot of information out there and it seems like there is nothing conclusive as to which one is the best.

I really appreciate any help that is provided, and I hope this is the right place to post this question.

Thanks!!

The example seemed to show what I needed to do as far as hashing and
  salting my passwords, but I was concerned with using a colon to create
  a split between the iterations, salt, and password.

  Wouldn't that just give clues to someone who would try to hack my
  database as to how I was hashing my passwords?

The security only has to come from the algorithm and the key used, keeping the algorithm or its parameters secret should not be necceasary. That is the principle of Kerckhoff, on of the pillars of modern cryptography.
This means in consequence, that since you are using an algorithm considered secure, it is no problem to show the public parameters to an attacker.

  Also, I am open to hearing others thoughts on which algorithm I should
  be using because there is a lot of information out there and it seems
  like there is nothing conclusive as to which one is the best.

PBKDF2 is fine, but it is not as resilient to attacks with specialised hardware as other schemes. SCrypt is the most well established such algorithm. Another scheme worth mentioning is Argon2. It is the recent winner of the academic Password hashing competition, but due tp its newness it is not as widely used (and implemented) as SCrypt.


Explain same encryption time for two files of different sizes I am encrypting files in a two layered fashion as follows:

Inner layer is 128 bit AES-CTR encryption
Outer/Second layer is a simple one time padding with a particular key.

While testing the running times I noticed that it takes same time to encrypt a 100kB file as it takes to encrypt a 10kB file. Logically it seems wrong to me, is it something that I am missing ?

Modern computers are quite fast, and modern cryptographic algorithms are quite efficient.

Most computers benchmark hardware accelerated AES in CTR mode well above 1GB/s, which would be a fraction of a millisecond for a 100KiB file. Since the standard system timer generally runs at 1ms intervals, the entire encryption operation ([file data] XOR [AES] XOR [Pad]) will take less than a single timer 'tick' to complete, and they will report the same completion time.

I would expect files up to 3 MiB will take less than 1ms to complete on computers made in the last 5 years, if the timer is started after the file data is read from disk, just prior to encryption.

Try using a much larger file, at least 1 GiB, in order to gauge the performance of the system. Also, Windows offers a high resolution timer through the kernel, if the hardware supports it, offering sub-microsecond accuracy. If you try to repeatedly measure very small time windows, they will vary greatly if there are other processes using the same CPU core.


Why is AES not a Feistel cipher? I am studying for an exam right now.  And I wanted to make sure I got this point correct.

AES is not a Feistel cipher because the operations in AES are not invertible.

Is the above statement correct? If not, why isn't it a Feistel cipher?

Well, AES is not a Feistel cipher because it's a substitution-permutation network instead. If I were taking a test that asked me why AES was not a Feistel cipher, this would be my argument: namely, that the structure of substitution-permutation networks is fundamentally different from that of Feistel networks. (Here one could elaborate on invertibility and other differences.)

That said, your statement is not correct. In a Feistel cipher, the round function is not necessarily invertible (DES's round function is not), but in AES, like any substitution-permutation network, the rounds are invertible. This is a property of the construction itself.


Is a composition of clocked entities a clocked entity in the UC model? In the book titled "Secure Multiparty Computation and Secret Sharing" the authors define an interactive agent and an interactive system. Further, the author defines a clocked entity for considering both synchronous and asynchronous protocols in the UC model. A clocked entity is an interactive agent which has certain rules that define how the activation token is passed.  The exact formulation of interactive agents, interactive systems and clocked entities can be found in the above mentioned book.

I have two doubts regarding the concept of clocked entities, which are described below:

Is the composition of clocked entities a clocked entity?  The authors claim that this is trivially true and does not require a proof, however, I'm not convinced with this claim. I have constructed the following counter example for the same:

Consider an interactive system $\mathcal{IS}$ composed of three clocked entities A, B and C. Further, consider a clocked entity D outside the system $\mathcal{IS}$. Let say the activation token enters the interactive system $\mathcal{IS}$ at port A.infl. Further A calls B, which in turn calls D. At this stage, A, B and $IS$ are in the calling state by definition. Now let say D calls C, which is currently inactive, hence C is activated now. But if $\mathcal{IS}$ was a clocked entity in the calling state, it should have bounced back the activation token when it receives activation token on any port other than D.leak. Hence $\mathcal{IS}$ does not follow the satisfy all the requirements of a clocked entity.

Please let me know as to what is wrong with my construction above and how the composition lemma follows from the definition of clocked entities and interactive systems.

How do clocked entities help implement synchronous protocols? What does the word "clock" signify in the word "clocked entities"?

When you compose $2$ interactive systems $\mathcal{IS}_1$ and $\mathcal{IS}_2$ into $\mathcal{IS}_1 \circ \mathcal{IS}_2$, the book indicates that you're simply connecting the matching ports between them.

In your example $\mathcal{IS} \circ D$ is a clocked entity because when $B$ calls $D$ then $D$ makes a recursive call to $\mathcal{IS}$ by sending the token to $C$. Taking from the book: "When it is clocked it must eventually
return the activation on the matching outport leak" not immediately.

Regarding your second question:

You can think of a synchronous execution as a single thread program execution which goes from one line to the next one. Each line represents an agent and the clock can be here the line number. The clock is just a flag to capture which agent is running at a given time.


using different IV and SALT with AES-CBC but same KEY I'm working on this project where a client can send a message, now obviously sending it in plainText is not very smart. So I decided to Encrypt it with AES-CBC.

Now, each time I encrypt something, the KEY is derived with PBKDF2, defined in RFC-2829, as:

DERIVED = PBKDF2(salt: 16 random bytes, key: plainText pasword, iteration count = 16834)

and this is the KEY. the IV is different every time BUT it's included in the final cyphertext.

Question: is it safe to use the DERIVED key , where the ORIGINAL key is the same, but the salt is different every time?

Question: is it safe to use the DERIVED key, where the ORIGINAL key is the same, but the salt is different every time?

No, but the reason is a little tricky.

First, forget AES-CBC—you should use an authenticated cipher like AES-GCM (if you must use AES) or NaCl crypto_secretbox_xsalsa20poly1305, and focus on the security contract.  AES-CBC is hard to use correctly and doesn't provide good security even if you do.  If you really just need to send multiple messages in sequence with a single key you've negotiated, you can just use the number of messages you've sent so far as a nonce for an authenticated cipher—no need to derive keys.

Second, if users are choosing their own passwords, you should use a modern password hash like Argon2 (specifically, Argon2id), not PBKDF2, so that you can take advantage of more of the user's resources to drive up the adversary's costs—specifically, so you can take advantage of the user's memory and parallelism too.  (If users aren't choosing their own passwords—if the computer is choosing passwords with (say) 256 bits of entropy—then there's no need for password hashing and you can skip that step.)

But let's say you have to use PBKDF2 for some reason, so that's the only way you can drive up the adversary's costs.  Should you repeatedly use PBKDF2 with multiple salts to derive multiple keys?

The purpose of the iteration count is to drive up the adversary's costs, at the expense of also driving up the legitimate users costs.  But the costs mean something slightly different to the legitimate user and the adversary:

The legitimate user cares about latency of key derivation: How long do I have to wait after I type in my password and hint ENTER before I get logged in?

If I'm willing to wait (say) one second, that's one second of resources that the application can spend on PBKDF2 to drive up the adversary's costs.  From the user's perspective, there's no difference between computing one key in one second vs. two keys consecutively in half a second each.  But from the adversary's perspective the story is a little different.
The adversary cares about throughput of password guesses: How many passwords can they guess every hour on my 100-CPU cluster?

The adversary doesn't care about deriving every key needed by the application during the password search process.  The adversary is happy if they use one key in the application to confirm a password guess.  If the application has to compute PBKDF2 twice for two different keys in one second, the adversary only has to spend half a second to test a password guess.

Even worse, if you ask PBKDF2 for a key that is longer than the hash output size, it is as if you invoked PBKDF2 multiple times in a row with the same iteration count.  There are some applications in which this may not hurt, but it was largely a stupid design.

So how should you derive multiple keys from a single passphrase?

Let's suppose you can't just reuse the key with different nonces.

Answer: Use a key derivation function, such as HKDF with SHA-256.  (Not a password-based key derivation function, also called a password hash—just a vanilla key derivation function; more on the distinction.)  A key derivation function takes a master key, such as what you got from PBKDF2, and a string uniquely identifying a purpose sometimes called the ‘info’, and returns a derived subkey.  Every time you feed in the same master key and info, you get back the same subkey, but without knowledge of the master key, the subkeys appear to be independent uniform random bit strings.

For example, you might do this:

Master key: $k = \operatorname{PBKDF2-HMAC-SHA256}(\mathit{salt}, 16384, \mathit{pw})$
File encryption key: $k_f = \operatorname{HKDF-Expand}_k(\text{‘file encryption’})$.
Backup encryption key: $k_b = \operatorname{HKDF-Expand}_k(\text{‘backup encryption key’})$.
etc.

(Note: HKDF has two steps—HKDF-Extract and HKDF-Expand.  HKDF-Extract is not necessary here: its purpose is to map a high-entropy but nonuniform bit string, like a diceware passphrase, into a short uniform bit string, but PBKDF2 already does that for us.  HKDF-Expand takes a short uniform bit string and an info parameter, and derives a subkey.  If you only have a combined HKDF-Extract/Expand module available to you, it doesn't hurt to do HKDF-Extract on the output of PBKDF2, but it doesn't do anything useful either.)

Addendum: What about the salt?

The purpose of the salt is to mitigate multi-target attacks: if everyone used the same salt, then breaking the first of $t$ targets would be cheaper than breaking one target by a factor of $t$, because there are ways an adversary can save effort by attacking many targets at once in a batch.  Adversaries like batch advantages like this because once you have a foot in the door of a network you can often exploit it to compromise more of the network.  But if everyone uses a distinct salt, that factor of $t$ batch advantage evaporates.


Probabilistic polynomial time algorithms in MAC's According to the Wiki article, a MAC is a triple of probabilistic polynomial time algorithms $(G, S, V)$ such that:

G gives the key k on input 1^n, where n is the security parameter
S outputs a tag on the key k and the input string x
V outputs 'accepted' or 'rejected' on inputs: the key k, the string x and the tag t.

From my understanding, a probabilistic polynomial time algorithm is one that runs in polynomial time, and returns a probability.

I don't really see how the outputs of G, S and V count as 'probabilities'. What are they measuring the probability of?

From my understanding, a probabilistic polynomial time algorithm is
  one that runs in polynomial time, and returns a probability.

Sadly, no. A probabilistic polynomial time algorithm is an algorithm that runs in polynomial time and may use (true) randomness to produce (possibly) non-deterministic results.
The "probabilistic" in the name comes from the fact that one can only predict certain outcomes with a certain probability. For example an algorithm that takes no input and simulates a coin-flip, would be such a probabilistic algorithm, as it's not sure (before evaluation) what the outcome will be, either head or tail?

In the concrete situation, only the key-generating algorithm must be probabilisitc (i.e. use randomness).
The tag-generating algorithm may use randomness but may also decide not to, HMAC for example is deterministic, while other MACs may not be. In either case, saying they are "probabilistic" doesn't hurt and gives the algorithms more freedom.
The verification algorithm on the other hand, must be fully-deterministic as you always want the right answer to the question "is this tag valid in this context?". However, it's still a probabilistic algorithm that just happens to never use the randomness it is allowed to use.


Digital signature algorithms within the European Union I've just noticed that US NIST has accepted DSA as a digital signature standard. Does the European Union have a similar standard, specifying an algorithm to use when digitally signing messages?

I have been looking this up for some time now, but I fail to find a reasonable answer.

Except if you are picky with updates of references, there is such standard. DSA, RSA, ECDSA-$F_p$, ECDSA-$F_{2^n}$, are approved by ETSI TS 102 176-1 V2.1.1 (2011-07) (Electronic Signatures and Infrastructures (ESI); Algorithms and Parameters for Secure Electronic Signatures; Part 1: Hash functions and asymmetric algorithms), which essentially is an update of ETSI SR 002 176 V1.1.1 (2003-03) (Algorithms and Parameters for Secure Electronic Signatures), which is referenced by CWA 14169:2004 (Secure signature-creation devices “EAL 4+”), which (in an earlier edition that it supersedes) is referenced by Commission decision 2003/511/EC (on the publication of reference numbers of generally recognised standards for electronic signature products in accordance with Directive 1999/93/EC of the European Parliament and of the Council).

However, updates of both CWA 14169 and ETSI SR 002 176 have broken the formal chain of approval, with no official repairs that I am aware of. The state of things is that Member States have their own rules, AFAIK. For France, that is currently RGS 2.0 and its annex B.1 (both in french).


Keyspace of asymmetric ciphers. (RSA) I have difficulty finding information about key space calculation of RSA. I think there is a gap in my math knowledge that prevents me from understanding the problem.

I know that symmetric ciphers such as AES 256 have key space equal to 2^256, but that can't be the same with RSA of key length 4096 that uses the product of prime numbers, can it?

The question makes a formal confusion between the keyspace, which is a set; and the size of the keyspace, which is an integer. AES-256 has keyspace equal to the set of 256-bit bitrings, noted $\{0,1\}^{256}$, which has size $2^{256}$.

Often, equivalent keys are counted only once. That's why DES is considered to have a keyspace of size $2^{56}$ even though its key is 8 octets (the low order bit of each octet is either ignored, or checked to be the complement of the XOR of the other 7). Similarly, TEA can be considered to have a keyspace of size $2^{126}$.

For symmetric algorithms, the size of the keyspace is of direct interest, since it determines the resistance to brute force key search, which ideally is the best attack.

For asymmetric algorithms like RSA, size of the keyspace is no longer directly related to security, because the public key is assumed avaialble to attackers. For this reason, size of the keyspace is not much studied, and for RSA there is not even consensus about exactly what that is. Rules vary for what a valid $N$ is, much more for a valid $e$. And it is unclear if we count (non-equivalent) pairs $(N,e)$, or just the possible $N$. We'll do the later, which alleviates the need to define a valid $e$, and makes a lot of sense since knowing a private key for $(N,e)$ allows to find a private key for any given $(N,e')$.

One possible definition of a valid 4096-bit RSA modulus is $N=p\,q$ with $p$ and $q$ prime, and $2^{(4096-1)/2}<p<q<2^{4096/2}$ (that's about what's FIPS 186-4 asks). By the prime number theorem, about one out of $\log(2^{2047.75})$ integers in the interval $[2^{2047.5},2^{2048}]$ are prime, giving about $u=(2^{2048}-2^{2047.5})/\log(2^{2047.75})$ choices for $p$. That gives roughly $u^2/2\approx2^{4070.5}$ choices for $N$. That's one possible estimate of the size of the keyspace for 4096-bit RSA. Which, again, has just nothing to do with its security.


Zero knowledge proof in smart parking managment systems I read this paper on protecting user privacy in smart parking management system. It talks about using zero knowledge proofs to protect privacy but I am not certain how they do it.  My assumption is that the Verifier has the public key of the User and sends the User challenges that the User needs to complete with its private key. Would be great if someone could clarify this to me.

I believe the answer lies in section 4 of the paper, titled "Privacy preserving outdoor parking management".

The authors explain the details of ZKP schemes later on, as well as the libraries they used and curve parameters chosen... which explains the "how" pretty clearly.

My understanding of this paper is that the the possession of secret information (e.g. personally identifying information) of a parking client is to be proven to the parking system operator in zero knowledge.

I would also add that they mention both interactive and non-interactive versions of ZK protocols. So in that case, only the prover sends a (single) message to the verifier, e.g. for the modified Schnorr protocol (5.3). Again, the client is the prover and the parking system is the verifier in this application, for this non-interactive scheme.


Cryptographic scheme where a single message cannot be decrypted but if combined with other it can be i'm wondering if this type of cryptographic scheme does exists. I know about homomorphic encryption but if one has the private key, he can decrypt every single message.

I would like to know if there is a scheme where each user can encrypt the message with a key (public?). Then, the one who has the decrypiton (private) key cannot decrypt every single message but if the messages are combined together (such as muliplied or summed), he can get the correct result.

For instance: A has a key KA, B has a key KB. A encrypts the value 1 with the key KA and obtains MA. B encrypts the value 2 with KB and obtains MB. MA and MB are published. An element C has a decryption key but he cannot decrypt MA and MB but if they are combined, such as MA+MB, he can decrypt the result and obtain 3 (1+2). I think if this type exists maybe there are several public-private keys related in a certain way...

You could accomplish this using a secret sharing scheme, which doesn't require any public key cryptography.  An $(n,k)$ secret sharing scheme allows a secret to be divided up into $n$ shares such that the secret can be recovered from any $k$ shares.  However, if you only have $k - 1$ shares you cannot recover any information about the secret.

Here, we will use a simple additive $(3,3)$ secret sharing scheme over a finite field $\mathbb{F}$.  Given a secret $s \in \mathbb{F}$, we can split it into three shares:

$$
[s]_1, [s]_2, [s]_3 \in_R \mathbb{F} \mid s = [s]_1 + [s]_2 + [s]_3
$$

Each of the three shares is uniformly distributed at random, so an adversary holding only one or two shares learns nothing about the secret $s$.  Recovering the secret from all three shares is simple:  just add them
all together.  A nice property of this scheme is that it's linear, so we can add two secrets together by adding their shares together:

$$
s_a + s_b = ([s_a]_1 + [s_b]_1) + ([s_a]_2 + [s_b]_2) + ([s_a]_3 + [s_b]_3)
$$

This means that we can do additions on the secret values while they are secret shared, and thus we can compute simple functions without revealing
the secret inputs!  In fact, there are even (complicated) protocols for
doing other operations on these secret shares, such as multiplication and exponentiation.

The protocol

Alice wants to send her secret $s_a$ and Bob wants to send his secret $s_b$ such that Charlie can only learn the sum $s' = s_a + s_b$ but not the individual values.  We assume here that all of the players are connected by secure authenticated channels.

Alice shares her secret $s_a$ by:

Keeping $[s_a]_A$ for herself
Sending $[s_a]_B$ to Bob
Sending $[s_a]_C$ to Charlie

Bob shares his secret $s_b$ the same way:

Sending $[s_b]_A$ to Alice
Keeping $[s_b]_B$ for himself
Sending $[s_b]_C$ to Charlie

Now we want each party to compute $s' = s_a + s_b$ on their local
 shares:

Alice computes $[s']_A = [s_a]_A + [s_b]_A$
Bob computes $[s']_B = [s_a]_B + [s_b]_B$
Charlie computes $[s']_C = [s_a]_C + [s_b]_C$

Finally, Alice and Bob open their result towards Charlie:

Alice sends Charlie $[s']_A$
Bob sends Charlie $[s']_B$

Charlie now has the following information:

One share of $s_a$:  $[s_a]_C$
One share of $s_b$:  $[s_b]_C$
Three shares of $s'$:  $[s']_A, [s']_B, [s']_C$

Charlie doesn't have enough shares to recover $s_a$ or $s_b$, but he can
easily recover $s'$ as:

$$
s' = [s']_A + [s']_B + [s']_C
$$

Note that this simplistic scheme is not robust, because Alice (or Bob)
could lie and provide shares $[s_a]_A + [s_b]_B + [s_b]_C \ne s_a$.  To
protect against this, you'd want to use a verifiable secret sharing
scheme so that the players can detect an inconsistent sharing.

This protocol is interactive, because it requires Alice and Bob to send their $[s_a]_B$ respectively $[s_b]_A$ values to each other.  With some
minor modifications, it could be made non-interactive.


Why does a hacker need to crack the key to an encrypted file, instead of just brute forcing the password? Most encryption softwares don't seem to have a trial limit. So why would a hacker need to crack the key, or even need to know the salt value, if he can just brute force the 6-8 digit password?

There's a few reasons.

First, most encryption doesn't rely on a password. It relies on 128-bit or 256-bit keys (for symmetric encryption at least), which are mathematically and physically outside the realm of what we consider ever possible to brute force.

Second, in systems that do derive a key from a potentially-weak password, you're right in that the password can be brute forced. However, this is why cryptographers have designed password-based key derivation functions (such as PBKDF2, scrypt, and Argon2). These impose a large computational cost upon each attempt at deriving the encryption key from the password. While it might take 500ms of computation (on a particular CPU) and 50MB of memory for a legitimate user to verify their password, this is an acceptable cost if they're only having to attempt authentication once or twice. On the other hand, this is a significant burden on someone who wants to brute force all possible combinations.


Do Message Digests protect public cryptography from replay attacks? I read about HMAC and want to be sure if it protects against replay attacks as well.

No, a MAC only prevents an attacker from modifying the message.  On its own, it does nothing to stop the attacker from resending a valid message unchanged.

To stop such replay attacks, your message have to include some contextual information that will make an originally valid message invalid if replayed.  For example, if your messages each have a sequential message number, you could simply reject any messages with the same or lower number than the highest-numbered valid message you've received so far.

(Of course, you also should be prepared to deal with the possibility that legitimate messages may be lost or arrive out of order, either due to active attacks or simply due to unreliable communications.  One option could be to use a non-cryptographic transport layer such as TCP to take care of message ordering and retransmission, and only use crypto on the application layer to verify that the data stream received over TCP has not been tampered with.  Another option would be to implement your own message transport protocol, e.g. using a sliding window approach to deal with accidental message reordering.)

What a MAC (computed over the entire message, including metadata) can do is protect these message numbers (and other relevant metadata) from tampering, so that an attacker can't simply change the message number on their replayed messages, or e.g. copy the message number from one valid message to another.


Prove integer is within the interval [a,b] I am trying to find a schema to ensure that a secret integer lies in the interval [a, b], where a and b are not power of 2.

I took a look at hash chains as described in this paper and at 'range proof' with ring signature as described here.

Unfortunately, I don't think those systems meets my requirements.
Do you know any other schema which could help me?

I can already tell that my numbers lies in the range [0, 100].
Thanks!

As I mentioned in a comment, you are looking for a range proof, see my previous answer to a related question.

You specifically ask for a solution not limited to powers of two, and for numbers known to be between 0 and 100. Let $0 \leq a < b \leq 100$ be the interval you consider. Let $m$ be your secret integer. The simplest solution I can think of works as follows:

Commit to $m$, using the Pedersen commitment scheme over a prime-order group $\mathbb{G}$ of order $p$. That is, let $\mathbb{G}$ be a prime-order group (e.g. an appropriate elliptic curve where the discrete log is hard), and let $g$, $h$ be generators of $\mathbb{G}$. To commit to $m$, pick $r$ at random from $\mathbb{Z}_p$ and send $c\gets g^mh^r$.
Commit to the bits $b_6, b_5, \cdots, b_0$ of $m-a$, using again the Pedersen scheme and $7$ random coins $r_6, r_5, \cdots, r_0$ from $\mathbb{Z}_p$, chosen uniformly at random subject to the following constraint: $\sum_i 2^i r_i = r$. For $i=0$ to $6$, let $c_i \gets g^{m_i}h^{r_i}$. Note that $m-a \leq m \leq 100 < 2^7$ so seven bits are sufficient.
Prove for each $c_i$, using a zero-knowledge proof, that it commits to a bit. As the verifier can check herself that $\prod_i c_i^{2^i} = c\cdot g^{-a}$ (because $\sum_i b_i\cdot 2^i = m-a$, and the random coins $r_i$ have been chosen to ensure that this relation will hold), if she is convinced that the $b_i$ are bits, they indeed form the bit decomposition of $m-a$, which proves that $m \geq a$ (otherwise, $m-a$ would be considerably larger than seven bits, due to the modulo reduction with $p$).
Repeat the two steps above, but using the bit decomposition of $b-m$ instead of $m-a$ this time. This will prove that $b-m \geq 0$, hence that $m \leq b$.

The only missing ingredient is a proof that a Pedersen commitment $C$ commits to a bit. There are two natural way to implement a $\Sigma$-protocol for this task.

The first possibility that comes to mind is to use an OR proof, showing that $C$ commits to $0$ OR $C$ commits to $1$. See for example the answer to this question.

The second possibility for such a ZK proof is quite simple: prove that you know $(x, s, s')$ such that $C = g^x h^s$ and $C = C^xh^{s'}$. This shows that you know an opening of $C$ to both $x$ and $x^2$; by the binding property of the commitment scheme, this ensures that $x = x^2$, hence that $x$ is a bit.


RSA - Calculating $d$ given $\varphi (N)$ and $N$ From this discussion, I know that if I know $\varphi (N)$ and $N$ (where $N=pq$, $p$ and $q$ prime), then I can very easily get $p$ and $q$.

Suppose I have the encrypted message $c$. I want to get the exponent $d$ such that $c^d \pmod N$ is the original message $m,$ without knowing $e.$

I know that it is theoretically possible to go through all the exponents from $1$ to $\varphi (N)$, and then see if the resulting message makes sense. But since I know $p$ and $q$ and $N$, I think there should be a better way than brute force.

I don't know if trying to factor $\varphi (N)$ is that much easier than trying to factor $N$? That means that even though not all numbers between $1$ and $\varphi (N)$ will have inverses (since they will not all be relatively prime to $\varphi (N)$) I won't know based on the information I have.

Is there a better approach to breaking the encryption?

Problem summary: in textbook RSA, it is given $N$, $\phi(N)$, and a ciphertext $c$. It is wanted the plaintext message $m$ and a private exponent $d$.

If $e$ or $m$ was random, that would be infeasible. But usually, $e$ is small thus guessable, and $m$ is highly redundant/recognizable. Thus we can try to compute
$$\begin{align}
d_e&=e^{-1}\bmod\phi(N)\\
m_e&=c^{d_e}\bmod N
\end{align}$$
for various small values of $e$ coprime with $\phi(N)$, and see which $m_e$ makes sense. Computing an $m_e$ has moderate cost, comparable to a normal decryption.

I'd first try $e=F_i=2^{(2^i)}+1$ for $i\in[0,4]$ (the Fermat primes, with $F_4=65537$ and $F_0=3$ very common). Then we can try (other) small odd integer $e>1$, including the popular $43$. I've also seen $e=2^{F_i}+1$ ($i\le3$), apparently due to a coding error.

If we find that a candidate $e$ is not coprime with $\phi(n)$, we can increase it by $2$ until it does, because some key generators do just that.


Summarize the mathematical problem at the heart of breaking a Curve25519 public key It's pretty easy to generate a Curve25519 private key: generate 32 random bytes of data and then do:

e[0] &= 248
e[31] &= 127
e[31] |= 64

You can then generate a public key by doing fancy math on the private key. For example, here's a random keypair I just generated:

public: e40ed268dff20db8497d0691421d00b086aad1efedcd5bd223d9eb6c0b85665f
secret: e3c0e8b20ba7894882ddb37522dbe90867befcf9f31a5ce29c0d7997e0bd856d

The whole safety of public key encryption is that it is hard to take a public key and reverse the operation. Elliptic curve cryptography, as I understand it, relies on the fact that a discrete logarithm is hard to find. In particular, for a given large b and g, it is hard to find an integer k such that

$b^k = g$

How does that equation relate to Curve25519? Specifically, if I had a public key like the one above, how would I express, in math terms, the problem I need to solve to find the private key? How does it relate to the equation I see from time to time - $y^2 = x^3+486662x^2+x$, and the number $2^{255} - 19$?

I am guessing it is not as simple as "the private key is k and the public key is b and/or g" in the equation above. I'm also a little confused because the keys would appear to have roughly the same number of digits, which would seem to imply that there aren't many feasible values for k?

Six-word summary: the elliptic-curve discrete log problem.

$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}$Summary with math: Given $x(A)$ and $x(P)$ for two points $A$ and $P$ on the elliptic curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\Z/(2^{255} - 19)\Z$, find an integer $a$ such that $A = [a]P$, where $[a]P$ is scalar multiplication on the curve.  We pick $a$ (in your notation, $k$) uniformly at random from $2^{251}$ possibilities, so that the best algorithms for computing it from $x([a]P)$ (in your notation, $b^k$) cost about $2^{125}$ arithmetic operations, more than any adversary can ever hope to carry out.

Or, more precisely, we rely on the computational elliptic-curve Diffie–Hellman problem: Given public keys $x(A)$, $x(B)$, and $x(P)$, find $x([ab]P)$ where $A = [a]P$ and $B = [b]P$.  But it seems to be not much easier than the ECDLP.

In a little more detail:

The number $p = 2^{255} - 19$ is a prime, so every integer that is not a multiple of $p$ has an inverse modulo $p$, and thus the integers modulo $p$ form a finite field $\F_p = \operatorname{GF}(p) = \Z/(2^{255} - 19)\Z$.  A field is necessary to define an elliptic curve.  The number $p$ is convenient because it is under $2^{256}$ but not too much under, and very close to a power of two.  Thus:

Every set of integers that are congruent modulo $p$ has a representative that can be written in 256 bits = 32 bytes (= 64 hex digits, as you have noticed).  In fact, it takes only 255 bits, which leaves one extra bit that turns out to be handy for encoding curve points.
To reduce an integer $u \geq p$ to an integer $\overline{u} < p$ congruent to $u$ modulo $p$, you can exploit the fact that $2^{255} \equiv 19 \pmod p$, so if $u = 2^{255} u_\mathrm{hi} + u_\mathrm{lo}$ for $u_\mathrm{lo} < 2^{255}$, then $u \equiv 19 u_\mathrm{hi} + u_\mathrm{lo} \pmod p$.

In other words, you can shift $u$ right by 255 bits, multiply it by 19, and add it to the low 255 bits of $u$; then the result differ will from the input by a multiple of $p$—with no need to compute general integer division, which makes crypto engineers happy because fast integer division that doesn't leak the values of the inputs to an adversary with a stopwatch is hard to do.

There are two main equivalent ways to view Curve25519.

One view of Curve25519 is that it is the set of all roots of the polynomial $$y^2 - x^3 - 486662 x^2 - x$$ over $\F_p$, each point written as affine coordinates $(x, y)$, together with an additional point written $\mathcal{O}$ called the point at infinity that does not have a representation in affine coordinates.

Another view of Curve25519 is that it is the set of all lines of roots of the polynomial $$Y^2 Z - X^3 - 486662 X^2 Z - X Z^2$$ over $\F_p$, each line written as homogeneous coordinates $(X : Y : Z)$ for $X, Y, Z$ not all zero, where $(X : Y : Z)$ represents the same line as $(\lambda X : \lambda Y : \lambda Z)$ for any nonzero $\lambda$.  The point at infinity has homogeneous coordinates $(0 : 1 : 0)$, and thus need not be treated separately as it is in affine coordinates.  Any other point with affine coordinates $(x, y)$ can be written with homogeneous coordinates $(x : y : 1)$, and any line with homogeneous coordinates $(X : Y : Z)$ for nonzero $Z$ can be written with affine coordinates $(X/Z, Y/Z)$.

The elements of Curve25519 form a group under a somewhat elaborate definition of addition (summarized on Wikipedia, and derived from a long rich history of mathematical theory contributing to the proof Fermat's last theorem, to fast algorithms for factoring large integers, and to dreams of a grand unifying theory of mathematics) defining a point $P + Q$ given points $P$ and $Q$ on Curve25519, for which the point at infinity is an identity so that $P + \mathcal{O} = \mathcal{O} + P = P$ for every point $P$, and for which there is an inverse $-P$ with $P + -P = P - P = \mathcal{O}$.

From this, we can define the scalar multiplication $[n]P$ of a point $P$ by an integer $n$ as $[n]P = P + \dots + P$, the $n$-fold addition of $P$ to itself, which has the property that $[n]([m]P) = [nm]P = [mn]P = [m]([n]P)$ for any other integer $m$, where $nm = mn$ is the product of two integers.

For any given $x$ coordinate, there are at most two possible points on Curve25519 with that $x$ coordinate, corresponding the two roots of the quadratic polynomial $y^2 - x^3 - 486662 x^2 - x$ in $y$.  There may not be any such $y \in \F_p$, if $x^3 + 486662 x^2 + x$ is nonsquare, or a quadratic nonresidue, modulo $p$, but we can augment $\F_p$ with a fabricated element $\sqrt{2}$ and all formal terms $a + b\sqrt{2}$ for $a, b \in \F_p$, giving the extension field $\F_{p^2}$ in which every nonzero element of $\F_p$ has exactly two square roots.  (If you augment $\F_p$ with roots for all polynomials, you get $\overline{\F_p}$, the algebraic closure of $\F_p$, and most elliptic curve theory in algebraic geometry is developed over algebraically closed fields such as $\overline{\F_p}$ and $\mathbb{C}$.)  The points on Curve25519 with coordinates in $\F_{p^2}$ are called the $\F_{p^2}$-rational points, and for every $x \in \F_p$ there are exactly two $\F_{p^2}$-rational points with that $x$ coordinate.

It turns out that for any $\F_{p^2}$-rational point $P$, if $x(P) \in \F_p$ then $x([n]P) \in \F_p$ too for all integers $n$, if we prescribe the abuse of notation that $x(\mathcal{O}) = 0$.  (This is Theorem 2.1 of the Curve25519 paper, with some details omitted.)  And this particular form of curve, a Montgomery curve—as opposed to, e.g., a short Weierstrass curve $y^2 = x^3 - a x + b$ for some $a, b \in \F_p$—admits very fast arithmetic to compute $x([n]P)$ given $n$ and $x(P)$ using only $X$ and $Z$ coordinates, in constant time independent of the values of $n$ and $x(P)$ so that someone who can time the computation from start to finish learns nothing about those values.

X25519 is a public-key key agreement scheme made out of elliptic-curve Diffie–Hellman over a group of $\F_p$-rational points of Curve25519.  Alice's private key is a secret integer $a$ chosen uniformly at random from $2^{251}$ possibilities.  Her public key is the $x$ coordinate in $\F_p$ of a point $A = [a]P$, where $P$ is a point with $x(P) = 9$.  If Bob's public key is $x(B)$ for some point $B = [b]P$, their shared secret is $$H(x([a]B)) = H(x([a][b]P)) = H(x([b][a]P)) = H(x([b]A))$$ which as you can see can be computed either by Alice or by Bob from the information known to each of them, where $H$ is some standard hash function mapping $\F_p$ to octet strings.

(For the full details of how to choose $a$ and how to encode secret scalars and public keys as octet strings if you wanted to implement X25519, see the Curve25519 paper or RFC 7748.  Note that when it was introduced, the name ‘Curve25519’ meant just the DH function.  The names have since been changed so that ‘Curve25519’ now means the curve, and ‘X25519’ is the DH function.  A birationally equivalent curve in twisted Edwards form, sometimes called Ed25519 or loosely just Curve25519 in twisted Edwards form, is used for signatures now too.)

The computational elliptic-curve Diffie–Hellman problem is to find $x([ab]P)$ given elements $x([a]P)$, $x([b]P)$, and $x(P)$ of $\F_p$.  The best known ways to do this are all by way of the elliptic-curve discrete log problem, which is to find, given two elements $x(P)$ and $x(A)$ of $\F_p$, an integer $a$ such that $A = [a]P$—that is, to find the secret scalar of a scalar multiplication.

The best generic ways to do this, knowing only how to compute the group operation, are Pollard's rho and kangaroo algorithms, which cost about $2^{125}$ group operations—likely more than anyone will ever compute.  If the base point $P$ had composite order—that is, if the smallest integer $n$ such that $[n]P = \mathcal{O}$ were composite—then the Pohlig–Hellman algorithm could compute $a$ faster by computing it modulo each factor of the order of $P$ independently.  But $P$ has prime order $p_1 = 2^{252} + 2774231777737235353585193779088364849$, so Pohlig–Hellman doesn't help, just like it doesn't help much in finite-field Diffie–Hellman over a safe prime of the form $2q + 1$ for prime $q$ or if the FFDH generator has prime order.

In the Lim–Lee attack (adapted to elliptic curve groups), if the attacker sends Alice the $x$ coordinate of a point $Q$ that is not a scalar multiple of $P$—possibly not even an $\F_p$-rational point but only an $\F_{p^2}$-rational point—and has small order $k$, then since $[a]Q = [a \bmod k]Q$, by checking which of $k$ possible derived shared secrets Alice uses, the attacker learns a little about $a$, namely $a \bmod k$.  But the only possible small orders of elements of points with $x$ coordinates in $\F_p$ divide 8, and Alice always chooses $a$ so that $a \bmod 8 = 0$—that is what (part of) the bit-twiddling at the beginning is about.

The number 8 is the cofactor of Curve25519, because the group of $\F_p$-rational points has order $8p_1$.  The group of $\F_{p^2}$-rational points with $x$ coordinates in $\F_p$ and $y$ coordinates not in $\F_p$ but in $\sqrt{2}\F_p$, called the twist of the curve, has order $4p_2$ for a large prime $p_2 = 2^{253} - 5548463555474470707170387558176729699$.  No legitimate public keys are on the twist, but the attacker can feed in what look like public keys that are.  This is the subject of twist security, and is the reason why $\F_p$ was not the only actor in the story of fields above.

There is more to the elliptic curve security story.  Further reading:

Everything else at SafeCurves.
A gentle introduction to the basics of algebraic geometry and computing with it:
David Cox, John Little, and Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd ed., Springer UTM, 2000.  ISBN: 978-0-387-35650-1.
Throw yourself into the deep end of algebraic geometry with:
Robin Hartshorne, Algebraic Geometry, Springer GTM, 1977.  ISBN: 0-387-90244-9.
For the specific topic of computing with elliptic curves:
Joseph H. Silverman, The Arithmetic of Elliptic Curves, 2nd ed., Springer GTM, 2009.  ISBN: 978-0-387-09493-9.
For a comprehensive survey of everything you ever need to know about elliptic curve cryptography up to 2006:
Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, 2006.  ISBN: 978-1-58488-518-4.


Synchronous Stream Cipher Problem Hello I am facing a problem trying to solve this question in the picture. Does anyone know how to produce the mentioned 32-bits of the key stream? The plaintext in this case is 0001  0001 0000 0000 1001 0111 0110 1001. The LFSR is also included as a picture below.

Thanks in advance

The question as stated has some serious issues:

The alternating step generator works with 3 LFSRs. If the output of R1 is 1, then R3 is clocked, otherwise R2 is clocked, so at each clock period exactly one of those two is clocked. The output of R2 and R3 is added modulo 2 to form the keystream. The initial loadings of the 3 LFSRs is essentially the key.

The example in the question is quite strange. The LFSRs should be maximum length (i.e., primitive). You can have a primmitive LFSR of cycle length 7, e.g., and instead nonprimitive LFSR with cycle lengths 5 and 6 are used--this would have statistical properties worse than a primitive LFSR and lead to problems.

Even ignoring this, the nonstandard notation $<4, 1+D, D^3>$ is used for R1. I have no idea what this means.

In particular, in the figure from part (b), a constant bit of $0$ is AND'ed to one of the registers which might as well be removed, since the output is always zero! Thus, the LFSR is defective in that it is only sampling two bits, and not at the two ends.


Lattice-based cryptosystems for blockchain/ledger? Are there lattice-based cryptosystems based i.e., SIS (Short Integer Solutions) and LWE (Learning with Errors) blockchain solutions for a post quantum world?

Has the Unique Shortest Vector Problem (SVP) been solved?

Are there [...] blockchain solutions for a post quantum world?

Quantum Computing and related algorithms are no threat to the current protocol of Bitcoin (and most other blockchain systems I am familiar with) at all. Indeed, Shor's algorithm can solve the Discrete Logarithm Problem (DLP) efficiently, and a modified version exists for the elliptic curve analogue (ECDLP). Blockchain systems in their conventional form are based on

preimage and collision resistance of the employed hash functions for most functions, including transaction IDs, block IDs, and the Proof-of-Work (PoW) scheme in mining
hardness of DLP/ECDLP for security of transaction signatures and user addresses (so that private keys can not be found)

At the current state of research, most consider hash functions quantum resistant due to their lack of mathematical structure. As mentioned, (EC)DLP is not resistant.

However, if user addresses are never re-used then this is irrelevant, since an attacker will only learn a users clean (i.e. non-hashed) public key once a transaction is signed in the name of said user address/public key. As long as the hash function (e.g. SHA-256) is preimage-resistant, an attacker has nothing to apply Shor's algorithm on.
So there is no pressing need for alternatives yet.

Nonetheless, lattice-based crypto is a proposal that comes up once in a while - to my knowledge no actual blockchain implementation exists as of today. As for the Shortest Vector Problem (SVP): the most efficient known algorithms are mentioned in the Wikipedia article.


What do GnuPG sign-only keys mean? In GnuPG, there is the option of making keys which are "normal" (encrypt and sign) and sign-only keys . But what sense does that make in regards of DSA?
Correct me if I am wrong, but I think DSA keys can only sign anyway.
So what is the difference between sign-only and normal keys?

Actually there are even more possible options if you use the --expert flag in GnuPG:

$ gpg --expert --gen-key
Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)

As you can see, you can decide to have DSA sign only, but also RSA sign only keys. What's more, DSA keys can also be used as "authentication" subkeys, so you can set your own capabilities for those as well as for the RSA keys (which can also serve for encryption, whereas DSA subkeys cannot)

Now, the difference between a "sign" subkey and an "authentication" one is simply in their respective goals, to allow strong segmentation between signing and authentication processes. The primitive used in both case are the same...
You'll typically use an authentication subkeys for SSH auth (this mainly allows to have your SSH key on a smartcard) and you'll use the signing subkey to sign data. (In the auth case you'll be signing only challenges.)


AES Is it safe to expose the plaintext and cyphertext in the same place, In a web application, I need to send in a webpage form an id (my plain text) and then retrieve it back when the user submit the form.
But i need the id to be protected, so malicous users can't send an incorrect id to the server.

I was thinking to send the id and the cypher text to the client, and when i retrieve them server side, i decrypt the cypher text, and if the id don't match the decrypted value, i reject the call.
I am using AES with 256bit key.

So the question is : is it safe to do that? is there a better way?
thank you for your help

PS : There is a business need to send the id as plain text (not encrypted) to the client.

Use a message authentication code if you want to ensure that the id is not modified by the client. Use SSL between the server and the client if you want to prevent replay etc network layer attacks from eavesdroppers.

But a malicious client can still reuse previously received ID. If this is a concern, you need to do more (e.g. use and keep a nonce for verification).


What is the importance of $f_k$ in a feistel network being a permutation I was doing some cryptography exercises, one of which was an example of a feistel network. It said that the function $f_k$ was a permutation for all k but didn't explain why that makes a difference. So what is the importance of a function being a permutation in a feistel network?

I assume that you are referring to the round function. This is false. The whole advantage of a Feistel network is that $f_k$ does not need to be a permutation. Indeed in DES, it is not a permutation. In an substitution-permutation network it needs to be a permutation so that it can be inverted, but in Feistel inversion is possible in any case. Thus, you have more freedom in choosing $f_k$.


Elliptic curve in Binary Field implementation For Elliptic curves defined over $GF(2^n)$, by adding any two points P and Q over $GF(2^n)$ we get the third point over $GF(2^n)$.
In Elliptic Curve Digital Signature Algorithm (ECDSA) https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
, there is a usage of prime numbers, particularly for the calculation of multiplicative inverse. It works fine for the Weierstrass form of Elliptic curve over $GF(P)$.
Now, I want to implement ECDSA using a binary form of Elliptic curve (like Hessian curve), but every time I am doing it, it is giving the wrong answer. My question is, is it not possible to use any curve over $GF(2^n)$ for an implementation like this?

Yes it can. The only variation from the wikipedia article is in step 5 where it states to calculate $r\equiv x_1\pmod{n}$. This does not make sense when $x_1$ isbn element of a binary field. Instead binary field elements are converted to integers by a standards prescribed process (see ANSI X9.62-1984 section 4)


Why is a one-time MAC secure for MAC-then-encrypt with randomized-CTR but not randomized-CBC? The Coursera cryptography 1 course says:

  If you want to use MAC-then-encrypt mode then you should either use
  randomized-CTR or randomized-CBC. And if you use randomized-CTR then
  one-time-MAC is sufficient.

Here is the slide:

I have two question regarding this:

How we can use one-time-MAC without negotiating the different keys for each message?
What is wrong with randomized-CBC that doesn't allow us to use with one-time-MAC?

How can we use one-time-MAC without negotiating the different keys for each message?

If you use a universal hashing one-time MAC, and you encrypt it with CTR mode, effectively you are creating a Carter–Wegman–Shoup MAC:

Carter and Wegman showed[1] that if $r, s_0, s_1, \dots$ are independent uniform random and $H_r$ is a universal hash with bounded difference probability $\Pr[H_r(x) - H_r(y) = \delta] < \varepsilon$ for all $x \ne y$ and $\delta$, then the forgery probability for the authenticator $m_i \mapsto H_r(m_i) + s_i$ is bounded by $\varepsilon$.
Shoup suggested[2] deriving $s_i = E_k(i)$ for a block cipher $E$, which is essentially what you get with MAC-then-encrypt in CTR mode.  Since $E_k$ is a permutation you run up against the birthday bound, of course, just like any use of a block cipher in CTR mode.

  What is wrong with randomized-CBC that doesn't allow us to use with one-time MAC?

Offhand, I am not sure!  If the one-time MAC is a universal hash with bounded collision probability $\Pr[H_r(x) = H_r(y)] < \varepsilon$ for all $x \ne y$, then this intuitively sounds like it ought to be a secure construction, because $m \mapsto F_k(H_r(m))$ is a secure long-input, short-output PRF if $F_k$ is a secure short-input, short-output PRF and $H_r$ has bounded collision probability[3].  That's not exactly the scenario we have here, because there is not one fixed family $F_k$—if we encrypt $m \mathbin \| H_r(m)$, we get $$E_k(\mathit{iv} \oplus m) \mathbin\| E_k(E_k(\mathit{iv} \oplus m) \oplus H_r(m)),$$ so $m$ figures in twice, but it's pretty close, so intuitively it seems like this should be secure.

Of course, it's not clear that the mere security of a one-time MAC—a bound on forgery probability after a single attempt—implies any of this even with CTR: I'm assuming bounds on collision or difference probabilities, specifically.  Maybe you could ask Dan Boneh what he meant.

There is also a danger of padding oracles with CBC in MAC-then-encrypt or MAC-and-encrypt, because CBC works on sequences of blocks rather than sequences of bits, which is why it is hard to get right: practical realizations like TLS and SSH had mistakes for years that leaked plaintexts via padding oracles.


Linear cryptanalysis and number of linear approximations I try to understand the linear cryptanalysis. Now I am reading as a secondary reference the book "Cryptanalysis of Block Ciphers:
A Survey" by Standaert , Piret and Quisquater. In the first step, the authors are saying that there are $(2^n-1)\times(2^m-1)$ linear approximations for a $n$-input vector and a $m$-output vector.

Since a linear approximation is a linear map between $\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m$, should the number of linear approximation not be $2^n\times 2^m$? Or do I miss a part?

I am grateful every help.

Sincerely,
Hypertrooper

It most likely assumes both $a$ and $b$ are nonzero in
$$
a \cdot x + b\cdot y.
$$
If either are zero, the overall inear approximation will be insensitive to changes in plaintext (respectively ciphertext) making the overal linear expresion useless to mount a linear attack on a multiround cipher, since the idea is to extract subkey bits by using enough known ciphertext plaintext pairs.


What is the totient function for an RSA modulus has several factors due to incorrect setup? $ϕ(n)=p.q−(p+q)+1$ where there are two factor $p$ and $q$, but what if there were 3 (or more) factors such as $(p,q,r)$ due to a typo in specifying the modulus?

$\phi(p \cdot q \cdot r \cdot ... \cdot s) = (p-1)(q-1)(r-1)...(s-1)$ (for $p, q, r, ..., s$ distinct primes)

In addition, the technically correct modulus for which $e \cdot d \equiv 1$ must hold is commonly known as $\lambda(n)$; in this case,

$\lambda(p \cdot q \cdot r \cdot ... \cdot s) = \text{lcm}(p-1, q-1, r-1, ..., s-1)$


What is "msg = group.random(GT)" in Charm encryption schemes? In many encryption schemes in Charm the random group message is used instead of a text-message:

msg = group.random(GT)

For example, in CP-ABE scheme, random message is used:

cpabe = CPabe_BSW07(group)
msg = group.random(GT)
attributes = ['ONE', 'TWO', 'THREE']

See link for scheme details: http://jhuisi.github.io/charm/charm/schemes/abenc/abenc_bsw07.html

Can anyone clarify for me whether I can use my own text-message instead of random ID here. I tried with a encoded byte-array but no luck. What is group.random(GT)? Can I use a custom message?

In real world applications Attribute-based Encryption (ABE) is used in conjunction with a symmetric cipher, because you can only encrypt group elements with ABE. In this case it is the multiplicative group $G_T$.

The number of bits is limited when you try to represent text messages (bit strings) with a group element, because the size of the group is derived from a prime. In Charm it is most likely 512 bit prime. You cannot represent messages that are bigger than any group element, if you would have a mapping function to map bit strings to group elements and back again.

Generally something else is done. It is called hybrid encryption in the context of ABE. The text message is encrypted using AES or other symmetric ciphers and the random key that was used is derived from the random $G_T$ element.

Generate a random $G_T$ element with el = group.random(GT).
Generate bytes from el e.g. like this extractor(el) or even hashlib.sha256(str(el)).digest() which can be directly used as the AES key.
You would encrypt your text message with a symmetric cipher like AES-256 using the previously generated key.

Charm provides something for steps 2 and 3: SymmetricCryptoAbstraction.

The schemes that are implemented in Charm don't go this far to implement hybrid version of the scheme, because it would be the same for every one of them. It is unnecessary for the validation of the functionality of the scheme. This is why the message is just a random group element as a placeholder for a real world message.


Are there any "cumulative signatures" for decentralized networks? Lets assume that there is a decentralized network $N$ with participants $A,B,C, D$ and that there was a message $m$ that all of $A,B,C,D$ agreed to. An outsider $X$ wants to know via signatures that $m$ was indeed agreed to by all of $N$.

Is there a way of combining the signatures of $A,B,C,D$ such that $X$ just has to check one signature? So if $m$ arrives at $A$ first, then $B,C, D$ they sign $D(C(B(A(m))))$ which would translate into $N(m)$ which $X$ only had to check once regardless of the order of $A,B,C,D$ in $D(C(B(A(m))))$? Is there any literature on this or does such an algorithm not exist (yet)?

You can have a look at Collective Signatures for example, which is, in a nutshell, the addition of multiple schnorr signatures resulting into a unique aggregated signature. The verifier needs to know only of one public key in order to verify such as signature, which is the aggregate public key of all participants.
Have a look also at MuSig for a more recent work applying this concept for Bitcoin with a twist.

Here it is important to note that you did not specify you threat model. If you assume all participants are present and honest during the signature generation, everything is so easy. When you start introducing some malicious adversaries, then things will get a bit more messy ;)


Why doesn't this defeat RSA? Apologies for the obviously ridiculous question but I need to know where I'm going wrong here.

For RSA, we compute $n=pq$ for primes $p$ and $q$. We then choose an $e$ such that $gcd(e, \varphi(n))=1$ and compute $d$ such that $ed = 1 \mod \varphi(n)$. The public key is $(n, e)$ and private key is $(\varphi(n), d)$. I see how this is correct and so on.

My question is this: Why doesn't an attacker just compute $d'$ such that $ed'=1 \mod n$? Then surely decryption will work mod $n$?

eg where does this go wrong? $e=3, p=11, q=17, n=187, M=2$ Then $C=M^3=8$ Attacker calculates $e^{-1} \mod n = d' = 26$ and $8^{26}= 2 \mod n$?? More generally $C=M^{ed'} \mod n = M^{1} \mod n = M$?

You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$.

In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell \pmod n$. Note that in the statement of the previous paragraph, $\phi(N)$ is not necessarily the order of $a$, hence it did not have the "only if" part.

EDITED to add: This is actually an important issue which bears emphasis because it occurs often in cryptographic contexts. When working with powers of an element in a group, it is important to remember that the exponents should be viewed as integers modulo the order of the element. In an abstract group this is not a problem, but when the group is integers modulo some $N$, it is easy to "think modulo $N$" also for the exponents, but it leads to this sort of errors.


Why is GCM not vulnerable at the birthday bound for 128 bit IV? According to this article, which looks at attacks on Caesar candidates beyond what they claim, they include an attack on page 6 for nonce-respecting adversaries for AES-GCM which allows IVs longer than 128-bits at the birthday bound (i.e., $2^{64}$).

My question is why is GCM not susceptible to this attack for 128-bit IVs? I could understand this if the GHASH calculation for a 128 bit IV acts as a permutation (and if so, could someone please prove this)?

Actually, it turns out that GHASH on 128 bit values is a permutation (unless $H=0$; this happens with probability $2^{-128})$

GHASH of a 128 bit value $X$ simplifies to $\text{GHASH}_H(X) = H \times X$, where $H$ is a function of the key (that is, will always be the same for a specific key), and $\times$ is multiplication in the field $GF(2^{128})$.

This is a permutation, as $GF(2^{128})$ is a field, and multiplication in a field by a fixed nonzero value is always a permutation.

As for the 'collision' you mention in your comments, that actually can't happen.

If we have $H \times I_1 = 128$, that means that $H \ne 0$ and $I_1 = 128 \times H^{-1}$

If we have $H \times ((H \times I_2) \oplus 128) = 0$, that can happen only if $H = 0$ (which can't happen if the first equation holds) or $(H \times I_2) \oplus 128 = 0$, which holds only if $H \times I_2 = 128$, that is, if $I_2 = 128 \times H^{-1}$

Hence, for both to hold, we must have $I_1 = I_2$, and thus this isn't a 'collision'


How do I construct and use the Okamoto protocol simulator? Proof Okamoto protocol has zero knowledge if we constructing a suitable simulator

I found the following schema of Okamoto:

But I don't really understand —how can I construct such a simulator and create proofs?

There is "zero knowledge simulator" and "honest verifier zero knowledge simulator". General idea is reversing the order of variables picked at random or cauluated. Namely, pick the simulated challenge and response first, and calculate the first message $a$. For HVZK, just pick a challenge and a response at random, calculate proper first message using verification equation. For ZK, one should get a challenge by querying the real Verifier. This means running a session with Verifier and sending some random first message. Please note I did omit minor details doable as a homework.


Clipper chip (SKIPJACK) key exchange protocol According to the Wikipedia page for NSA (emphasis mine):

  However, NSA's Fortezza hardware-based encryption cards, created for
  the Clipper project, are still used within government, and NSA
  ultimately published the design of the SKIPJACK cipher (but not the
  key exchange protocol) used on the cards.

However, the NIST publication describing SKIPJACK also describes a Key Exchange Algorithm (KEA).

My question is simple: Is the Wikipedia page wrong, or is it talking about something else?

Wikipedia is wrong in this case - just like the NIST publication describing SKIPJACK already implies by being titled "SKIPJACK and KEA Algorithm Specifications". In fact, on page 17 of that paper, you will find infos about KEA exchange for Email and on page 12, there's a summary of a full KEA exchange between devices A and B…

A summary of a full KEA exchange between devices A and B (page 12)

A summary of an Email KEA exchange between devices A and B (page 17)

On a side-note: If you check the Wikipedia entry, it shows that Wikipedia entry has been edited meanwhile, just like @ilmari-karonen already mentioned in a comment.


What is "electronic" in electronic codebook (ECB)? This is an honest question regarding terminology. I believe that I understand why one mode to use a block cipher is called a codebook. But I wonder why electronic as a work appears here?

Is it fair to say this is just a fancy/stylish addition?
Should it relfect that often encyption is used with electrical devices?
Would ECB be impossible for a mechanic setup?

In a paper codebook, plaintext words (perhaps arranged alphabetically like in a dictionary) lead to a replacement word.

Cipher for Telegraphic Correspondence — a code book used by Union General Joseph Hooker’s code clerk. Source: wikipedia.

A block cipher implemented using electronic circuitry (as DES was initially) does the equivalent, with block instead of word, and new key instead of new book. That's thus an electronic codebook. The operating mode based solely only this feature is Electronic CodeBook.

It would be possible to implement a block cipher using non-electronic means, e.g. mechanic of even manual; and operate it in ECB mode. Fact is, this was not done on a large scale. Before DES, mechanical ciphers tended to operate on a letter-by-letter basis, not something wide comparable to a word.


Crypto-Compression Algorithms? I was wondering, whether there exist such algorithms/enciphering procedures which both compress and encrypt the input data. That means, for starters, the output will be both smaller in size and difficult to decrypt...and if the compression algo is good, then the bits will be almost random.

Also any twin-encryption algo-s around?: by which I mean, suppose I have 2 data strings (alphanumeric only, say for now) -- Using them both, and an algo, I produce the encrypted output - I take in a pair, and produce a pair. The procedure is algo-based and not key-based. Any comments on this? And how this could relate to the earlier crypto-compression problem? (One way it would relate is, if the data is not just strings of characters, but a large multimedia file, it can be compressed fast and securely apart from being encrypted)

The FAQ says "please ask questions that can be answered, not merely discussed" but I can not be more specific, atleast not now: if it had some coding, I might have posted it on stackoverflow!

All comments, with links to other Q&A are welcome. Other forum addresses are also welcome!

Unlike some crypto tasks like encryption+authentication combining compression+encryption have nothing in common/non synergies, so combining them into one algorithm offers no advantages.

In practice this means you first compress your data, and then encrypt it, because encrypted data is uncompressable. That way you cleanly separated the separate concerns, and you can vary them independently.

A good point to combine them is at the protocol/fileformat level. For example TLS supports compression and encryption, as do most archive formats(zip, rar, 7z,...).

But compression can hurt security: Typical encryption is designed to hide everything about the data, except its length. Compression depends on the data itself and affects the length of the data. That means that it can leak information about the data through the length bypassing the encryption. This is particularly severe if you compress data chosen by the attacker and secret data within the same context. This lead to the CRIME attack against TLS compression.


Should the secret key of Shamir's secret-sharing algorithm be interpreted byte by byte? Should the secret message of Shamir's secret-sharing algorithm be interpreted and processed byte by byte?
Interpreting it byte by byte makes it easier to process, but in case one of the shareholders decides to tamper with some of the bytes in his possession, this will affect the secret reconstruction.
This is a serious risk, and I don't know how it could be prevented.

Would it be sensible, as an alternative, to interpret the secret message as a whole string, instead of byte by byte, transforming it into an integer? In this case, what I am worried about is the huge size of the integer...

Shamir's secret sharing scheme provides only confidentiality against shareholders who want to try to learn the secret.  It does not prevent denial-of-service attacks (or attacks on integrity), where a malicious shareholder submits a bogus share to try to cause the reconstruction of the shares to fail.

If you want security against that sort of attack, don't use Shamir's secret-sharing scheme; there are other schemes that can accomplish that.  Verifiable secret sharing schemes do exactly that: they protect against malicious shareholders who submit bogus shares.  There are many constructions of verifiable secret sharing schemes in the literature.  They do exactly what you want.

Depending upon your application, you may also find threshold cryptography  relevant.


why Efail CFB malleability gadget is different from CFB mode decryption? Really, I could not understand why the decryption process of CFB malleability gadget takes the next cipher block while PGP uses the previous block as shown in the equations in the attached image, I read Efail attack paper but I could not understand how it works? Could someone clarify it to me.

Both schemes present in your image represent the same thing. Only the indexing of Ci differ by 1. It all depends on what you consider to be your "first block":

In the first, you decrypt by manipulating the previous block and the current block. This means your decryption process start with C-1 and C0 to recover P0. Here, C-1 = IV
In the other, you decrypt by manipulating the current block and the next. So P0 = Enc(C0) XOR C1, meaning C0 = IV.

Clarification:

CFB malleability gadget does not modify the decryption process in any way. The only trick is to modify the ciphertext before decryption.

You seem to have trouble with the notation and the block indexing, so here is a little example of how the CFB gadget would be used. In this example, C0 is the first block of encrypted data, the IV is considered apart (whereas C0 is the IV if we follow Efail notation, hence the shift in the index you may notice in my figure).

To make it clear, keeping the same notation as in my figure, CFB decryption would go as follow:

P0 = Enc(IV) xor C0
P1 = Enc(C0) xor C1
P2 = Enc(C1) xor C2
...
Pi = Enc(Ci-1) xor Ci
Pi+1 = Enc(Ci) xor Ci+1
...

That is how CFB decryption works, whether or not you are using it as a gadget.


How do you apply bilinear mapping to attribute based encryption? I'm new to both bilinear mapping and ABE. I have a vague idea of how bilinear mapping works now, but I don't understand how it applies to ABE. Can someone give me an example?

You can study pages and papers below to understand bilinear maps (or pairing) and ABE.
https://en.wikipedia.org/wiki/Pairing-based_cryptography
https://eprint.iacr.org/2004/086.pdf
https://eprint.iacr.org/2006/309.pdf


What is the fastest block cipher in the (Intel) world? In AES competition,Rijndael cipher obtained first rank and become Standard and Serpent, Twofish, RC6 and MARS obtained another ranks and I know that Serpent took second rank because it was slower than Rijndael.

My questions are:

Is Rijndael the fastest block cipher in the world?
What is the reason of 10 negative votes for Rijndael in AES2 conference?
What is the fastest block cipher in the world? (for software implementation on Intel processor)

In my question, suppose that I implement all known block ciphers with equality of condition (key size, block size, software implementation on PC) then which secure block cipher is fastest?

The fastest block cipher is identity, which leaves input blocks completely unchanged. This is infinitely fast on all platforms; however, it is not secure. So maybe you want the fastest block cipher that still offers some given non-trivial level of security?

Then it depends a lot on what you want to implement the block cipher on. With recent PC, you would have a hard time getting anything faster than AES, because of specialized opcodes -- although you could define a block cipher that is identical to AES except that it has 9 rounds instead of 10. That alternate block cipher would be faster and still secure, but with less "security margin", an intuitive but very poorly defined notion.

During the AES competition, Rijndael was outperformed on some platforms, e.g. on the PC of that day, RC6 was faster. But Rijndael offered the most consistent performance on platforms of that era: there was no software platform (including 8-bit CPU) were it was abysmally slow, and it was perceived to be reasonably hardware-friendly (contrary to, say, RC6).


Example of a PRP that is not a strong PRP The exact definition of security for a pseudorandom permutation is straightforward - for some encryption scheme $E\,\colon\,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D}$, it must be the case that no efficient adversary can distinguish $E_k(\cdot)$ from $\Pi(\cdot)$ (a random permutation on $\mathcal{D}$) except with negligible probability. A "strong" PRP is defined the same way, except $E_k(\cdot)$ and decryption $D_k(\cdot)$ must be jointly indistinguishable from $\Pi(\cdot)$ and $\Pi^{-1}(\cdot)$.

I've thought about this but I can't quite come up with an example of an $E$ whose encryption is indistinguishable from a random permutation but its decryption doesn't have the same property. Does anyone have a nice example?

EDIT: I saw DW's example in the answer of this question. It is a very clever construction but quite 'unnatural' as well. Are there more straightforward examples?

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP.

A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$, where $f$ is an element of a pseudorandom function family.  This PRP will be keyed with three keys $k_1, k_2, k_3$, which will be used to key a PRF $F$ differently each round.

We define $E_{k_1,k_2,k_3}$ to be a three-round Feistel network:

$E_{k_1,k_2,k_3}(L \| R) = \operatorname{Concat}(P_{F_{k_3}}(P_{F_{k_2}}(P_{F_{k_1}}(L, R))))$

Assuming $F$ is a PRF, $E$ will meet the definition of a weak PRP.  I believe this proof is originally attributed to Luby, Rackoff (for details of the proof, see here, starting on page 11).  Similarly, the inverse $D_{k_1,k_2,k_3} = E^{-1}_{k_1,k_2,k_3}$ is also a weak PRP.

Interestingly, though, $E$ is not a strong PRP.  When given simultaneous access to both a "forward" oracle and a "backward" oracle, an adversary can distinguish between $(E_{k_1,k_2,k_3}(\cdot), D_{k_1,k_2,k_3}(\cdot))$ and $(\Pi(\cdot), \Pi^{-1}(\cdot))$, where $\Pi$ is a randomly selective permutation on the same domain.

Here is an adversary that distinguishes the two with high probability:

Query the decryption oracle with two strings of zero bits: $(a\|b) \leftarrow D(0\|0)$
Query the encryption oracle: $(c\|d) \leftarrow E(0\|a)$
Query the decryption oracle again: $(e\|f) \leftarrow D((b\oplus d)\|c)$
If $e=c\oplus a$, then return $1$, else return $0$.

Here's why this works:

By expansion, we see that $D_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_3}(R))$

$y=L \oplus F_{k_3}(R) \oplus F_{k_1}(R \oplus F_{k_2}(L\oplus F_{k_3}(R)))$
It follows that the first oracle query will result in:

$a=F_{k_2}(F_{k_3}(0))$

$b=F_{k_3}(0) \oplus F_{k_1}(a)$
By expansion, we see that $E_{k_1,k_2,k_3}(L\|R) = (x\|y)$, where:

$x=R \oplus F_{k_2}(L \oplus F_{k_1}(R))$

$y=L \oplus F_{k_1}(R) \oplus F_{k_3}(R \oplus F_{k_2}(L\oplus F_{k_1}(R)))$
It follows that the second oracle query will result in:

$c=a \oplus F_{k_2}(F_{k_1}(a))$ and

$d=F_{k_1}(a) \oplus F_{k_3}(c)$.
Note that $b$ and $d$ both contain the term $F_{k_1}(a)$.  When we compute $b\oplus d$, the terms cancel:

$b\oplus d=F_{k_3}(0) \oplus F_{k_3}(c)$
Finally, in the third oracle query, the specifically crafted $L$ and $R$ cause the following simplification:

$e=c \oplus F_{k_2}((b\oplus d) \oplus F_{k_3}(c))\\=c \oplus F_{k_2}(F_{k_3}(0))\\=c \oplus a$
The adversary finds that $e=c\oplus a$ as required, which would only be expected with low probability for a truly random permutation.

The basic idea is to set things up so that $F_{k_2}$ receives the same input in two different queries.  This causes the left oracle output to be masked with the same value, which can be detected by the adversary.

Crucially, this attack would not work without the ability to query the permutation in both directions.


Is the curve25519 algorithm a special(implementation) one of ECDH? It's the first time for me to learn about Key Exchange Protocol. And I thought that in both ECDH and DH there is a necessary step to share some public infomation(the common parameters) to each sides such as the SSH2_MSG_KEXDH_GEX_REQUEST to get g.

But in my machines, the 2 sides decided to use curve25519 to exchange the key.And When I using WireShark to capture the packages. I only find 2 steps between the c-s key exchange when using curve25519.

Diffie-Hellman Key Exchange Init(30) (with DH client e)
Diffie-Hellman Key Exchange Reply(31) (with DH server f and the signature H)

So I tried to look up the rfc,

  The key exchange procedure is similar to the ECDH method described in
     chapter 4 of [RFC5656], though with a different wire encoding used
     for public values and the final shared secret.  Public ephemeral keys
     are encoded for transmission as standard SSH strings.

So here is my question:

Is the curve25519 algorithm a special(implementation) one of ECDH? And why it need no common params for both sides to config?

Is the curve25519 algorithm a special (implementation) one of ECDH?

X25519 is a particular Diffie–Hellman function built out of the elliptic curve Curve25519, originally described in the Curve25519 paper.*  Specifically, it is a function from two 32-byte inputs to one 32-byte output with the Diffie–Hellman properties that make it useful for key agreement: $f(a, f(b, u)) = f(b, f(a, u))$.

  And why it need no common params for both sides to config?

Here's one possible way to do design a protocol that does key agreement over the internet.

Protocol designer chooses a secure DH function like X25519* that has been thoroughly vetted by the public cryptography community.
Client and server do DH handshake.

Note an adversary may be modifying the DH handshake over the wire.

Client and server authenticate DH handshake with long-term identity keys.

Here's another possible way to design a protocol that does key agreement over the internet.

Protocol designer defers question of what secure DH function to use and makes it configurable.
Client and server software implementors provide umpteen different configuration knobs with inscrutable names like ecdhk283 and accept arbitrary group parameters (like $g$ and $p$ for finite-field DH over $\mathbb Z/p\mathbb Z$, or $a$, $p$, and $p$ for elliptic-curve DH in $y^2 = x^3 + a x + b$ over $\mathbb F_p$).
Client and server operators bumble around in the dark trying to decide which acronym soup to configure their ECDH cipher suites with.
Client and server talk over the network in an attempt to negotiate a choice of cipher suite and curve.

Note an adversary may be modifying the cipher suite and curve negotiation over the wire, and may suggest curves (or finite-field DH groups) that don't even make any sense.

Client and server act on the choice of curve and do a DH handshake.

Note an adversary may be modifying the DH handshake over the wire.

Client and server authenticate DH handshake with long-term identity keys.

Which way do you think provides adversaries with more room to screw you up?

If it's not obvious, check out FREAK and logjam!

The second way was used for a long time by TLS and SSH; now modern consensus, after decades of experience, is that it is too dangerous, and even for finite-field DH, TLS 1.3 doesn't allow dynamic group negotiation.  It is a lot of work to validate curves, and much easier to implement them securely and efficiently if you don't allow arbitrary fields and parameters—and it is essentially impossible to dynamically validate finite-field DH groups securely.

* A note on terminology: These days, Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\mathbb F_p$ where $p = 2^{255} - 19$, while X25519 means a specific Diffie–Hellman function based on scalar multiplication using only $x$ coordinates on Curve25519, roughly $\operatorname{X25519}(n, u) = x([n] x^{-1}(u))$—i.e., if $u$ is the $x$ coordinate of a point $P$ on Curve25519, then $\operatorname{X25519}(n, u)$ is the $x$ coordinate of the scalar multiple $[n]P$ on Curve25519.  The Curve25519 paper was written before this terminology was settled, and uses the name ‘Curve25519’ to refer to the DH function.


GMW Multiplication AND for 2 parties I am looking into the GMW protocol's evaluation for multiplication in 2 parties. I have referred to different materials on it but I didn't exactly understand how $a_i b_j + a_j b_i$ is calculated in a 2 party setting.

As you know multiplication in GMW is given as $$(a_1\oplus a_2\oplus \cdots \oplus a_n)(b_1\oplus b_2\oplus \cdots\oplus b_n) = \bigoplus_i(a_i b_i) \bigoplus_{i<j}(a_i b_j \oplus a_j b_i).$$

Finding the first term in this equation is easy where we just multiply $a_i$ and $b_i$ share. I have trouble understanding the second term which involves Oblivious Transfer.

Let's say you are party $I$, and your friend is party $J$, secret values are $a$ and $b$. The result of the multiplication would look like:

$$
a.b = (a_i \oplus a_j) . (b_i\oplus b_j) = (a_ib_i) \oplus (a_ib_j) \oplus (a_jb_i) \oplus (a_jb_j)
$$
$I$ and $J$ already have these shares and need no communication for $a_ib_i$ or $a_jb_j$. But for $(a_ib_j)$ and $(a_jb_i)$, they do need other's input. $I$ selects a random value r and creates a table with four entries depending on the values of $I$'s and possible values of $J$ with entries $e$ like $r \oplus a_ib_j \oplus a_jb_i$.

$$
\begin{align}
a_j = 0,b_j &= 0: e = r \\
a_j = 0,b_j &= 1: e = r \oplus a_i \\
a_j = 1,b_j &= 0: e = r \oplus b_i \\
a_j = 1,b_j &= 1: e = r \oplus a_i \oplus b_i \\
\end{align}
$$

Although these entries look confusing, note that $J$ already knows $a_j$ and $b_j$ values. And any if these entries are $0$, then look at the equation $r \oplus a_ib_j \oplus a_jb_i$. This would have one or two entries evaluate to $0$. That is why the table was constructed that way. Clearly, if $I$ and $J$ engages in a 1-out-of-4 Oblivious Transfer protocol now, then $J$ can only retrieve one entry from the table. So $I$ would be having the random number $r$ and $J$ would be having the computed value xor'ed with $r$. Meaning they share the multiplication result but not the result itself.


Key-size of encryption method Is there a definied keysize to be used with the "AES_256-CBC" method in PHP, and what is the size?

Some background:

I want to store encrypted text into a PostgreSQL database. The user who posts the data has a key (stored in db) which gets appended to a generic private key hard coded in the library.

$key = $genericKey . $userKey;

The used encryption method is "AES-256-CBC" with an iv_size of 16. The IV gets prepended to the encrypted string

$return = $iv.$encrypted

This is then stored in the database.

It appears that if I produce an extremely large generic key, then store some data with $userkey1, and then decrypt it with $userkey2, the data just gets decoded. If I rerun it with a small generic key and small user key, it does not get decoded. To me, it looks as if the big key gets truncated somehow.

Could someone confirm this and tell me what the max keysize is? What is the best-practice to make sure the set key doesn't exceed the key_size* E.g.: md5($key) because this produces a "fixed" amount of characters.

update

Because apparently php has its own implementation of the AES, this is the way I implement it in my own Class:

class Crypto {

function __construct(){
  $this->iv_size = 16;
  $this->sleutel = 'somelongkey';
  $this->encryptionMethod  = 'AES-256-CBC';
}

    private function encrypt($str){
 $sleutel = $this->sleutel . $this->userKey;
 $iv = $this->generateRandomString($this->iv_size);
 $cipher = openssl_encrypt($str, $this->encryptionMethod, $sleutel, 0, $iv);
 return $iv.$cipher;
    }
    public function decrypt($data){
        $iv = substr($data, 0, $this->iv_size);
 $sleutel = $this->sleutel . $this->userKey;

        return openssl_decrypt(substr($data, $this->iv_size), $this->encryptionMethod, $sleutel, 0, $iv);

    }
}

You're simply appending the userKey to your "sleutel" (aka key) in this piece of code:

$sleutel = $this->sleutel . $this->userKey;

Problem is, doing that can result in $sleutel lengths beyond the expect 256 bits (32 bytes), or - as you are experiencing - less than the expected 256 bits (32 bytes/characters).

As @CodesInChaos correctly mentioned in his comment:

  AES-256 uses a 256 bit or 32 byte key by definition. No more, no less.

So, to fix your problem, you will have to make sure the key you are passing to your cipher function is no more and no less than 32 bytes.

To achieve that, you can simply choose to follow the usual path of encryption by taking your $sleutel and hash your key to the expected 256-bit length with (for example) MD5, like this:

$sleutel = md5($this->sleutel . $this->userKey);

or — if you prefer to choose another hash and a speedier function — you can use PHP's hash function, with it's multiple of available hashes to select from, like (for example) this:

$sleutel = hash('ripemd128', $this->sleutel . $this->userKey);

But… that's not the way I would recommend you to do it! Because, you don't want to use a weak hash like MD5 (which is known to have collisions), and you surely don't want to feed a weak hexadecimal character sequence to your cipher either, do you?

My Recommendation

Following current crypto standards, my recommendation is to use SHA256 the way it is supposed to be used in this case:

$sleutel = hash('sha256', $this->sleutel . $this->userKey, TRUE);

Notice that there's a 3rd parameter which is set to TRUE, which means $sleutel will contain 32 raw bytes (= binary characters) instead of 64 human-readable hexadecimal characters.

I'm sure that will fix your "short-key" related problems, as well as any potential "long-key" problems.


curve25519 by openSSL How can i generate ec curve25519 keys using openSSL?
When I run

openssl ecparam -name curve25519 -genkey -noout -out private.ec.key

I have this message

unknown curve name (curve25519)

Use the genpkey command:

openssl genpkey -algorithm x25519

or, for edwards25519:

openssl genpkey -algorithm ed25519

This requires a recent OpenSSL version.


Toy public/private key example open to frequency analysis? I've been looking at an online Public Key Encryption Example (summarized below). It seems to me that choosing cyphertext = plaintext^(key) mod n would produce the same ciphertext letter for a particular plaintext letter, leading to easy frequency analysis of the output. Would there be a way to modify the example so that this isn't the case? Is there something I'm missing in the results? Thanks!

Summary of method:

Pick a pair of large prime numbers at random (e.g., 3, 11 (not large in this case))
Compute product: n = p × q = 3 × 11 = 33
Compute the value of Euler's totient function of n: φ(n): φ(n) = (p-1) × (q-1) = 2 × 10 = 20
Pick any number less than and relatively prime to φ(n) (e.g., 7)
Compute the matching private or decryption key d, as the inverse of e modulus φ(n). d = inv of e mod φ(n) = inv(7) mod 20 = 3
Encrypt: cyphertext = plaintext^(key) mod n

The site also misrepresents RSA encryption. If you are using textbook RSA (i.e. this scheme, with no padding), you don't independently encrypt each letter. Rather, you take the entire message, treat it as a number, and encrypt that.

This doesn't work if your primes are 3 and 11, but if they're each, say, 8 bytes long, then you could encrypt a 16-byte message using textbook RSA by treating the whole message as a single number. The only time you run the encryption operation multiple times on different parts of the message is if the message is longer than the RSA modulus, in which case you need a chaining mode.

RSA has no real chaining modes (no one's bothered coming up with one), but a real block is fairly big anyway. The site broke the message into letters and encrypted each separately (which is the horrible no-good ECB mode) to make the math easier, but that's not even how textbook RSA is used.

There are all sorts of attacks on textbook RSA; frequency analysis isn't really one of them.