Is it possible to have perfectly secure public-key cryptography with oracles? It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme.  That’s because the adversary can search through all possible private keys.
But I’m wondering if it can be made possible using oracles.  My question is, do there exist sets of natural numbers $A$ and $B$ such that if Alice has access to an oracle for $A$ and Bob has access to an oracle for $B$, then these oracles can be used as private keys for a perfectly secure public-key encryption scheme?
I’m thinking that perfect security may be possible in this setting since there are uncountably many sets for the adversary to search through.

What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time for the key. The issue is, this basically equates to having a key of infinite size which is just as impossible to use for encryption, since the time to encrypt increases as well - just not as fast as the time to break it.
However, if we assume your oracles $A$ and $B$ operate in a finite amount of time (somehow you manage to encrypt using an infinitely large key) you would have a perfectly secure scheme, as you describe.


Does knowledge of equal exponents decrease security? Say I have a group $G$ with two different generators $g_1$ and $g_2$, where the discrete log from one to another is unknown.
Also, there are two public commitments $g_1^{r}$ and $g_2^{r}$, where it is publicly known that they are raised to the same $r$ (but unknown which $r$).

Does the latter piece of information compromise security in any way?

This answer aims to show that the security does not decrease.

Let me explain it as a game. $\mathcal{D}$ is the challenger who asks $\mathcal{A}$ to solve a 2-hint DL problem.

$\mathcal{D}(\mathcal{G})$ samples $r$ and sends $(g_1,g_2,g_1^r,g_2^r)$ to $\mathcal{A}$.
$\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ is supposed to answer $r$ correctly with a non-neglibigle possibility.

First, let me formalize "the discrete log from one to another is unknown".

There is a group $\mathcal{G}$ and a public generator $g_1$. $\mathcal{D}$ chooses $g_2$ as follows:

Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$, where $\mathsf{ord}(\cdot)$ means the order of a group.
Computes $g_2=(g_1)^s$.

Then, let me introduce the basic DL game, which consists of another challenger $\mathcal{D}'$ and another adversary $\mathcal{A}'$.

$\mathcal{D}'(\mathcal{G})$ samples $r$ and sends $(g_1,g_1^r)$ to $\mathcal{A}'$.
$\mathcal{A}'(g_1,g_1^r)$ is supposed to answer $r$ correctly with a non-negligible possibility.

In groups where DL assumptions are believed to hold, a probabilistic polynomial-time $\mathcal{A}'$ cannot answer with a non-negligible possibility of getting it correct.

Now, we say $\mathcal{A}'$ is winning if it can output the correct answer with a non-negligible possibility.

So, we know there is no $\mathcal{A}'$ winning in $(\mathcal{D}',\mathcal{A}')$ game.

Now, if there is a PPT adversary $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ that can play $(\mathcal{D},\mathcal{A})$ game with a non-negligible possibility of winning.

Then, there is a winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

We can construct a winning $\mathcal{A}'(g_1,g_1^r)$ from this winning $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$ as follows:

Samples $s\in\{0,1,...,\mathsf{ord}(\mathcal{G})\}$.
Computes $g_2=g_1^s$.
Computes $g_2^r=(g_1^r)^s$.
Outputs the answer of $\mathcal{A}(g_1,g_2,g_1^r,g_2^r)$.

Then, if $\mathcal{A}$ is winning, $\mathcal{A}'$ is also winning.
This contradicts the fact that there is not winning $\mathcal{A}'$.

So, such $\mathcal{A}$ does not exist.
In other words, there is no PPT adversary that can break your construction.

I think this answer also shows that it cannot be used to reduce the number of rounds for attacking.


Given a sha-512 hash of a value picked at random from the $2^{128}$ key space, how hard would it be to recover the original value? More specifically is it reasonable to assume that someone with the resources of a state actor can feasibly compute a rainbow table of all the sha-512 hashes of values within the $2^{128}$ key space?

Am I correct in assuming that the most efficient attack in this case would be to compute a rainbow table, given that sha-512 doesn't have any known vulnerabilities?

The answer, as SEJPM pointed out, is "no, a work effort one the order of $2^{128}$ SHA-512 computations would be infeasible, even by a three letter agency".

However, the other question was "would constructing a rainbow table be the most efficient attack?"  The answer is "it depends".

If the attacker was interested in just one SHA-512 hash, and had no expectation of ever needing to attack another hash (or, at least, one with the same salt; for example, known bits that are also included along with the 128 unknown ones), then constructing a rainbow table is wasted effort.  The takes a constant factor more work than simple brute force (just trying all possible 128 bit values, and hashing them), and has a probability of failure (if none of the chains happens to hit the target value, the rainbow table lookup will fail).

On the other hand, if the attacker expected to have a series of SHA-512 hashes, all of the 128 bit keys (and all the other parts of the hash the same known values), then constructing a rainbow table makes a lot of sense; yes, constructing it takes a long time (infeasibly long in this case), however once you've done it, looking things up in it doesn't take that long at all.


Is this method of encryption theoretically unbreakable? I implemented a Stream Cipher using Cryptographically Secure Random Numbers for the key values. The key stream was as long as the plaintext stream. This key data set won't be reused. Have I met all the requirements for a truly theoretically unbreakable encryption process?

I know programmers without the math or general crypto background are strongly encouraged NOT to avoid AES, Two Fish, etc. in favor of their own, amateur approaches. Yet I can't see where I've missed a requirement. I look forward to those with domain expertise to show me if I've failed to understand something here. Thank you.

Ignoring concerns about missing integrity and authentication verification, here is why:

Suppose that the key you used to generate your keystream from your CSPRNG is shorter than your plaintext; if it isn't, you may as well use the one-time pad. Then I know from the pigeonhole principle that there will be some (many, actually) keystreams that will never be generated. Furthermore, I can enumerate these keystreams by simply going through every key (your plaintext has finite length, so there are only finitely many keys I have to check).

Therefore given any ciphertext, I can infer that there are many plaintexts that can never encrypt to this ciphertext, regardless of the key you picked. I have derived knowledge* about the plaintext from the ciphertext alone, therefore your encryption scheme is not information-theoretically secure (what you call "theoretically unbreakable").

Did I mention I was an entity with unbounded (infinite) computational power? If you want truly unbreakable encryption, this is effectively equivalent to your ciphertext conveying zero information about the corresponding plaintext without knowledge of the key. It's a very high bar to set, and one that is virtually useless in the real world, which is why we are perfectly okay with AES and the like.

You cannot cheat information theory by stretching your keys through deterministic processes. You cannot cheat information theory through elaborate encryption schemes involving multiple encryption passes with different keys and liberal sprinkling of hash functions and CSPRNG's - an unbounded adversary will see right through it, unraveling whatever layers of convoluted encryption you have going on, until it all eventually boils down to how much information your ciphertext has, which is itself fundamentally lower-bounded by how long your key is.

Information is given, not created, and your cipher's security is measured in terms of how much computation it takes to extract information out of the ciphertext without the key. If it carries no information, there is nothing to be extracted, and you have information-theoretical security.

* the length of the plaintext is not generally considered "knowledge" as it is more metadata than anything else; it cannot really be relied on as you can always pad your plaintext to a fixed length and communicate through a prearranged dictionary of fixed-length symbols.


Factoring large $N$ given oracle to find square roots modulo $N$ When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either
  zero or four square roots. A quarter of the points have four square roots; the rest have no square
  root. The four square roots of $x\in\mathbb Z_N^\ast$ will look like $\pm a$, $\pm b$. (Of course, $-a$ means $N-a$ since
  we’re working modulo $N$.) Suppose that I give you an efficient deterministic algorithm $S$ that, on
  input $x$ that has square roots, finds some square root of $x$. (If $x$ does not have a square root, it returns
  $\bot$.)

  Use $S$ to make an efficient probabilistic algorithm $F$ that factors $N$. [Hint: If you can find two
  square roots of a number, call them $a$ and $b$, which are not of the form $a \equiv \pm b \pmod N$, then you
  can factor $N$. Show how.] Note: You only get to call $S$ as a black-box, so you don’t know a priori
  which of the square roots it will find.

I am having trouble understanding this homework question, could someone please guide me or give a hint on how to proceed? What I have come up with till now is,
first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a \equiv \pm b \pmod N$. Repeat this for all points.
I am still stuck on how I use this to factor $N$ though.

What I have come up with till now is, first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a\equiv\pm b\pmod N$. Repeat this for all points.

This has (at least) two problems:

For a fixed input, $S$ will always return the same square root.
You can not "repeat this for all points" since there are $\mathcal O(N)$ of them, hence your algorithm $F$ will not be (probabilistic) polynomial-time.

As to how we can fix this: Since $S$ will only give us one square root, we somehow have to obtain the other one (modulo negation) ourselves. A good (efficient) way to do this is to simply construct the number given to $S$ in a way that we already know one of its square roots, and hope that $S$ will give us the other one. Here's an algorithm:

Choose $x\in\mathbb Z_N^\ast$ at random.
Pass its square $x^2$ to $S$; call the result $y$.
If $x\equiv\pm y\pmod N$, we were unlucky: Start over with a new $x$.
At this point, we know from
$$ x^2\equiv y^2\pmod N $$
that
$$ x^2-y^2=(x+y)(x-y) $$
is a non-zero multiple of $N$ while neither $x+y$ nor $x-y$ alone is, hence we can recover a factor of $N$ by computing
$$ \gcd(x+y,N) \text. $$

Now we would like to prove that this algorithm is (probabilistically) efficient. Our choice of $x$ is equivalent to first choosing some square $r$ at random and then choosing $x$ as one of $r$'s square roots also at random. The oracle $S$ is deterministic, hence will always return the same square root $y$ of $r$. Therefore we have a probability of $\frac12$ that our choice of $x$ is not in the same "class" as $y$, i.e. $x\not\equiv\pm y\pmod N$, thus yielding a factorization. Clearly one iteration of this algorithm runs in polynomial time, and the expected number of iterations to succeed is only $1+\frac12+\frac14+\dots=2$. Therefore $F$ efficiently factors $N$.


Rate my idea: is that a stronger GPG-like algorithm? I came up with a simple idea but I don't know if it is really secure or not. I know that you shouldn't create any algorithm on your own. I'm just curious, that's all.

Algorithm explanation:

First of all, Alice and Bob agree on a common secret password, lets say P1 (this should be done using a secure channel, like meeting in real life just a single time to exchange the password which is more practical than exchanging one time pads)
Alice chooses one secret passwords, lets say A1, which she keeps secret, Bob does the same, B1
Alice hashes her password and Bob does the same, so we have:

HA1 = hash(A1)    Alice's hashed password

HB1 = hash(B1)    Bob's hashed password
Alice sends her hashed password (HA1) to Bob, even on a insecure channel, because it's hashed. Bob does the same: he sends her his hash HB1
Let's say Alice wants to encrypt something. She would to the following:

Take P1 (the common password) and hash it so HP1 = hash(P1)
Take Bob's hashed password HB1
Encrypt the message using this long password (just a concatenated string) =  (HB1 + HP1)

When Bob's gets the message, he has to:

Insert two different passwords: his private password + the common shared password
The algorithm transforms those two words in their hashes and then tries to decrypt the message

In my opinion, this would be great because:

If Alice encrypts a message with Bob's hashed password, even if someone knows the shared password, only Bob can decrypt the message
If someone finds Alice's or Bob's private password, he can't still encrypt/decrypt anything because he doesn't know the common one
Only Alice knows the common password, so Bob's is sure that the cypher is surely made by Alice (no MITM attacks, fake identity like in GPG)
You have to share a common word just once. This solves the key distribution problem of the OTP method

What do you guys think?

Your idea is no stronger than simply having a common shared password $P_1$ from which the symmetric encryption key is derived.

  If Alice encrypts a message with Bob's hashed password, even if someone knows the shared password, only Bob can decrypt the message

You assumed the hash of Bob's password – $H(B_1)$ – is public, so if Eve knows both it and the common password $P_1$ she can calculate $H(B_1)||H(P_1)$. She doesn't need to know $B_1$ itself.

A program can be written to require the password $B_1$, but Eve could write her own program that accepts either the hashes or the passwords.

I.e. unless you assume $H(A_1)$ and $H(B_1)$ are private, they do nothing. If you do assume that, they effectively become part of the shared secret.

  Only Alice knows the common password, so Bob's is sure that the cypher is surely made by Alice (no MITM attacks, fake identity like in GPG)

Yes, but the problem of sharing the common password $P_1$ remains. If you can securely exchange that password, you can likewise securely exchange GPG keys or any other encryption keys.


Difference between Hardware implemented algorithm and software implemented one? In the articles about cryptography I see the words Hardware implemented and Software implemented. I'm curious to know what is the difference between them?

In the other words, even in the computer when I write a program to do a crypto algorithm, I finally run it on CPU. So why I couldn't call it hardware implemented?

What is the difference between a simple processor and a crypto processor(coprocessor?)?

There are typically four different settings where you want to run your crypto.

The Central Processing Unit (CPU). This may be a classic desktop or laptop CPU or the one of your embedded device. Its characteristic is that it usually has rather few computation cores ( < 20), but it can use the ones it has very fast and can execute arbitrary instructions (in mostly arbitrary order) from its assembler language. Crypto algorithms that run on CPUs are most likely software-implemented because the algorithms (i.e. the instructions) are merely information given to the CPU for execution. CPUs are best at running complex, linear algorithms.
The Graphics Processing Unit (GPU). This may be your desktops or laptops graphics processor or it may be your supercomputing computation accelerator. Its characteristic is the high number of cores, the low speed of each core and the limited instruction set. GPUs are made to run simple algorithms massively parallel.  Much like CPUs they accept their algorithms as pieces of information, so it's the software that implements the algorithm.
The Field Programmable Gate Array (FPGA). The FPGA is typically found in small embedded devices and is running specialized algorithms. Its hardware can be configured post shipping, at the expense of lower speeds of operation than with ASICs. With FPGAs you change the hardware layout of your integrated circuit to run your algorithm. Hence algorithms run by FPGAs are said to be hardware implemented, because in its current state, the hardware can run only this exact algorithm, nothing else.
The Application Specific Integrated Circuit (ASIC). This is an integrated circuit that is manufactured to run exactly one algorithm, nothing else. ASICs provide high speed for this algorithm usually and are used when speed matters. An example application are Hardware Security Modules (HSMs) which commonly use ASICs to accelerate the execution of cryptographic operations (like AES encryption). Crypto processors commonly are simple processors with additional crypto-specific ASICs.

As for the security of each platform, the tendency is that if you go down this list, the security will increase. CPUs are usually occupied by many different processes (including the OS), allowing somewhat "easy" side-channel attacks, GPUs are usually not used for crypto (besides hash-cracking), FPGAs should provide more security than CPUs if done right because there less "noise" of other operations on the chip and ASICs have the same benefit, but a bit more extreme.

The speed increases similarly if you go down the list. CPUs must be capable to do many different things and so can't be too much optimized in one direction, some goes for GPUs although they have much more computation power if needed. FPGAs are faster because you can more optimizations and ASICs are king because you can do whatever you want with them and optimize the heck out of them.

The price has a similar order. CPUs are easy to obtain, cheap to program and you can get your program running quickly. GPUs are also quite easy to obtain, a bit more expensive to effectively program and can be get to run your code somewhat fast. FPGAs are more expensive by theirselves and require you to design your algorithm using the hardware language of your FPGA, requiring a lot of time and expertise and thus money. ASICs need to be planned before they are built, have long design cycles, but once you've got the design, you can manufacture them "easily" and for a "low price".

The last two points could already be observed in natura when looking at the development of Bitcoin mining. It started with CPUs on PCs, went on with GPUs, then with FPGAs and is now dominated by ASICs. Note that Bitcoin mining is equivalent to "doing many double-SHA-256 hashes".


Definition of soundness (a different approach) in "Witness Indistinguishable and Witness Hiding Protocols" In any other context where I encountered the concept of soundness it was very simple: if the input does not belong to the language then the protocol fails or fails with great probability.
But in the paper Witness Indistinguishable and Witness Hiding Protocols there is an interaction between a prover $P$ (with a set of valid witnesses $w(x)$), a verifier $V$ and an input $x$ and the definition of soundness is:
$\exists M\ \forall P'\ \forall x\ \forall w'$,
$$ P[V_{P'(x, w')}(x) accepts] < P[M(x, w'; P') \in w(x)] + negligible $$
Where the probability is over the random tapes of $V$, $P'$ and $M$. $M$ uses $P'$ as a blackbox.
I just can not grasp this, can someone explain it to me?

The soundness definition that you are familiar with is the normal soundness definition of proof systems. The soundness definition in this paper is a definition of soundness for "proofs of knowledge", i.e., the goal of the prover is not only to convince the verifier that the statement is true but also that it knows a witness. This can be a much stronger requirement.
Now, there are two main aspects in which this differs to the notion you're familiar with. The first aspect is related to this question: How can we formalize that the prover "knows" a witness? The short answer in informal words is: if there's a witness in the prover, then there must be some way to get it out of the prover. This extraction process is the job of the knowledge extractor $M$ in the definition you found. The knowledge extractor $M$ is given black-box access to $P$ in order to extract the witness. I could expand on this concept but I believe there are a lot of very good resources with different levels of rigor that elaborate specifically on this point [1,2,3,4] because this is often a source of confusion for newcomers.
The second difference is that this definition relates the accepting probability of $P$ with the probability that $M$ extracts. In other words, whenever $P$ convinces the verifier, then $M$ should be able to extract a witness (with a negligible error). An alternative (but flawed) definition which is closer to the definition you're aware of would require that if $P$ convinces with non-negligible probability, then $M$ can extract successfully.* Variants of this definition have indeed been used early but they're too weak for what we typically need, as Bellare and Goldreich [4] explain in an entire paper that I very much recommend for a deeper understanding. In Appendix A, they explain why the definition you found is better than the flawed definition but still not optimal.
A final remark is that the paper you've found is already pretty old. These were the first days of zero-knowledge when the community was still in the process of finding good definitions for zero-knowledge proof systems, which can be nicely seen from the paper by Bellare and Goldreich [4]. The definitions in newer works may be clearer.
*Note that the condition "if the statement is in the language" would obviously be too weak: just because the statement is in the language does not mean that some $P$ (which could be just a dummy machine outputting only zeros) knows a witness.


Is a changing public truecrypt container secure? I have a Truecrypt container which I want to synchronise between computers (i.e. different people, that I want to share the data with).

If I used Dropbox for synchronisation and someone downloaded all the different versions of a publicly accessible Truecrypt container over time, whenever it gets changed, is it then easier for them to find the password than if they just had one version?

The truecrypt folks seem to have done a pretty good job with their crypto, so I'm going to say the answer is no, it would not get easier for them to find the password for any practical sense of the word "easier". They even have a write up on Sharing over Network which seems pertinent.

Typically in a cryptanalytical attack, however, the more information the analyst has, the easier their job. So I guess in that sense, theoretically the answer would be yes, their job is easier since they have extra information. But I personally wouldn't be worried about it as to gain any real-world advantage the analyst would probably need petabytes (if not more) of information for any attack to be practical. By the time they gather that much information, they probably could have guessed your password.


are anonymous credentials a type of zero knowledge proof? Are anonymous credentials (such as IBM Idemix) a type of zero knowledge proofs (ZKP)? if so what type of ZKP are they?

The papers such “Security without identification: transaction systems to make big brother obsolete” don not reference ZKP.

My understanding is they both refer to similar topics.

I would rather call them a type of blind signatures. Since signatures stem from non interactive ZKP you can say that they are related.


Why MACs are so important despite digital signatures doing everything a MAC can do and more When an entity A wants to send a message to entity B, he can attach a MAC to the message. Entity B on receiving the message can use the pre-shared key to compute the same MAC and confirm if the message is untampered with.

This approach protects A and B from an external attacker who might want to mess with the message. However, it does not protect A from B or B from A. For example, A can craft a message and claim that it came from B since B is the only entity that shares this particular key with A.

Digital signatures eliminate this problem, since the MAC is replaced with a hash which is encrypted with the senders private key. Usage of the private key means that A and B cannot deny or forge messages between each other.

Which brings me to my question. Why do MACs continue to be so relevant when they are susceptible to the kind of attack described above? Under what circumstances would one prefer a MAC to a digital signature?

Note that I have been made aware that there is a question on here which seeks for a comparison between MACs and digital signatures. That question is different from mine since I am looking for concrete cases where MAC would be used instead of digital signatures. Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored?

There are many advantages of MAC's over signatures.

For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow).

Instead you can simply agree an authentication key (or a key for an authenticated cipher). This allows much more efficient operations both regarding

the speed of calculation of creation and verification of the authentication tag / signature and
with regards to the size of the authentication tag / signature.

For many protocols the problem that the receiver can also spoof authentication tags is not a (huge) issue. It could be a bigger issue for protocols where the two participants use the same authentication key for both sending / signing messages and receiving / verification of messages. TLS, to name just one protocol, uses separate keys.


Generate Elliptic Curve Private Key from User Passphrase? I'd like to generate a private elliptic curve key from user input like pass phrase. Is the best way to do this with a key derivation function like PBKDF2? Is there a better way?

Edit (based upon @poncho's questions)

To be specific, this is for a Bitcoin ECC private key. It seems to me that if a user picks a passphrase like puppies, it makes sense to try to use PBKDF2, Bcrypt, or Scrypt to increase entropy.

Something like...

eccPrivateKey = pbkdf2(HMAC−SHA, "puppies", randomSalt, 10000, 256)

right? Should any inputs or outputs be hashed? So, is it acceptable (security perspective) for the output of the pbkdf2 to be the private key?

@poncho, hopefully my use case implicitly answers your questions regarding the brute forcing. i.e. don't care how long it takes to generate as long as it's under a few seconds. Care very much about dictionary and precomputational attacks.

Using PBKDF2/Bcrypt/Scrypt might be the least-bad way, but that doesn't mean it's a good way.  If your passphrase is puppies, it doesn't matter whether you use PBKDF2, Bcrypt, or Scrypt: you've got serious problems.  If someone tries to crack your key, you're going to be toast: your key will be cracked within minutes.

Bottom line: this sounds like a bad idea to me, if there's any possibility at all that the passphrase might be weak (which, in practice, there will be).
I would not use this to protect my money.

Instead, you should be generating a truly random or cryptographically-strong random number for the private key, then storing the private key somewhere safe.  If you want to store the private key in encrypted form, you can derive a symmetric encryption key $K$ from a passphrase and store the private key encrypted under $K$ (though please understand that this will likely be vulnerable if someone manages to steal a copy of the encrypted private key).


Are DSA and ECDSA provably secure assuming DL security? Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?

(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)

Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in  particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.

There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.

So, in short, the answer would be no, not under reasonable assumptions.

(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)

[B] Brown. Generic Groups, Collision Resistance and ECDSA.

[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.

[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.

[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.


How to prove identity in this peculiar case Lets say Alice wrote a book under the name Alyssa. The only other person who has read the book is Bob. Bob then publishes the same book but under the name Bobby. Is there a way for Alice to prove that the book was originally published under the name Alyssa?

I think it is the "trust problem" which requires web of trust and therefore is impossible to solve strictly. However it can be in essence solved in a way. Alice first publishes a summary of the book under the name of Alyssa and spreads the word as much as possible. The summary specifies a timeframe under which any identity X can claim to be writing a book with the matching summary. If X exists then Alyssa continues to publicly engage with him/her until sufficient difference arises in the actual specifics of the book. After this period Alice shares her book with Bob. Then if Bob publishes the same book but under the name Bobby the trust would be weak since Bobby didn't spoke up when Alyssa published the summary. The emphasized parts are the weak aspects of this mechanism but can be enough for certain trust threshold.


Iterated AES encryption under a fixed key Is it right that repeated AES encryption under the same key will eventually lead back to the original plaintext?

The reasoning is that AES acts like a reversible permutation of the blocks, the composition of several permutations is yet another permutation (closure), and because the number of permutations is finite, it must eventually get back to where it started.

If I write $E \circ E = E^2$ to mean "double AES" and $E^N$ to mean $N$ applications of AES (under the same key), then I can state the hypothesis symbolically as $E^N = I$ for some $N$, where $I$ is the identity permutation.

If this is correct, then it seems that $N-1$ applications of AES behaves identically to the inverse/decryption function, $D$, because

$$E^N = E \circ E^{N-1} = E \circ D = I$$

Is this statement correct?

Under a fixed key, $E_K$ is a permutation in the symmetric group of permutations on $2^{128}$ elements. Thus its order divides $(2^{128})!$.

If AES is modelled as a random permutation, for a randomly chosen fixed key, the order $N$ of $E_K$ is likely to be near $2^{127}$ as explained in the comment under the question, and indeed $E_K^{N-1}(x)=E_K^{-1}(x)$ for all $x\{0,1\}^{128}$.


Reducing the XOR's in Implementation Cost Suppose that we want to implement the following equations in binary finite field.

$$
\begin{array}{l}\tag{1}
y_{{1}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}}\oplus x_{{8}},\\
y_{{2}}=x_{{1}}\oplus x_{{2}}\oplus x_{{6}}\oplus x_{{8}},\\
y_{{3}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}},\\
y_{{4}}=x_{{2}}\oplus x_{{8}}.
\end{array}
$$

My question: Is it possible to implement  the given equations in $(1)$ with five $\operatorname{XOR}$?

My try results in six $\operatorname{XOR}$ for implementation cost. For example;

$$
\begin{array}{l}\tag{2}
u_1=x_1\oplus x_2,\\
u_2=x_2\oplus x_8=y_4\\
u_3=x_6\oplus x_8,\\
u_4=u_1\oplus x_7=y_3\\
u_5=u_4\oplus x_8=y_1\\
u_6=u_1\oplus u_3=y_2\\
\end{array}
$$

Thanks for any suggestions.

Edit: As Dear fgrieu said with greedy thoughts, the answer is as follows:
$$
\begin{array}{l}\tag{3}
u_1=x_2\oplus x_8=y_4\\
u_2=x_1\oplus u_1\\
u_3=u_2\oplus x_7=y_1 \\
u_4=u_2\oplus x_6=y_2\\
u_5=u_3\oplus x_8=y_3
\end{array}
$$

Thanks to greedy thoughts.

Yes. I have a solution with 5 $\oplus$.

Hint 1: That would not work with $*$ (ordinary multiplication, or even multiplication in $\Bbb Z^*_p$) where there is $\oplus$, because we must use a property of $\oplus$ that $*$ does not have.

Hint 2: The right path is greedy.

Hint 3: It's key to compute $y_3$ late, with just one extra step.


Can adding nonces make challenge response authentications weaker? In a custom protocol we want to replace an aged tiger32 based challenge response authentication. I suggested that we use something existing, so threw HMAC into the room. As per wikipedia it works as:

$\textit{HMAC}(K, m) = H \left( (K \oplus opad) | H((K \oplus ipad) | m)\right) $

where $m$ would be the nonce. Now The Architect™ suggested "Let us put a few more nonces in there, more randomness does not hurt." and came up with this:

$\textit{HMAC}(K, m_{0..4}) =
H \left(m_0 | (K \oplus opad) | m_1 | H(m_2|(K \oplus ipad) | m_3)|m_4\right) $

Although I could not see anything immediately wrong with it, my reply was "We are no cryptographic experts, let us stay with something that has proven to be good in real world applications already."

So we are kind of still arguing and now need input of cryptographic experts. The two main questions here that arise are (Always under the assumption that key, nonce and hash are sufficiently good):

In this specific instance, will adding those nonces hurt security? That is, will it make authenticating without knowing $K$ any easier, or will it make recovering $K$ from intercepted traffic any easier?
For the general case, if possible, will in similar situations ("hashing stuff for authentication") adding nonces always make things better, or are there situations to be aware of were adding them could make things worse?

This is vulnerable to a length extension attack. Given a valid nonce/MAC, the nonce can be extended to forge a new valid nonce/MAC value. This is because $m_4$ is appended to the end inside the outer hash.

How this affects you will depend on how you validate your nonce. But in general, this is not a secure construction.

There's probably more things wrong with it, but this was the one that stood out the most to me.

  Now The Architect™ suggested "Let us put a few more nonces in there, more randomness does not hurt."

Don't fall for this. Saying doing X doesn't hurt is NOT a valid reason do it. You'll end up buying yourself nothing, and possibly decreasing security. And it's also not a standard algorithm, so it won't exist in any programming libraries.


How does one verify a GPG/PGP key revocation? After revoking a key and sending the revocation to MIT's keyserver, I noticed that the key is listed as such:

pub  2048R/XXXXXXXX 2011-01-01 *** KEY REVOKED *** [not verified]

Who is responsible for the 'verification of the revocation'? Does the owner of the key do this verification?  If so, how is this accomplished? Do other people sign the revocation and at a certain point it becomes verified?

How does one verify a key revocation?

As Jon Callas already stated: you simply don’t.

In case a different wording helps, here’s a quote related to the exact same question… https://lists.gnupg.org/pipermail/gnupg-users/2014-February/049100.html

  …

    I revoked my key and on the public key server it says: "* KEY REVOKED * [not verified]" Why does it say that revocation is not verified?

  That probably refers to the point that the keyservers don't do crypto checks. It means: There is a packet which looks like a key revocation but it could be forged. If an OpenPGP application  downloads the key from the server then it does a signature check.

  …


Is this a prg: G'(x) = G(x) ⊕ (x || 0^(l(|x|)-|x|)) This is not homework, but a question from an exam.

Let $G(x)$ be a PRG with expansion parameter $\ell(n)$.

$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

My intuition is that it is a PRG, first, $n$ bits are just XOR between $x$ which is random, with $G(x)$ which is a PRG, and the rest of the bits are untouched.

I tried to formally prove this to no avail, so I tried a simpler exercise:

$$G'(x) = G(x) \oplus (x_1 \mathbin\| 0^{\ell(|x|)-1})$$ where $x_1$ is the first bit of $x$.

If I can show this is a PRG, it will be easy with induction on the number of bits we take from x to show the original $G'$ is a PRG.

$G'(x)$ is not a PRG.

I am posting a formalized version of @fgrieu 's example.

Given $H(x)$ PRG we build $G(x)$:

$$G(x) = x_1\mathbin\|H(x_2\mathbin\|\ldots\mathbin\|x_n)$$

$G(x)$ is a PRG:

The expansion requirement is easily shown.

We show that for all $D$ there exists a negligible function $neg$ such that:
$$|\Pr(D(r)=1) - \Pr(D(G(x))=1)| < neg(n)$$

Let $D'$ be an identifier for $G(x)$, we shall build an identifier $D$ for $H(x)$:

$D(w):$

Generate a random bit $b$
Run $D'$ on $b\mathbin\|w$
Return 1 if and only if $D'$ returned 1.

Analysis:

Let $r$ be a uniformly drawn binary string:

$$\Pr(D(r)=1)=\Pr(D'(b\mathbin\|r)=1) = \Pr(D'(r')=1)$$
Where r' is also a uniformly drawn binary string.

$$\Pr(D(H(x))=1)=\Pr(D'(b\mathbin\| H(x))=1)=\Pr(D'(G(b\mathbin\| x))=1)=\Pr(D'(G(x'))=1)$$

Since we assume $H(x)$ is a PRG, there exists a negligible function such that:

$$|\Pr(D(r)=1) - \Pr(D(H(x))=1)| < neg(n)$$
Subtitute the above:
$$|\Pr(D'(r')=1) - \Pr(D'(G(x'))=1)| < neg(n)$$

This proves that $G(x)$ is a PRG.

Now we show $G'(x)$ as defined below is not a PRG:
$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

Substitute our $G(x)$:
$$G'(x) = (x_1 \mathbin\| H(x)) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$
$$G'(x)=0||(H(x)\oplus(x_2\mathbin\| x_3\mathbin\| \ldots\mathbin\|x_n\mathbin\| 0^{\ell(|x|)-|x|})$$

As shown $G'(x)$ will always start with a 0, so we can build an identifier $T$ that will output 1 if the first bit is 0.

$$|\Pr(T(r)=1) - \Pr(T(G'(x))=1)| = |1/2 - 1| = 1/2$$ which is not negligible, hence $G'(x)$ is not a PRG.


Given A, B, G, H prove the I know x s.t. $A=xG$ and $B=xH$ Given A, B, G, H .How would I prove that I know x such that
$A=xG$ and $B=xH$

There is a standard $\Sigma$-protocol for proving knowledge of a witness showing that $(G,H,A,B)$ is a DDH-tuple, assuming a group of prime order $p$:

The prover picks a random exponent $r \in \mathbb{Z}_p$ and sends $(R,S) = (rG, rH)$.
The verifier sends a random challenge $e$ from $\mathbb{Z}_p$.
The prover computes and send $d = e\cdot x + r$.
The verifier accepts the proof if and only if $eA+R = dG$ and $eB+S=dH$.

Since you seem to ask these questions for the purpose of learning, I'd suggest that you try to prove yourself the security of this protocol (that is, soundness, and honest-verifier zero-knowledge). You can take inspiration from the security analysis I gave for a similar protocol in this answer, that deals with the Schnorr protocol (about which you asked in another question).


Searching for a zero knowledge proofs I don't exactly know what I'm searching for but the scenario is at follows. Alice and Bob want to get married. According to the law, they have to make a set of medical investigations. Bob must show his medical results to Alice and Alice must show Bob her medical results. After that, they both need to go to a doctor that has to certify that they showed each other their medical results but the doctor isn't allowed to view the results of investigations from either Bob nor Alice. Can this task be resolved by a zero knowledge proof? If so, can you give me some references please? Thank you!

How about:

Alice and Bob both have to answer a series of yes-or-no questions by the doctor. Alice and Bob have to answer these questions separately.

Before they answer any question they agree that "1" is "yes" and "0" is "no", but the doctor doesn't know which is which. The doctor also has shuffled the questions so that Alice and Bob can't make some sort of predefined pattern for their answers.

One of the questions could i.e. be: "Does Bob have diabetes?".

Alice and Bob both know the correct answer to this (let's say that Bob doesn't have diabetes) and they both answer to this question with "0".

The doctor is not allowed to ask them questions that he knows the answer to, i.e. "Does Alice have blue eyes?"

The doctor now has both of their answers and compares them. If they both have the same answer to each question (assuming they answered truthfully and didn't make any mistakes) the doctor can be sure that they told each other their results.

The zero-knowledge part of this is, that the doctor still doesn't know anything about their medical results.


About converting Leveled FHE to Pure FHE and the Circular Security Assumption As it was pointed out in one answer of this question, the BGV paper has a footnote that says

  One can obtain a "pure" FHE scheme (with a constant-size public key) from these leveled FHE schemes by assuming "circular security", namely that it is "safe" to encrypt the leveled FHE secret key under its own public key.

However, I do not understand how the circular security assumption is related to this transformation from a leveled FHE to a pure FHE.

In my understanding, any leveled FHE can be turned in a pure FHE by setting the acceptable multiplicative depth, that is, the parameter $L$, to a value large enough to evaluate homomorphically the decryption circuit plus one operation and then apply the Gentry's blueprint, namely, refresh the ciphertexts after any operation by running the decryption function homomorphically.

So, can anyone explain what authors of BGV mean with that footnote or show what is wrong with my understanding ?

You need the "circular security" assumption to obtain an FHE scheme with a single public-private key pair, as you want to homomorphically decrypt using the private key $k_0$ (whose corresponding public key was used for encrypting the data) that is encrypted using a public key $k_1$.

If the public key $k_1$ used for encrypting the private key $k_0$ is the "partner" of the private key $k_0$ in the public-private key pair, then you can repeatedly use the encryption of $k_0$ under $k_1$ to get your pure FHE-scheme via Gentry's bootstrapping, but to prove security you need the "circular security" assumption (cycle length 1).

Otherwise there is some other private key $k_2$ belonging to the public key $k_1$, so that in your second application of Gentry's bootstrapping you now need an encryption of the private key $k_2$ under some public key $k_3$. You can define in this way a sequence of keys $(k_i)_{i\in\mathbb N_0}$ (where for odd $i$ the keys $k_i$ are public keys and for even $i$ private keys, and for $i$ odd the key $k_{i+i}$ is the matching private key for the public key $k_i$).

If all the keys $k_i$ are different, then you don't need the "circular security" assumption, but your system needs infinitely many different public keys as well as infinitely many different encryptions of private keys, which is not really satisfying. If you have some repetition, then you can choose $k_i = k_{i+2\cdot n}$ for some $n\in\mathbb N$, but for proving security you need the "circular security" assumption (cycle length n).


In the Paillier cryptosystem, is there a method to judge whether an encrypted number is less than 0 (without the private key) Or, is there a cryptosystem that is both order-perserving and additive homomorphic?

In Paillier, if it were possible to determine whether an encrypted number is less than 0 (that is, is equivalent modulo N to a value $x$ where $N/2 < x < N$), then it would be possible to decrypt arbitrary encrypted values with only the public key.  That is, if someone found such a method, they will have broken Paillier as a public key system.

The details are fairly straight-forward; to compare an encrypted value $E(x)$ against a known value $y$, you compute $E(y)$, use the homomorphic property to compute the value $E(x+y)$, and then use your blockbox to determine from this value whether $x+y<0$

Hence, you can use binary searching, using the above method as the comparison method, to recover the value $x$ given $E(x)$, using $O(\log N)$ probes.


Proof of (in)distinguishability based on DDH/CDH/DL I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group generator):
Given the input tuple $(g, g^{\alpha_1}, g^{\alpha_2}, g^{y}, g^{z})$ where $z \in \{y \alpha_1, y \alpha_2\}$, the desired output is $g^{\alpha_i}$ (or simply $i$) such that $z = y\alpha_i$.
If it is not known, I would appreciate any suggestions for a reduction based proof.

The two given tuples are computationally indistinguishable. Here's a proof
Let tuples $T_1=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_1y})$ and $T_2=(g,  g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_2y})$
Lets take a tuple $T_3=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^r)$ where $r \overset{$}\leftarrow
 \mathcal{R}$. That is, for the purpose of the proof we generate a tuple with the last element being a random element of the group.
It's easy to see that $T_1 \approx T_3$ ($\approx$: notation for compuational indistinguishability) because of DDH assumption. Same way, $T_2 \approx T_3$ as well. Since we know that computational indistinguishability is transitive, that means $T_1 \approx T_2$.


Does RSA key transmit with OAEP insecure? In the Key encapsulation article of Wikipedia, the RSA-KEM is described shortly, as follows;

Generate a random element $1<m<n$ then drive your symmetric key by  $M=\text{KDF}(m)$
Then compute the ciphertext and transmit $c \equiv m^e \pmod{n}$
The reciever decrypts $m \equiv c^d \pmod{n}$ and apply $M=\text{KDF}(m)$ to derive the key.

Q1: The random selection should be $\sqrt[3]{n}<m<n$ due to cube-root attack?

Now at the end the document it says;

  An attacker who somehow recovers $M$ cannot get the plaintext $m$. With the padding approach, he can.

Q2: How can the attacker recover the $M$ while there is formal proof of OAEP.

Q1: The random selection should be $\sqrt[3]{n}<m<n$ due to cube-root attack?

Suppose $n$ is 2048 bits long.  Then $\sqrt[3] n < 2^{700}$.  If $m$ is uniformly distributed in $\{1, 2, \dots, n - 1, n\}$, what is $\Pr[m < \sqrt[3] n]$?  Is this probability large enough that you have to worry about it?

  Now at the end the document it says;

    An attacker who somehow recovers $M$ cannot get the plaintext $m$. With the padding approach, he can.

  Q2: How can the attacker recover the $M$ while there is formal proof of OAEP.

I don't know exactly what the article is getting at here, but what really matters is that even if the adversary has a collection of $(c, H(m))$ pairs where $c = m^e \bmod n$ and $H$ is a random oracle, it doesn't help them to predict $H(m)$ given a $c$ not previously seen before.  Usually the way we use this to encrypt a real message—an arbitrary bit string—is:

Use RSA-KEM to generate $(c, k)$ where $k = \operatorname{KDF}(m)$ and $c = m^e \bmod n$.
Use $k$ as the key for a symmetric authenticated cipher like crypto_secretbox_xsalsa20poly1305 to encrypt the actual plaintext.
Transmit $c$ along with the authenticated ciphertext.

The recipient can recover $m = c^d \bmod n$, and then $k = \operatorname{KDF}(m)$, etc.

This composition of a KEM and a DEM (data encapsulation mechanism; an authenticated cipher serves as a DEM) provides the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.


Solving for a One-time pad cipher help ; crib dragging doesnt work (no surprise) Basically we're given the text

  7ECC555AB95BF6EC605E5F22B772D2B34FF4636340D32FABC29B
  73CB4855BE44F6EC60594C2BB47997B60EEE303049CD3CABC29B
  64C6401BAF45F6A930435F3DF875C4E102F8742A45C824AFCA9B
  7AC24F5EAF17F0A0754D5834BC3CC3A90ABD7B2A52C222ABC89B
  72C24A52B550B3B8624D4F22F86BD2B30ABD642C498122A1D29B
  73CC5457BF17E7A4750C5423B178D0A44FFF756355C03CABC28A
  74CC0155B443B3A8795F4224AA7E97B507F2632606CF3FA0D59B

And what we have to do is solve this, I understand the fact that if used properly the one-time pad is uncrackable but in this case we abuse the fact that certain characters are repeating ("ABC" and/or "AB") and have to use XOR in the process some how, unfortunately the problem is that it wasnt very well explained how to solve and other online resources dont really explain it very well in my opinion

How does one go about solving this?

Take the ASCII values of each letter , convert them to binary and xor them with characters you think it may be. You can do it manually or have the internet tell you each characters values. Just from what I read from the link posted it above it shouldn't be that difficult to do. Since this cipher you have has a lot of repeats, you should be able to crack it fairly easy follow the previous posts guide.


Multiparty key exchange for end-to-end encryption I need to make end-to-end encrypted messaging between 2 and more parties without trusting a server. Each party has it's secret and private keys. The obvious solution is to make ECDH between all of them, but it may require N-1 key exchange rounds. Is there another way to generate shared secret among N participants with less rounds required than ECDH?

Well There are many options to do so. One of them and the most easy to implement and naive one is to do one of the following:

Each participant sends its own temporary symmetric secret key to others via pairwize secure channels. Every time each participant receives a message is reiceived from him/her/it uses this key to decrypt it. (I think WhatApp does this using Signal's Sender Keys)
The rooms initator owner (The one who wants to talk) sets up pairwize key generation with the one who participates and sends the common room/chat key.

An another Option (and the most efficient one) is to use a Group Key Agreement protocol like ART or the (n+1)sec uses.

The only Difference is when you use Diffie Hellman in each protocol modify it to use the variety of Diffie hellman that uses Eliptic Curves or even Deniable Group Agreemens Such as 3XDH like signal does.


Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y? My understanding is that $a^b \bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $ \log_y x \bmod p$.

For instance, if we are trying to compute the discrete logarithm of 3 to base 2 - given that $p=11$, what would be the output (or the equation)

Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution.

Let $G$ be any group and $\odot$ be the group operation. For any $k \in \mathbb{Z}_{>0}$, let $b \in G$ then we define $[k]b =  \overbrace{b\odot\cdots\odot b}^{{k\hbox{ - }times}} $. Then for a given $a \in G$ the $k$ that satisfies $[k]b = a$ is called discrete log of $a$ to base $b$. It can also be written as $k = \log_b a$

Additive DLog : The analogous definition for $(\mathbb{Z}_p,+)$ is well-defined with given $a,b,n$ find $x>0$ such that $x a \equiv b \bmod n$. It can be solved easily  if you find the inverse of $a$ by using the Ext-GCD algorithm.
Multiplicative DLog :, the discrete Logarithm Problem (DLP) is given $a,b,n \in \mathbb{Z}^+$ find $x \in \mathbb{Z}_{>1}$ such that $a^x \equiv b \bmod n$, if such $x$ exists.

For the small modulus we can build a table for the DLP problem, or you can stop building the table whenever you find your case.

The below is a DLog (Discrete Log) table for modulus 19 with base 2.

\begin{array}{c|rrrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \color{red}{13}& 14& 15& 16& 17& 18\\ \hline
2 ^x \bmod 19&  2& 4& 8& 16& 13& 7& 14& 9& 18& 17& 15& 11& \color{red}{3}& 6& 12& 5& 10& 1
 \end{array}

For example, given 3 as the DLog base 2 modulo 19, we will look for 3 in the second row and corresponding $x$ in the first row that is 13. I.e. $2^{13} \equiv 3 \bmod 19$

Different bases will produce different tables; for base 5:

\begin{array}{c|rrrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18\\ \hline
5 ^x \bmod 19&  5& 6& 11& 17& 9& 7& 16& 4& 1& 5& 6& 11& 17& 9& 7& 16& 4& 1
\end{array} If you know the relation with the two bases then you don't need to calculate another base.

This approach is actually is brute-forcing the and has $\mathcal{O}(n)$- time complexity.

The brute-forcing approach will fail around when $n \approx 2^{80}$. There are better search algorithms for DLOG, the generic algorithms that work for any group;

Shank's Baby-Step Giant-Step method with $\mathcal{O}(\sqrt{n}\log n)$-time and $\mathcal{O}(\sqrt{n})$-space.
Pollard's $\rho$ method with $\mathcal{O}(\sqrt{n})$-time is improved version of Shank's method.
Pollard's $\lambda$ method (wild and tame kangoroos)
Adleman's index calculus with $\mathcal{O}(\exp(c \sqrt{\log n \log\log n}))$
Gordon's NFS algorithm with $\mathcal{O}(\exp(c(\log n)^{1/3}(\log\log(n)^{2/3})$-time

and

Pohlig–Hellman algorithm that is applicable when the order of the group is smooth. It has  $\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)$-time complexity where $\prod_i p_i^{e_i}$ is the prime factorization of group order $n$. To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time.

DLog for Elliptic Curves (Additive): DLOG is also defined for Elliptic Curves, in which given a base point $G$ and another point $Q$ find $x$ such that $[x]G = Q$ where $$[x]P = \overbrace{G+\cdots+G}^{{x\hbox{ - }times}}$$

Dlog is not hard for every EC like curves with $|E(\mathbb{F}_q)|=q$. In Elliptic Curve Cryptography, we use curves where the Dlog is hard.

Some of the above generic algorithms, Pollard's $\rho$, Pollard's $\lambda$ also apply for DLog for Elliptic Curves, except index calculus-based algorithms and NFS. The records on finding DLog on EC mostly based on parallel Pollard's $\rho$.


Diffie-Hellman for Encryption In learning how DH works for cryptography applications, I'm coming across some confusing language. For starters, most of the time DH is discussed in the context of "generating" their shared secret. However, I'm also seeing that it can be used for encryption purposes as well (such as encrypting the shared secret using an ephemeral key).

As a concrete example, I'm trying to encrypt with the following formula:

y = mgabmod n

However, I'm having trouble finding how to decrypt based on that formula. What is the use case for that formula, and what is the decryption process?

To decrypt with this system, the decryptor first computes $g^{ab}$ (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of $g^{ab}$; that is written as $(g^{ab})^{-1}$.

The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is commonly referred to as the reciprocal): $b  = a^{-1}$ is true iff $a\times b = 1$.

So, $(g^{ab})^{-1}$ is that value $x$ where $x \times g^{ab} \equiv 1 \bmod n$.

Modular inverses can be computed using the Extended Euclidean method; another method (which is usually more expensive, but not drastically so) that works if $n$ is prime is using the identity (for $n$ prime and $a \neq 0$):

$$a^{-1} \equiv a^{n-2} \bmod n$$

Once you have that, then the decryption can then be computed by a single modular multiplication:

$$m = y \times (g^{ab})^{-1} \bmod n$$

In addition: When using DH for encryption using the method you are using, it is more normally called ElGamal (after the person who first invented it); you might want to use that as the search term to look up more information on it.

In addition, there is a distinct (but generally better) alternative method for using the DH primitive to perform encryption; that is known as the Integrated Encryption Scheme; you might want to study that as well.  One advantage that has is that it doesn't require a modular inverse to decrypt.


Is there a proof for showing any cryptogram is crackable? I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time".

Is there a proof to show that any cryptogram is "crackable"? The proof may be of a more philosophical form rather than relying on mathematical proofs. I really don't know what to expect, but would be fascinated by anything that could show empirically that all cryptograms are crackable (as opposed to a proof that all known strategies for encryption are crackable)

Related: Is it enough to say that given enough time and resources, all brute-force attacks will eventually succeed?

Not all ciphers can be broken, even by infinitely powerful adversaries.

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need at least as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (e.g. by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.

To illustrate this, consider what happens if one tries to brute force OTP:
 Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the corresponding plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to every possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0, 1, 2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.

Most cryptographic methods we use now are computationally secure. There are lots of different ways to show this, and I'll just sketch two of them below:

We might come up with a reduction to a problem conjectured to be hard (e.g. the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve Some-Hard-Problem".
Meaning our problem is at least a difficult to solve as Some-Hard-Problem. So, if the problem is indeed hard to solve, then so must be cracking our encryption.
Another method used is that you might be able to prove a lower bound on the effort required to break a cipher, in terms of some security parameter. Then, the security parameter can be set such that this lower bound is higher than the strength of any computer that could possibly be built. Notice, the infinitely strong computer described in the question could still break such a scheme, but we could fix the parameter so high that it would be impossible to make a computer that could break it.

Possibly of interest: wikipedia:provable security


Definition of one-way functions: randomly-chosen point vs every point Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$.

In the context of computer-science a strong one-way function is generally defined as follows:

A function $f:\Sigma^{\ast}\longrightarrow\Sigma^\ast$ where $\Sigma=\{0,1\}$is a strong one-way function if the following conditions holds:

$f$ can be calculated in polynomial time.
If $M$ is a probabilistic Turing machine that inverts $f$, then for every polynomial $q:\mathbb N\longrightarrow\mathbb N$ there is a $k_q\in\mathbb N$ such that  for every $k>k_q$ we have that
$$\textrm{Pr}\bigg(M\left(f(x)1^k\right)\in f^{-1}(f(x))\bigg)\le \frac{1}{q(k)}$$
for $x$ randomly chosen in $\Sigma^k$.

Many book emphasize the fact that $x$ is randomly chosen amongst all strings of length $k$. But what is the difference between the condition 2) stated as above and a condition $2)'$ where the phrase "for $x$ randomly chosen in $\Sigma^k$" is replaced by "for every $x\in\Sigma^k$"? Generally if a property is true for a generic element of some set, then we conclude that the same property holds for all the elements of the set. Why this importante on the random choice of the string $x$? To be more precise, when I read "for $x$ randomly chosen in..." can I interpret this sentence as "for any $x$ in..."? It seems that the answer is NO, but I don't understand the reason.

(This is the Wiki definition ).

The reason you are looking at a random choice of $x$ is that, otherwise, there is no probability space any longer. Put differently, if we require that for every x there should not be an algorithm that given an image $f(x)$ can output a preimage, we have a problem, because there is such an algorithm. For every $x$ consider the algorithm $M_x$ that on any input simply outputs $x$. Thus, we have just defined for every $x$ an algorithm that (on input $f(x)$) inverts the function.


Why can't we use a hash with no collision to compress data reliably? According to wikipedia, a hash maps digital data of arbitrary size to digital data of fixed size.

For all practical measures, a hash is a unique signature of a big chunk of data. But there is such a thing as a collision free hash, I "heard".

Other than being able to decompress back, arguably the main difference between compressing and hashing is precisely that collision factor - but what if the hash has no collisions?

Why exactly can't we "just" get that "perfect" hash and use it as a compressing method instead? Wouldn't it be able to generate way smaller files?

I see how I must be just missing something, so it's just my way of trying to understand what's the underlying difference between hashing and compressing! :)

Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is.

Cryptographic hash functions in good standing have no known collisions. That's one of their defining properties. They do have collisions, but there isn't enough computing power on Earth (if not in the whole universe) to find one, given current mathematical knowledge. A SHA-1 value is 160 bits, so we know that there exists a pair of 161-bit strings that have the same hash, but the best-known techniques to find one are out of range of current computing power (not out of range of imaginable computing power, though, which is why we're moving away from SHA-1).

Intuitively speaking, if it's hard to find collisions for a hash, the hash is hard to inverse. If there was a known algorithm to invert a hash, then at some point the algorithm would have to decide which of the possible preimages to go for, and we could run it with both decisions to find a collision.

It is possible to use a hash as a compression function. But since there is no way to calculate the original text from the hash, this compression method can only be used when the original text is available. Sounds useless? Not quite. In fact, that's one the basic reasons to use hashes! Cryptographic hashes are used when there are two storage or communication mechanisms, one that's secure but supports only a small volume of data, another that's insecure but supports a large volume of data. Store the hash on the small, secure storage and the actual data on the large, insecure storage. Then, when you need the file, retrieve the data, retrieve the hash, and check the hash. In this way, the secure storage mechanism uses the hash as a compression function; the decompression function makes use of the insecure storage, but guarantees the security of the outcome. (You'll not that something is lost, however: if the insecure storage is corrupted, this will be detected, but cannot be corrected. The “decompression” mechanism guarantees integrity (if you get the data back, it's the right data) but not availability (you might not be able to get the data back).)

Seen another way, a cryptographic hash can be used as a compression mechanism, but this requires that each time a new file is stored, the decompression function is somehow modified to remember the original file content. This is clearly impractical, but it is of theoretical interest — this basically describes a random oracle, which is a sort of idealized version of a cryptographic hash.

A perfect hash is a different kind of beast: it is mathematically collision-free, but it achieves that by restricting the possible inputs to a finite (usually small) subset of all possible inputs. The decompression function for a perfect hash is usually stored as a table from hash values to the corresponding original data (for example using an array if the hash values are small integers).


For CFB, if the IV is corrupted, can the system re-synchronise? How does CFB (Cipher feedback mode) self correction work? And if the initialization vector (IV) is corrupted during transmission, how will it affect encryption or decryption?

Depends on the type of corruption (mangled vs. lost data) and what the segment size is.

If you use a segment size equal to the block size, which is most efficient from a computational point of view, you can recover from corruption that changes data. However, you cannot recover from dropped bytes unless you happen to fall on the same block boundary – i.e. the dropped data is a multiple of the block size.

Recovery is based on the fact that to decrypt a block of data you only need that block's ciphertext and the previous block's. This is similar to CBC. The "advantage" (see below) CFB has is that you can use a segment size of a single byte and recover from any number of dropped bytes. In that case to decrypt a byte you only need the ciphertext of a sliding window up to that byte and its alignment does not matter. You could even do that with bits if you wanted to.

However, in practice such error recovery is not very useful. Indeed, we usually want to use authentication and discard any message that has changed in transit. Otherwise an attacker could be able to change the message, even if only in random ways.


Logjam-style attack on Factoring? We're all aware of the Logjam attack, which is known as "FREAK on discrete logarithms". The attack works by doing a large pre-computation step, which needs only to be done once per field and then quickly computes discrete logarithms. As this seems to be a special property of the GNFS version for discrete logarithms I asked myself if the same property applies for the GNFS version for factoring.

Question: As the GNFS performs a large pre-computation step, can intermediate results be re-used for distinct factorizations?

Yes, but it's different and not as cost-efficient.

The discrete log variant of the number field sieve goes (very loosely) like this:

Collect logarithms of many small primes using sieving and linear algebra (the precomputation stage)
Represent the target field element as a product of small primes and use the small logarithms to recover it (the individual logarithm stage)

In factorization by the number field sieve we do not have an individual log step, so the same principle used in Logjam does not apply directly. But if we look deeper into the inner workings of the number field sieve, we can obtain something similar.

The number field sieve begins by choosing two polynomials $f(x)$ and $g(x)$. The only conditions required for these polynomials is that they share the same root modulo $N$—the number to be factored—and that they are irreducible (if you find a splittable polynomial, you can immediately factor $N$). There are several ways to accomplish this, but the most common is (again, loosely):

Pick an appropriately-sized base $m$
Represent N in base m, and let $f(x)$'s coefficients be the $d+1$ base-$m$ digits of N. Thus $f(m) = 0 \pmod{N}$.
Let $g(x) = x - m$. Trivially $g(m) = 0 \pmod{N}$.

Then, we proceed with the number field sieve:

Find pairs $(a, b)$ such that both $b g(a/b) = a - bm$ and $b^d f(a/b)$ are smooth.
Once sufficiently many pairs have been found, use linear algebra to find two distinct squares modulo $N$: $t_1^2 \equiv t_2^2 \pmod{N}$.
Compute the square roots on both sides, and factor $N$ with $\gcd(t_1 - t_2, N)$.

Notice that $g(x)$, for any particular fixed $m$, is always a root of the polynomial regardless of which $N$ we are working with. This suggests a batching approach:

Pick an appropriately-sized $m$ for a given integer size (or set of integers $N_i$). Say, $m \approx \sqrt[6]{2^{1024}}$ for $N \approx 2^{1024}$.
Precompute a sufficiently-large number of pairs $(a, b)$ for which $a - bm$ is $B$-smooth for some appropriate bound $B$.
For every $N_i$, take the pairs $(a, b)$ precomputed earlier and find the ones for which $b^df_i(a/b)$ are also smooth. Then proceed with the number field sieve as usual.

This approach was suggested by Coppersmith as the "Factorization Factory", and is itself based on earlier work by Schnorr, who also found a batch version of a factoring algorithm by Miller. The complexity Coppersmith came up with was $L_N[1/3, 2.006]$ time and $L_N[1/3, 1.638]$ space for the initial precomputation, and then $L_N[1/3, 1.608]$ time for each individual factorization. Here $L[a, c]$ is the usual

$$
 L_N[a, c] = \exp((c + o(1)) (\log N)^a (\log \log N)^{1-a}).
$$

In 2001 Bernstein proposed the "circuit NFS", which used the area-time (AT) cost metric instead of the usual RAM metric (where memory is free), which had been used until then. This metric shows that the factorization factory is actually pretty terrible when it comes to cost, due to its enormous space (and time) requirements. Circuit NFS instead optimized for the AT cost—using mesh circuits instead of a more common RAM model—and reached an AT cost of $L[1/3, 1.97]$. The Batch NFS follow-up included Coppersmith's factorization factory ideas into the circuit NFS, and given sufficiently many numbers to factor reaches an AT cost of $L_N[1/3, 1.704]$ per factorization.

Now, this may make the Batch NFS sound great, and raise the question of why, say, the FREAK attackers did not use it. Firstly, the Batch NFS assumes a mesh circuit layout; this alone makes implementing it out of reach for the vast majority of people, since we are generally constrained to (more or less) RAM machines. Secondly, the results on the Batch NFS are purely asymptotic—we simply don't know what the constant factors look like in reality.

There is one instance of the factorization factory being used in practice—the Mersenne factorization factory. Here the authors flipped the idea above: instead of fixing $g(x)$ and testing $b^df(a/b)$ for smoothness, they fixed $f(x)$ and tested $a - mb$ for smoothness. The result was an estimated 50% savings in computation on the factoring of 17 Mersenne numbers, with a 70 TB storage overhead. This is a fairly modest saving, but according to the authors it gets worse for general (that is, RSA) numbers. In practice, without your own chip factory you are likely better off factoring each integer one by one with the classic number field sieve.


is the functional signature result relies on f(x) or on x where x is a message and f is a function? I am new on cryptography and I have a question about the functional signature scheme. The notion was introduced in this paper.

In a functional signature scheme, there is a standard signature and verification key pair, as well as an algorithm to derive functional signature and verification keys, for any function f. The signature scheme allows signing any message m in the range of f.

Can anyone please tell if the resulted signature corresponds to the result of the function f over the data m or a signature of a message m corresponding by the function f?

A signature $\sigma$ created by $\mathrm{FS.Sign}(f,\mathit{sk}_f, m)$ is a signature on the value $m^* = f(m)$.
You can see this because the verification algorithm just takes the signature $\sigma$ and the image $m^*$ as input and hence signature validity syntactically does not depend on $f$ or $m$.
You can see this in Definition 3.1.

This is not only a syntax thing, however. If the scheme fulfills the property of "function privacy" (Section 3.1), a signature on $m^*$ is required to look independent of the function and pre-image used to create it. With details omitted, the property requires the following: Given a signature on $m^* = f_0(m_0) = f_1(m_1)$, the verifier cannot tell whether the signature was created by $\mathrm{FS.Sign}(f_0,\mathit{sk}_{f_0}, m)$ or by $\mathrm{FS.Sign}(f_1,\mathit{sk}_{f_1}, m_1)$.

I hope I understood your question correctly.


How could an offline app verify a signature from one of many private keys? I have a situation where an offline app needs to be able to verify whether some data was created by a set of privileged users of the app. These privileged users will each have one private key of some sort that can be used to sign this data. Any user (privileged or not) must be able to verify that the data came from a privileged user.

I'm not sure what the number of privileged users is going to be, but for the sake of discussion we can assume it will be no more than 100,000. And the app being offline means it can't rely on connecting to a server to verify any data or update itself.

I know one possible way to do this with public-key cryptography would be to generate all of the needed public/private key pairs ahead of time, include all of the public keys in the app itself, and give each privileged user one private key. Then signed data from privileged users could include some metadata that identifies which public key should be used to verify its signature.

However, I'm not sure what the security implications of that method is. I'd also like to keep my app as compact as possible. If I used 2048-bit RSA encryption then the size of 100,000 public keys would be just under 25 MB. In this day that's not too bad but it'd be nice if that space requirement wasn't there.

So my two questions are:

Are there any significant problems with the above approach?
Is there a cryptography method available that would allow me to do the above without needing to include so many public keys? Ideally it would also a) allow a practically unlimited number of private keys to be generated after the app is released, and b) not have the signatures be anonymous, though neither of those are strictly necessary.

I'm also open to alternative approaches for accomplishing what I'm after. My understanding of cryptography is admittedly not so deep so I may be missing or misunderstanding something.

You seem to be the person that is responsible for the private keys or at least the app. In that case you should look into PKI: public key infrastructure.

The most well known PKI infrastructure is that for TLS certificates. If you take a look at the certificate store of your favorite browser you'll see that there are no certificates there for your favorite services. Instead there is a set of trusted certificates of different certificate issuers. These are used to sign other certificates, in the end one of these certificates is the certificate of the end user, in this case a web server. This end-user is certificate is called a leaf certificate. The first certificate in the chain is called a root certificate. The certificates together look like a certificate tree.

The idea of a PKI is that the public key is part of the certificate. In the end this public key is trusted because there is a chain of certificates leading to a certificate that is trusted.

So you should become your own CA: you will create a self-signed root certificate, which is shipped with (and therefore trusted) by your app. You sign other certificates using the private key that is part of the key pair for the root certificate. Now the users can use their private key to create a signature, and have that signature be accompanied by the certificate that contains the public key of the user. Once that certificate is trusted by chain verification to the root certificate, the public key is trusted and can be used to finally verify the signature.

Generally PKIX is used, which uses a specific type of certificates called X.509 certificates. There is pre-made software that can be used to create certificates. An example is openssl ca.

The difficulty with your approach is not the security - public key or certificate pinning is a valid approach. The problem is the management: each time you add a key you need to update all your software. That is not the case if you can verify a certificate chain, only one certificate needs to be trusted. A certificate can also contain things such as identity, issuer, validity period, key usage and more.

Note that revoking a certificate or public key can be more tricky. You may need e.g. an Online Certificate Revocation Status protocol server so certificates and public keys can be trusted to be still valid.


Does Lamport's authentication scheme still work if the hash function is not collision-resistant? Geology professor Peter McMenteur gets interested in Lamport’s authentication
  scheme. After a brief study, he claims that the scheme works even if the hash
  function is substituted by a function that is only easy to compute and hard to invert
  (i.e., a hash function without the property of collision resistance

Can anyone point me in the right direction with this ?

Lamport's one-time authentication scheme requires a one-way function.  In terms of cryptographic hash functions, one-wayness is (practically, modulo some technical differences in the definitions) equivalent to first preimage resistance.  In particular, a function does not need to be collision resistant in order to be one-way.

(A practical way to construct a non-collision-resistant one-way function is to take any given one-way function, such as a secure hash function, and make it ignore one of the bits of its input.  This weakens the first preimage resistance of the function only slightly, but completely destroys both collision resistance and second preimage resistance.)

Indeed, the original description of the scheme (Lamport, 1981) does not mention hash functions at all, but rather suggests constructing a  by encrypting a fixed plaintext with any secure encryption algorithm, using the input as the key and the resulting ciphertext as the output (citing Diffie & Hellman, 1976).  Such a construction generally does not guarantee collision resistance and, in particular, will trivially lack it if the encryption scheme has equivalent keys.


Quoting the original answer at StackOverflow

  Haven't got enough time to look up the details, but I would guess that you're applying (or not applying) padding correctly. That would cause the right result to come up for some input lengths, but not for others.

  I guess I'll look into this more, but I wanted to get something in under the bounty wire :)

  Edit: Ok, found an error. Not sure why you're getting it, but if it's fixed, then the right answer comes out. In your not-working example, you calculate w (s^-1 mod q) as

 w =  702955297882281869313155599553522395227576660460 // s^-1 mod q

  but I get

 w =  702955297882281869313155599553522395227576660458

  off by 2! Really, really close values though. And it can be shown that mine is right:

s * your_w mod q = 308227306159276200906356361486529830038073078504

s * my_w mod q = 1

  If you plug in this w value, you then get

u1 = 536931432138658080437983667536052790245747416035
  u2 = 591698847955233800072578903940910445457030802333
  v = (g^u1 * y^u2) % p % q = 666804200764671083282351405489424949903645052927
  r == v

  Hope that helps.


Security benefits of Ed25519 generating signatures deterministically I am reading on the Ed25519 curve, and I am trying to understand a claim. Here is the claim:

  Foolproof session keys. Signatures are generated deterministically;
  key generation consumes new randomness but new signatures do not. This
  is not only a speed feature but also a security feature, directly
  relevant to the recent collapse of the Sony PlayStation 3 security
  system.

Does that mean a node or device in the system will have its own unique key? (The Sony PlayStation 3  reference is confusing me).

Since Curve22519 is Diffie-Hellman based, does that mean a Ed25519 curve simply assigns a different base point on the curve? (And derives the public point from a serial number or other hardware characteristic).

Its also not clear to me why a "fast" verification is needed in this case. It seems to me it should not matter how fast (or slow) a node or device is when verifying a signature since its not a frequent operation.

The paper itself has more details on this:

  ECDSA, like many other signature
  systems, asks users to generate not merely a random long-term secret
  key, but also a new random secret session key $r$ for each message to be
  signed. ... If the same value r is ever used for 2 different messages the
  secret key can be computed as well, as ElGamal... It was reported in
  [24] that the latter failure had occurred in Sony's ECDSA
  implementation for code-signing for the PlayStation3, immediately
  revealing Sony's long-term secret key.

As is also mentioned in that section, but to avoid me quoting the TeX, actually knowing $r$ lets you recover the key directly - you don't actually need two messages using the same $r$, although as I understand it the PS3 hack used two messages.

  Since Curve22519 is Diffie-Hellman based

I think there's a slight confusion there. I believe the origin of Curve25519 was for use with ECDH,but:

Curve25519 is just an elliptic curve - that is, a curve of the form $x^2 = y^3 + ax^2 +b$. Curve 25519 is just a specific set of parameters $a,b$, as opposed to nistp-521, which is again just a different set of parameters. See Curve25519,

You can perform any group operation over a rational points on an elliptic curve (it turns out they form a group) so you can perform DH in elliptic curves. You can also perform DSA, hence ECDSA, ECDH (DSA, DH over EC).

This is the beauty of algebraic number theory :)

In this paper they are concerned with signature verification, hence the use of DSA.

  EdDSA avoids these issues by generating
  $r=H(h_b, \ldots, h_{2b-1}, M)$ so that
  different messages will lead to different, hard-to-predict values of
  r. No per-message randomness is consumed ...

From this it sounds like they're taking a hash of the message and the key (the $h_b$) and using this to derive the per-message secret (hence determinism - it is directly related to the message).

At first glance, this looks a little insecure since knowing the message and assuming a relatively short key length you could potentially compute the inverses of the hash using a rainbow table. However, bear in mind $r$ is supposed to be secret too - knowing $r$ breaks DSA.

I can't comment on its security beyond that as I am not qualified to - someone with far deeper knowledge of DSA would have to say something - but the authors are all well respected cryptographers.

  ts also not clear to me why a "fast" verification is needed in this case. It seems to me it should not matter how fast (or slow) a node or device is when verifying a signature since its not a frequent operation.

I think it depends really. If you have an embedded device, which I believe is the target here, a lower clock speed (and fewer cores) makes any verification more costly. If you go as far as say smartcards, then fast verification is desirable. Likewise, if you are producing for example a HSM or any other dedicated, embedded cryptographic device you might be concerned about performance.


What type of curves have co-factors? I read that non-primes only have co-factors, but Edwards have a co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime right?

How is the co-factor created, some have co-factor 4 and some have co-factor 8?

Am I right in saying that P256 for example, has no co-factor because it is of prime order?

I have seen a Twisted Edwards Curve with prime order, but also had a co-factor, was I mistaken?

I have also seen the case where co-factor = 1. This is strange because in order to make sure that the value is in the subgroup, we must multiply it by the co-factor. If co-factor is 1, then this is irrelevant.

I will attempt to answer some parts of my own question.

Short answer: All of them.

We define curves over Fields which have size n. We then operate in some subgroup of it, which has size/order r.

The cofactor is calculated by doing n/r . if the cofactor is equal to 1, then it means that n = r and the subgroup is equal to the whole field.

I would like to say by intuition that this means that since the co-factor is an integer. If n is prime, then the co-factor is either n or 1. The case where the co-factor is n means that the subgroup has one element. Could this be the empty set? or just the neutral element?

The case where the co-factor is one would be the only logical or useful case, which means that the subgroup is equal to the order of the field. My intuition tells me that every prime field would therefore creator subgroups that are equal to it's size.

If n is not prime, then this means that there are other numbers that it can divide by. 8 and 4 seem to be special numbers.

I would like to say that we the 8 and 4, or any multiple of two, pops up because these curves normally have orders of 2^m.

h = 2^m / r => r must be even and so must h. Does this imply that h must be a multiple of 2?

Yes. h*r = 2^m => that h and r must be multiples of 2.

I've not seen curves with odd primes, however I do not see any reason for there to not be any.

  I have seen a Twisted Edwards Curve with prime order, but also had a
  co-factor, was I mistaken?

From my deduced understanding, it must have had a order that was 2^m.

  I read that non-primes only have co-factors, but Edwards have a
  co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime
  right?

A quick google search would have shown that this number ended in 6 and so is even.

  Am I right in saying that P256 for example, has no co-factor because
  it is of prime order?

Co-factor is one.

  How is the co-factor created, some have co-factor 4 and some have
  co-factor 8?

I explained this part above where they have an order of 2^m

I'm not quite clear on how to find a G s.t. it has a small subgroup and I am not sure how multiplying a point by the co-factor "puts it in the subgroup" . Will open another question for this.


Please help a complete noob with deniable encryption! I am completely new to cryptography and am interested in encrypting two basic text strings into one encrypted text that can be accessed separately with two different keys (preferably using something easily accessible like 256bit AES). For example:

Text1= I like peanut butter

Key1= Password1

Text2= I'm allergic to peanut butter

Key2= Password2

Output: 5UniWN0MjkPvUbLImrQUP68W4tpwOBMp2nrDqV73xeY

This output is just Text1+Key1, but is there a way that I can get both to work simultaneously so if Key1 is used, Text1 is returned, but if Key2 is used, Text2 is returned?

From my understanding, this is called deniable encryption and I was wondering where I could find a generator.

Thanks so much in advance!

If you aren't concerned with integrity guarantees, one easy way of accomplishing this is via AES-CTR encryption. For a given ciphertext, decrypting with any AES key results in a valid plaintext.

That being said, you should be concerned with integrity guarantees. I'm not recommending deploying any crypto which does not meet standard security notions like IND-CCA2.


Password hash contained '\x00' in middle, resulting in ValueError from bcrypt.hashpw I have some code that accepts a password in string format, and hash it with SHA3-512 before passing it to bcrypt for hashing. However, by some coincidence, I found a test case that produces a hash that contains '\x00' in the middle of the hash result, as seen below:
password_str = 'tes15!tes15!tes15!tes15!tes15!tes15!tes15!tes15!tes15!tes15!tes15!tes15!.'
password_bytes = password_str.encode('utf-8')
hashed = hashlib.sha3_512(password_bytes).digest()

The hashing result that contains '\x00' in the middle of the hash:
b'u~"\x98\xac\xc8E2eV\xbb\x8e#}\x92R\xdc\xa2\xab\xab\xcb\x8d.~\x9f\x82a\xbf\xec]k\xdb\xc55\x1d\xa4\x00\xe8\x03\x94\xb0\x91\x14\xf0\x9ec\x9a\x9ay\xfeP\xe3\x07J\x00\xb5\xbd\xba\xcb(\xf5\xdb\xab\x1a'

As we can see, there is an '\x00' found in the middle of the hash, but not at the end. bcrypt detects this a ValueError exception:
if b"\x00" in password:
    raise ValueError("password may not contain NUL bytes")

I understand that '\x00' is a reserved character and possible attack vector due to hash-length extension attacks. However, I do not think that I have done anything outside the ordinary. Is there a best practice that sanitizes the hash prior to passing it to bcrypt that I am missing, or is there another type of byte-encoding that should be used with passwords?
It would be weird to reject a normal password just because it's derived hash conflicts with the auth library used.. Any help or advice is greatly appreciated. Thank you!
EDIT: After posting, I found some issues on bcrypt that describes my problem
https://github.com/pyca/bcrypt/issues/55
https://github.com/pyca/bcrypt/pull/57

You should not be hashing it before passing to bcrypt, which is designed to do the hashing and key-stretching work itself.
It's choking on the hash result because it's expecting a redundant, mushy, ASCII (or UTF-8), not-rigorous, user-entered string.
Generally speaking, hashing things that might be untrustworthy is good to avoid various numeric vulnerabilities (e.g. the internal SHA-512 ops in Curve25519 to sanitize things) -- but, in this case, you can just trust bcrypt; it's designed to work safely and well when fed a lame, user-created password (and a proper, randomly-generated salt ).

 On further contemplation, though, I believe that the behavior of pyca/bcrypt is actually incorrect here. You are supposed to use a cryptographic hash function to convert passwords which are more than 72 bytes (576 bits) into a size that bcrypt can accept. [This is only for pigeonholing purposes; it IS still designed to safely stretch cryptographically mediocre passwords.]
Looking at the ticket on their tracker, and the changeset which they affirmed as having "fixed" it, it appears that the authors did not actually fix their implementation's oddball behavior, but instead merely updated their documentation to recommend the following workaround:

a common approach is to hash a password with a cryptographic hash (such as sha256) and then base64 encode it to prevent NULL byte problems…

This seems sloppy and bizarre to me; it will, for instance, limit such digests' output to, at most, around 408 bits (with base85 encoding), thus truncating >72-byte passwords to just 51 bytes. I would be very interested to see the opinions of more experienced cryptographers on this.
This doesn't negate the first half of this answer, but it's something to keep in mind. Obviously, even with the workaround, the scheme is still quite secure (the best cryptographic schemes are designed to survive some slip-ups in their implementations); it just doesn't seem completely correct to be applying such arbitrary truncations to the user's password, above and beyond what the author of bcrypt itself applied.

You might want to consider bouncing that 72-byte limit back to your users, if you would otherwise have to truncate longer ones by a minimum of 30% to comply with pyca's implementation quirks. (I'm sure that those who care to max out their password's entropy and are hitting that 72-byte limit would, if they looked into how the sausage is made, ultimately prefer the former.)


How would the opponent defraud this secure communication? I am new in the cryptography and the information security problems, I try to understand things as much as I can and I know it's really complicated in the beginning.

Considering the communication protocol between a bank and its machines is standard and we have got an opponent who knows a little bit the way the information is encrypted. Of course this wouldn't cause a problem since the code that the bank uses is considered secure ( a secure Stream Cipher ).

The problem is the bank does not use a MAC. In that case, how would the hacker defraud the bank ? I thought that the MAC doesn't have any relation with the confidently ?

I appreciate your help/ explanations

For an attacker to be able to actually successfully break the security of the bank, we need to make a few assumptions, which I'll state here:

A stream cipher without proper authentication is used.
The attacker knows the data format the bank uses.
The attacker knows the recipient and amount of a transaction (i.e. the interesting values), which he may change.

First we need to consider how a stream cipher works. Most stream ciphers work by taking a key and an initialization vector and expanding this to a long keystream. The keystream $K$ is used to encrypt a message $M$ to the ciphertext $C$ as follows: $C=K\oplus M$ where $\oplus$ denotes bitwise XOR.

Now assume that the message being actually sent by the bank is $M$ containing a valid recipient and a valid transaction amount. Now further assume the attacker wants to replace this by $M'$ where he increases the amount and makes himself the recipient. One nice thing about bitwise XOR is that $a\oplus a = 0$ holds. Now the attacker can calculate the difference $\Delta=M\oplus M'$. He now replaces $C$ by $C'=C\oplus \Delta$. Now observe that $$C'=C\oplus\Delta=(K\oplus M)\oplus (M\oplus M')=K\oplus M'$$ which will decrypt to $M'$ by XOR'ing $K$ in again.

As requested by Maarten in the comments:

The (actual) Example

Assume that 0001001001100101100000001011010010 is the (legitimate) recipient ID.
Assume that 0000010111011100 is the legitimate transaction amount in USD.
Assume that 1001001100100100011110000010001010 is the attacker's ID.
Assume that 1100001101010000 is the attacker's preferred enrichment.
Assume that the message encoding consists of simple concatenation of the recipient ID and amount.
Assume that  01011000011010011001110010010110101100010100011100 is the keystream.
The message $M$ is then 00010010011001011000000010110100100000010111011100 and the (legitimate) ciphertext $C$ is 01001010000011000001110000100010001100000011000000.
The malicious message $M'$ would be
10010011001001000111100000100010101100001101010000 and therefore the
difference $\Delta$ would be
10000001010000011111100010010110001100011010001100
Thereby $C'$ is
11001011010011011110010010110100000000011001001100 which will be decoded to 10010011001001000111100000100010101100001101010000 which is $M'$ and thereby the attacker will receive 50k USD.