Should the identity of a sender be verified using additional means, or does a MAC suffice? This question is aiming at clarification related to message authentication codes (MACs).

Wikipedia’s Message Authentication Code article states:

  In cryptography, a message authentication code (MAC), sometimes known as a tag, is a short piece of information used to authenticate a message—in other words,  to confirm that the message came  from the stated sender (its authenticity) and has not been changed.  The MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content.

(emphasis mine)

Is it correct to say that MACs not only provide integrity information related to the data itself, but also validate the identity of the originator? Or does it make sense to verify/validate the identity of a sender using additional cryptographic means – maybe something along the lines of a Sender Identification Code, Originator Verification Code, or something like that?

Differently asked:

Should the identity of a sender be verified using additional means, or does a MAC suffice?

It is a recurring topic: what exactly is identity and how to prove it ?  But related to your question: a MAC (correctly implemented) proves that the author of the message was in possession of the secret key (like you are, if you can verify it).  Now, depending on the application you have in mind, that's a good enough proxy of identity, or it isn't.

In other words, a MAC takes as assumption that you trust that only the right entities have knowledge of the secret key (you included), and then prove that the message could only have been signed by one of these entities.  The question of whether the right entity has the knowledge of the key is then another issue.


Question about CTR_DRBG Instantiation specification NIST SP 800-90a defines the CTR_DRBG in section 10.2.

There is a comment within the document that I don't understand.

Let's assume we want to achieve a security strength of 256 bits, using as underlying algorithm AES-256 and we do use a derivation function.

Therefore in Table 3 the entropy string is supposed to be within $[256,2^{35}]$ bits and the personalization string is up to $2^{35}$ bits.
The seedlen is equal to $384$ bits.

But in section 10.2.1.3.2 "Instantiation When a Derivation Function is Used" step 1 seed_material is defined as

seed_material = entropy_input || nonce || personalization_string

with the comment "Ensure that the length of the seed_material is exactly seedlen bits".

What is the sense of this comment ?

If personalization_string and entropy_input are allowed to grow up to $2^{35}$ bits, how can their concatenation (excluding the nonce) be forced to be exactly $384$ bits ?

I believe the comment is explaining the next line:

seed_material = df(seed_material, seedlen)


Is that possible to calculate modular inverse of a point on elliptic curves? Imagine that you are given a point $P$ so that $P=a\times G$. If you have no knowledge of $a$ is that possible to calculate point $I$ so that $I$ is the modular  inverse of $P$?

We know that over prime fields each member has a modular inverse, which means for $a\in \Bbb F_n$ there exists $x$ so that $ax\equiv 1\pmod n$. Now, My question is, is that possible to calculate point $I$ on the same curve as $P$ for which the equation  $I=x\times G$ holds. This is to happen with no knowledge of either $a$ or $x$.

If such algorithm exists or become discovered in future will that be considered a weakness to the security of elliptic curves?

No, this is a known variation of the computational Diffie-Hellman problem, called Inverse computational Diffie-Hellman (InvCDH), according to which on input $g$, $g^{x}$, it is difficult to find $g^{x^{-1}}$.

See section 2.2 at Variations of Diffie-Hellman Problem by Bao et al. for more info and problem reduction proofs.


How to only encrypt a subset of the plaintext I was wondering if there is a smart way for a user to only encrypt a subset of a plaintext.

I'll try to be more specific. Let's suppose the user U wants to use a special cipher such that given a plaintext P and some additional information, it only encrypts the subset requested by the user, the rest of the plaintext is not modified.

Does it exist such a cipher? If so, where can I find it and how does it work? If not, how would you do design such a cipher?

Thanks

EDIT:
I've read about selective encryption but it looks like it's mainly meant for images and video streams

You can get what you want programmatically. No special ciphers or modes needed.

You say there is a single, continuous subset that needs to be encrypted. Thus, you could have a function where the programmer specifies the start of the portion of the plaintext that needs to be encrypted and the number of bytes to encrypt. The function could pull that part out, encrypt it (using a good block cipher and mode) into a buffer. Then write out the part preceding it, the ciphtertext, then the part following the portion that needs to be encrypted.

If you require integrity checks too, a simple HMAC of the plain-part-one + ciphertext + plain-part-two using a different key would do.


Rock-paper-scissors over network, how to protect from cheating server? I'm trying to design cryptographic protocol to play Rock-Paper-Scissors with two parties, neither trusting each other, nor trusting server they use for communication, so game is 'provably fair'.

So there are Alice and Bob. They don't know about each other, and they've came to server to match them with each other, with server prompting them to make a bet.

Alice comes to server and deposits some money
Bob comes to server and deposits some money independently of Alice
Alice thinks out of her bet (say, 'rock'), but tells server HMAC('rock', 'some_random_secret') instead of just plain text, to prevent server from implementing always winning bot.
Bob tells server HMAC('paper', 'secret string by bob')
Now server has both commitments, and it publishes them to parties, so Alice gets Bob's commitment, and Bob gets Alice's commitment. Server does not know actual moves.
Now server expects for Alice and Bob to disclose their choices and secrets, and depending on disclosed choices, pay out the pot to winner (minus some server royalty), or if draw just returns money.

Now here is problematic case: imagine there is no Bob, but only server pretending to be Bob.

Alice deposits her bet to clearance account and sends pseudo-Bob commitment of her 'rock' move.
Server responds Alice with clearance of some random move.
Alice discloses to server plaintext of her move.
Now server checks if it's own move was winning — if it was, server claims victory and gets money Alice deposited, providing Alice with proof.
If server appears to be losing, it just pretends pseudo-Bob left the game due to connection problems or whatever, cancelling the deal and returning Alice money.

It's not possible for real Bob to cheat this way, because when Bob gets Alice plaintext, he had already sent his own plaintext, so server knows who had won and who hadn't.

I've been thinking about closing deal by timeout if second party does not respond with plaintext within some reasonable time (or had provided plaintext that does not evaluate to commitment given before), but in cheating server case it's possible to pretend server just hadn't received Alice's plaintext to make her always losing.

Does a solution to this exist, or is this more like "pigeon chess"? How to convince both Alice and Bob server is fair?

If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely.

I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably fair.

One way to do that is to award the bet to the remaining player if one leaves the game for any reason. Now if the server decides to keep the money by becoming unresponsive, Alice will know not to trust that server in the future, instead of keep losing money to it.

Another is to start communicating with Bob before the game begins and agree on a server at random. Now the probability of a server ripping off Alice is equal to the probability of Bob colluding with that server.

Lastly rock-paper-scissors doesn't depend on some input from the server, so the server can't prove fairness ahead of time.


ECC algorithm pollard's $\rho$ complexity One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to find w.

The algorithm is supposed to take a time $O(\sqrt p)$.

The authors say its exponential or subexponential, at best. How is it that way?

Is there any relation between w and p which makes it exponential?

Wiki article says without any citation:

  The algorithm offers a trade-off between its running time and the
  probability that it finds a factor. If n is a product of two distinct
  primes of equal length, running the algorithm for $O(n^{1/4} polylog(n))$
  steps yields a factor with probability roughly half.[citation needed]
  (Note that this is a heuristic claim, and rigorous analysis of the
  algorithm remains open.)

When we say an algorithm is 'exponential' or 'polynomial', when mean that the running time is bounded by an exponential or polynomial function of the size of the input in bits.  That is, the input of the function is not $p$, but $\log p$.  And so, $O(\sqrt p ) = O( e^{1/2 \log p})$ is bounded by an exponential in $\log p$.

Also note that the Wiki article is not talking about the Pollard rho algorithm applied to ECDLP, instead it is talking to Pollard rho applied to factorization.  For the Pollard rho applied to factorization, the time it takes is a factor of $p$, where $p$ is the smaller factor; hence, (because the factors are approximately the same length) $\sqrt p$ is roughly $n^{1/4}$ (with the $polylog(n)$ factor coming into place because Pollard rho isn't perfectly efficient in this scenario).


Use of nonces in Kerberos and Needham–Schroeder protocols Can you please explain me what is the reason of using nonces in the Needham-Schroeder and in the Kerberos protocols for Key Transport.

In particular :

Can you explain me the use of $N_A$?

And also, I suppose $N_B$ is used for the scope of letting $B$ know that $A$ shares the same key $K_{AB}$ and was able to decipher the value of $N_B$, alter it and encrypt it back by using $K_{AB}$.

Is this assumption correct?

And finally:

How does the use of the nonces provide more security to the protocol?

Here you can find more details about the two protocols.

For Needham-Schroeder, $N_A$ is used to prevent a replay attack. Look at the message from $S\to A$. Without a nonce, a malicious server could replay an old but valid response. The message would still decrypt, etc. Furthermore, the key $K_{AB}$ would be the same as a previously used key which could open up the system to more attacks.

It is the same for Kerberos.

You are correct with $N_B$. The only way Alice could return $N_B-1$ is if she knows $K_{AB}$. Thus it is to prove knowledge of the key.

The nonce $N_B'$ in Needham-Schroeder is used to prevent a replay attack with someone spoofing Alice to Bob.

  How does the use of the nonces provide more security to the protocol?

It ties messages to specific sessions of the protocol. This ensures that all messages are "fresh" which prevents replay attacks.


Is using different public keys for different peers safer than reusing the public key, beyond forward secrecy? In X25519 (ECDH over Curve25519) Peer A and B exchange their Public Keys PkA and PkB and then calculate a shared-secret SecAB using cominationOf(SkA, PkB) == combinationOf(SkB, PkA).

For forward secrecy, I think it's recommended for A and B to re-negotiate a new shared-secret regularly (thus advertise new Public Keys).

Leaving that aside is there any other disadvantage if A uses the same Public Key that they have with everyone to get corresponding shared-secret VS if they use new Public Key with each new peer ?

In other words:

Peer A gives PkA to all, B, C, D ..., and as usual calculates shared-secret using PkB, PkC, PkD as SecAB, SecAC, SecAD and so on and uses those to encrypt/decrypt messages to the corresponding peers.
Peer A gives new Public Keys to each. So PkAB to B, PkAC to C, PkAD to D and so on. Then, just like before, calculate the shared-secret after using Public Keys of the corresponding peers as SecAB, SecAC, SecAD and so on.

Is 1. above less secure in context of how X25519 (and its maths) works than 2. ? Or is it just wasteful to do 2. and 1. is equally good ?

Generally for forward secrecy you should not just limit the use of the private key (and thus public key) in time, but also per connection. For that reason, you can assume that in most implementations that require forward secrecy that there will be one ephemeral key pair per connection, not per time frame.

Similarly, you're assuming that a new key pair is generated regularly, but please note that this kind of wording may be interpreted as once in a certain time frame. It makes a lot of difference how much the key is actually used within that particular time frame. So I think in your scheme you're using the private keys too much (you could tie that to forward secrecy, but you haven't made is explicit that you did see this tie to PFS).

One of the big disadvantages of your scheme is that the delivery of the public keys is required for each party. Some parties actually may not be active at all, and therefore distribution of the keys would be waste full. It also means that there must a central distribution point, which could wreak havoc in a distributed design.

Possibly you should simply exchange public keys each time you want to generate a new symmetric key, tying the validity of the private key to the symmetric key. How long you want to keep that symmetric key active is another matter. I'd say you could keep it active for a certain amount of actions within a specific time frame; having two rather than one limit for invalidating key pair and generating new ones. I'd certainly do that for each connection separately as indicated in the first section.


Can any one explain Circuit Privacy using fully homomorphic encryption from Gentry's thesis? Craig Gentry's thesis talks about circuit privacy being straight forward from fully homomorphic encryption in the last chapter.

Can somebody explain in simpler terms what that means ? I have read it couple of times but could not get it. While the definition of Circuit privacy is simple the realization of the same using FHE in the last chapter is what is tough to understand.

Let $\rho$ be the 'initial noise level' of ciphertexts output by FHE.Enc. Fix any such ciphertexts $c_1$, ..., $c_k$.

Fix some function, written as a circuit $C$. Let $\rho_f$ be the 'final noise level' of ciphertexts output by FHE.Eval($C$, $c_1$, ..., $c_k$).

And observe that it should be easy to distinguish a ciphertext $c$ with noise-level $\rho$ from a ciphertext $c'$ with noise-level $\rho_f$, since they will be in geometrically different regions of the lattice (due observably differing noise levels).

Now, to achieve circuit privacy, we define the goal to have the distribution of ciphertexts output by FHE.Enc and the distribution of ciphertexts output by FHE.Eval be indistinguishable. Clearly, this is initially not the case (given the above discussion about noise levels).

So: To fix the problem, we "drown out" both the noise terms of size $\rho$ and size $\rho_f$ by introducing a MUCH BIGGER noise term $\rho^*$. To be specific, this means adding $c^*$ (a ciphertext encrypting 0 with noise level $\rho^*$) to the outputs of BOTH FHE.Enc and FHE.Eval.

E.g. define ciphertext $c_{re-rand} \stackrel{\rm def}{=} c + c^*$, and ciphertext $c'_{re-rand} \stackrel{\rm def}{=} c' + c^*$. (And from here on, we will be comparing the distribution of ciphertexts $c_{re-rand}$ vs the distribution of ciphertexts $c'_{re-rand}$, generated in these respective ways.)

In fact, we will set $\rho^*$ to be super-polynomially larger than $\rho_f$. Thus, statistically, since $\rho^* \ggg \rho_f > \rho$, we only need to consider the $\rho^*$-sized noise terms when arguing indistinguishability.

But since the noise terms in both $c_{re-rand}$ and $c'_{re-rand}$ that are of size $\rho^*$ were drawn independently (and from the same distribution), the distributions of re-randomized ciphertexts are indistinguishable, as desired.


Is it secure to repeatedly rehash a digest to extend the digest length? Upon reading through the source code of Rainbow, a post-quantum signature algorithm, I found a hashing function that, using SHA-512, produced a variable length digest.
This was achieved was by initially hashing the message to obtain a 64 byte digest, and then hashing that digest, and again, each time hashing the N - 1 digest. It's essentially being used as a deterministic CSPRNG.
Is this secure? Can SHA-512's digest be stretched out indefinitely like this? And why didn't Rainbow simply use a well-studied CSPRNG like ChaCha20?

Section 2.6 of their submission talks about this.
There they state that for most cases they simply use SHA-256, -384 or -512.
In the (uncommon?) case that a hash function with a larger output is needed, they use the OFB-like1 construction.
The rationale being that a collision on the OFB construction would immediately imply a collision on the underlying hash function - as the direct output is part of the expanded output.
This also explains why they don't want to involve another (more efficient) function: To reduce security guarantees and prefer simplicity over optimization for rarely needed scenarios.

1: OFB-Mode is a way to construct a PRG and an CPA-secure encryption scheme out of a fixed-length PRF. It works essentially as $K_i=F_k(K_{i-1})$ outputting $K_1\|K_2\|\ldots\|K_\ell$ for a PRF $F$ and a secret random key $k$.


What do NM-CPA and NM-CCA mean? When I've been researching authenticated encryption, the following terms keep showing up:

NM-CPA
NM-CCA

....without any definition as to what they mean. I've tried searching the web for their definitions, but I'm not getting very far. Could someone explain what these abbreviations mean, and why papers such as this one don't give a definition of their meaning?

Edit: While the possible duplicate question explains IND-CPA and IND-CCA (which I think I'm still going to have trouble remembering), it doesn't explain the NM- ones.

A cipher $E_k(m)$ is malleable if there is a nontrivial binary relation $\sim$ on messages such that given $c = E_k(m)$, it is easy to find $c' = E_k(m')$ with $m \sim m'$.  For example, AES-CTR is malleable because for any $m$ and $m'$ with $m' = m \oplus \delta$, it is easy to compute $$c' = c \oplus \delta = E_k(m) \oplus \delta = E_k(m \oplus \delta) = E_k(m'),$$ in which case $m \sim m' = m \oplus \delta$.  A hash-then-encrypt variant where we encrypt $m \mathbin\| H(m)$ instead is still malleable because it is easy to compute $\delta = (m \oplus m') \mathbin\| [H(m) \oplus H(m')]$ for any desired message $m'$.  Similarly, textbook RSA, where the ciphertext for a message $m$ is $m^e \bmod n$, is malleable because for any $m$ and $m'$ with $m' = m \cdot \eta \bmod n$, it is easy to compute $$c' \equiv c \cdot \eta^e \equiv m^e \cdot \eta^e \equiv (m \cdot \eta)^e \equiv (m')^e \pmod n,$$ in which case $m \sim m' = m \cdot \eta \bmod n$.

As defined by Dolev–Dwork–Naor (paywall-free) and used throughout the literature, a cipher is nonmalleable (NM-) under an attack model (-CPA, -CCA, -CCA2, etc.) if, after interacting with the oracles in the attack model, and upon being presented a challenge ciphertext $c$ for a message of a form chosen by the adversary, the adversary cannot find—even using further interaction with the oracles—a nontrivial relation $\sim$ and a ciphertext $c'$ whose plaintext is related by $\sim$ to the plaintext of $c$.  (Here we rule out trivial relations like $m \sim m$.)

In practical terms, nonmalleability means an adversary can't selectively modify ciphertexts; the worst they can do is denial of service or wholesale replacement.

The Bellare–Namprempre 2000 paper you cited on generic composition of symmetric ciphers and MACs doesn't formally define nonmalleability because nonmalleability is largely not important for the symmetric setting: when the sender and recipient share a key, they generally care about eavesdropping and forgery, but not about selective modification—detecting forgery means detecting selective modifications, and rejecting forgeries prevents abusing selective modifications to leak secrets.

Nonmalleability matters more in the setting of public-key anonymous encryption, like an activist leaking a document to a journalist.  While it may not directly reveal to the adversary what a message was, selective modification can often be exploited in a larger system like an PGP mail client with EFAIL to leak the message when there is no notion of authentication to prevent forgery per se since anyone can anonymously submit documents.  So nonmalleability is defined in the Bellare–Desai–Pointcheval–Rogaway 1998 paper on generic relations between notions of security for public-key encryption.


Is using HMAC signature as a long-term password secure? I'm considering implementing an authentication service without storing users' passwords/hash.

I want to use a key derivation function with a corresponding username and a master secret key to calculate the password of the user(user is actually a service). Then deliver the derived password to each user(service).

Something like using HMAC(secret_master_key, username) or PBKDF2(HMAC(secret_master_key, username)) as the long-term password for user. Or maybe some other algorithm should be more suitable for this scenario?

Is this way secure cryptographically? Thanks in advance.

As long as your master secret key is generated properly and protected properly, this should be fine. HMAC is widely believed to be a pseudorandom function. So, the output (i.e. the password = PRF(secret_master_key, username)) should be pseudorandom and has good entropy.


Reducing a 64 digit integer to 10 digit Situation:-
I am using Python.
I am using RSA and I am using two 64 bit keys. I am not an cryptographer .
I can provide you the RSA code if needed but i am not posting it as it doesn't have to do anything with the problem. I have to give the private key to a human to remember well 64bit key cannot be remembered by normal humans as far as know.
Problem: -
I want a method to compress my 64bit key to at least an integer of 10 digits and a method when those 10 digits are entered they decompress back to 64bit key.
Solution I have tried: -
Converting my 64 digit integer sequence to an string phrase or a string (the worst Idea wasted a lot of time do not try yourself).
Using basic math operations such as 'division', 'subtraction', etc. This proved to be not a good practice as it is easily readable in the code.
Note

I need not to change the private key whenever programs run but whenever client wishes to.

If is not possible to reversibly compress a 64-bit RSA key (nor a 64-bit prime) into 10 digits after the fact: there are just too many such keys or primes to assign them a unique 10-digit value. And at this size RSA is totally insecure, I mean breakable in a fraction of a second. Even 640-bit is insecure, see history or factorization records there.
However, that are several ways to use secure parameters for RSA and arrange things such that what's needed to decipher can be remembered as 10 digits (or a short passphrase or sequence of words: that's easier for most humans).

The classical way, used e.g. in PGP/GPG and OpenSSL, is to use a normal RSA key (say, 4096-bit) and encipher it when at rest using password-based encryption, with the 10-digit value used as the passphrase/password. That is symmetric cryptography, with the symmetric key derived from the password (and salt) by a purposely slow hash function, such as Argon2, scrypt…
When the private key is needed, the passphrase-to-key slow hash is run, recovering the symmetric key, then used to decipher the RSA private key (stored in a file, but here that could be in the database). The public key is stored in clear (it's not secret anyway).

A less common option is to generate the primes in the RSA key using a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG) seeded by a key derived as above. When the private key is needed, the passphrase-to-key slow hash is run, recovering the symmetric key, then used to seed the CSPRNG and re-generate the same RSA private key as originally.

The advantage of 2 is that it's impossible to loose the encrypted version of the private key, since none is needed. It's drawback is that it is impossible to change the passphrase, and that we loose the first line of defense against attacks: we normally try to keep the encrypted private key out of reach of attackers.


Are block ciphers more prone to implementation flaws? I came across a Chrome extension: Minilock

It's blog contains a post: "No, the NSA Isn't Breaking AES". Small excerpt is below:

  A block cipher key is pretty much an initial seed for a
  pseudo-randomness permutation more than anything, and that’s why newer
  ciphers have focused on adding features (such as AEAD) instead of
  making ciphers “harder to break”. The most likely source of design
  weaknesses in block ciphers are likely to be not in the block cipher
  itself, but in its mode of operation (ECB spot-the-penguin, CBC
  bit-flipping, CTR nonce-reuse, to name a few). This is why block
  ciphers are now discouraged, and most new ciphers are moving to the
  stream cipher model.

Recently few ransomware started using stream ciphers like Salsa20 (probably because of speed).

I want to know whether there is more chance of implementation flaw in block ciphers as compared to stream ciphers like Salsa20?

If we are not confident with AES implementation, a stream cipher should be used?

A block cipher is a very versatile building blocks for implementing various cryptographic algorithms, such as hash functions, message authentication codes, and yes, also stream ciphers.  You almost never use a block cipher on its own, but as part of some higher level construction.  In a way, a block cipher is a bit like the engine in a car — it needs the rest of the car (or truck or boat or airplane) around it to actually do anything useful.

A stream cipher, on the other hand, does just one thing: it encrypts a stream of data.  (Some modern ones may also authenticate the data being encrypted, to protect it from tampering.)  While you can build a stream cipher by using a block cipher in an appropriate way, a purpose-built stream cipher has "no user-serviceable parts inside" — it's a bit as if a car had the engine and the frame permanently fused together, so that you couldn't separate them without tearing the whole car to pieces.

Now, the article does have a point is saying that the main source of vulnerabilities in block cipher based encryption schemes is not the block cipher itself, but the way it is used.  To stretch the car analogy even further, cars don't usually fail because the engine blows up — more likely they fail because there's something wrong with the drivetrain or the steering or the electrics or the suspension, or because the driver was distracted and ran into an obstacle.

Also, because there are so many different ways to use a block cipher for different purposes, it's arguably easy for a non-cryptographer to select the wrong way of using it.  In particular, to anyone who knows a bit of cryptography, saying that something is "encrypted using AES" is an immediate red flag, because it doesn't say anything about how AES is being used.

For all we know, you could be using AES-ECB (bad idea) or AES-CTR with a fixed nonce (really bad idea) or AES-CBC with a predictable IV (bad idea if the attacker can submit chosen plaintexts to be encrypted) or with padding oracle vulnerabilities (hard to avoid with CBC, and a bad idea unless you use a message authentication layer on top).  Or you could be using AES-SIV (an excellent choice for a maximally foolproof design) or AES-GCM (a pretty good choice for raw speed, and secure as long as your nonces are unique) or even AES-GCM-SIV (a fairly new mode that combines the speed of GCM with the foolproofness of SIV).

Besides, the fact that you're using AES really isn't that relevant for cryptographic security — block ciphers are, by design, interchangeable, and any other unbroken block cipher with comparable block and key sizes is basically a valid drop-in replacement for AES.  What really matters is whether you're using the block cipher in a manner that's appropriate for the purpose (e.g. any IND-CCA2 secure authenticated encryption mode for ordinary message encryption, an appropriate disk encryption mode for mutable random access data, etc.)

All that said, simply using a stream cipher doesn't magically make your code secure, either.  Sure, with fewer choices, there are fewer ways to make wrong choices — but "fewer" doesn't mean "none at all", and worse, one of the possible wrong choices you can make with stream ciphers is choosing the wrong stream cipher in the first place, or not realizing that you may need something more than just the stream cipher.

In particular, most traditional stream ciphers (including e.g. DJB's Salsa20 and ChaCha ciphers, if used without a MAC) are vulnerable by design to exactly the same bit-flipping and nonce reuse attacks as block ciphers in CTR or OFB mode are.  To protect against those attacks, you need an authentication layer on top of the cipher, and a secure way of generating unique nonce values.

So I would say that the conclusion ("block ciphers are now discouraged") is wrong.  Block ciphers are here to stay, and there's no way that stream ciphers could ever displace them, because there are lots of things block ciphers can be used for that stream ciphers cannot.

What is (or at least should be) discouraged, however, is handing out isolated low-level components like AES or Salsa20 to developers, and expecting them to build a secure cryptosystem on top of them.  What you should do instead, as far as possible, is use a standardized authenticated encryption scheme that already contains all the necessary components, and specifies how they should fit together, and which has been published and independently reviewed by multiple crypto experts.  Preferably you should also be using a pre-existing implementation of the complete system that has been written by a competent cryptographer and published and reviewed for possible implementation flaws and side channel leaks.

Whether the chosen system is based on just a block cipher (like AES-SIV) or on a block cipher and a separate MAC (like AES-GCM or Poly1305-AES) or on a stream cipher and a MAC (like Salsa20-Poly1305) is, at that point, of much lesser importance.  In fact, I would argue that it is completely irrelevant, except insofar as it affects the speed, resource use and external security constraints (e.g. whether the system needs a secure source of randomness, and whether it is safe to use on hardware that might be tampered with by an attacker) of the chosen system.

Ps. As for the recent popularization of stream cipher based encryption schemes, I would argue that it's as much a fashion swing as anything else.

At the moment, after a relatively long period where most crypto research focused on block ciphers, we just happen to have a bunch of novel stream cipher designs that are new and sexy (there haven't really been any prominent new block ciphers since AES established its position).  Several of these ciphers, like Salsa20 and ChaCha, have been designed and promoted by a well known and trusted crypto researcher (D.J. Bernstein) who also happens to be the author of a popular crypto library (NaCl) and notably skilled at writing fast and secure low level crypto code, which also just happens to mean that they come with standard implementations that run blazingly fast on popular CPUs (which is attractive to companies like Google that transmit a lot of encrypted data over HTTPS).

This also coincided with the discovery of generic attacks against several widely used block cipher based cipher suites in the SSL/TLS protocol, which made it important to find new alternatives for them.  As such, it's hardly a surprise that stream cipher based encryption schemes just happen to be in vogue right now.


Chosen Plaintext attack on AES in ECB mode I am familiar with the following method for an chosen-plaintext injection attack on ECB ciphers, where I am allowed to append a block of bytes to the packet being encrypted:

I inject a string with known bytes one less than the blocksize and try figuring out what the first byte of the available data could have been by brute forcing all the 256 possiblities. And then, I carry this information over to extract the next byte.

I can understand why this could be used to extract a blocksize worth of the original plaintext. However, how do I extend this method to get bytes beyond the blocksize?

Suppose we have a block cipher that takes a 16 byte plaintext and produces a 16 byte ciphertext (that is to say $\mathcal{Enc}: \{0,1\}^{128} \rightarrow \{0, 1\}^{128}$). We use this block cipher to encrypt two blocks worth of unknown data, call them $m1$ and $m2$. Additionally we are allowed to prepend some data to these two blocks, let's call it $m0$ (we control this data).

Note that in this scheme nothing prevents us from choosing an $m0$ that is 16 bytes long. This means we effectively have an encryption oracle for a full block, since the first block returned in this case would be $\mathcal{Enc}(m0)$ if ECB mode is being used. This means we can get the encryption of arbitrary blocks of data, which will come in handy.

You correctly state that we can set $m0$ equal to 15 known bytes, and if we have an encryption oracle we can brute force the last byte:

 Block 1          Block 2  Block 3
|AAAAAAAAAAAAAAA?|?......?|?......?|
 |----known----||--m1---|

We just have to send all 256 possible guesses for Block 1 to the encryption oracle and see which one matches the output. Let's say we get a match on the byte encoding "w". We then repeat the process with a one byte shorter $m0$ to get the next byte in the same fashion:

 Block 1          Block 2  Block 3
|AAAAAAAAAAAAAAw?|?......?|?......?|
 |----known----|

We can repeat this process for each byte until we have the whole first block $m1$, which let's say is "we attack at daw". Unfortunately at this point we can't reduce $m0$ by any more bytes since $m0$ would be 0 bytes and we would simply get:

 M1               M2
|we attack at daw|?......?|
 |----known-----|

But we since we now know all of $m1$ we can use the sort of attack we used to recover the first byte of $m1$ to recover the first byte of $m2$. Suppose we again choose $m0$ to be of length 15 bytes:

 Block 1          Block 2          Block 3
|AAAAAAAAAAAAAAAw|e attack at daw?|?......?|
 |------------known-------------|

There's only one unknown byte in Block 2 so all we have to do is again submit all 256 guesses to the encryption oracle, except this time for Block 2 instead of Block 1! This process can be repeated to decrypt an arbitrary amount of ciphertext that is ECB encrypted as long as we can prepend data to the plaintext and have access to an encryption oracle.


Post-Quantum Public Key Cryptography with EC math properties Is there any quantum resistant public key cryptography with similar properties of elliptic curves?

Assuming lowercase for scalars and uppercase for points. The properties I'm interested are:

Reusing the same public key.
Given $k = a + b$ then $k \times G = (a + b) \times G$
Distributive Scalars: $(a + b) \times G = a \times G + b \times G$
Distributive Points: $k \times (A + B) = k \times A + k \times B$
Commutative Sum: $(a + b) \times G = (b + a) \times G$
Commutative Mul: $a \cdot b \times G = b \cdot a \times G$

How existing solutions map to the same properties?
I'm interested in the direct applications not how it fundamentally works.

Is there any quantum resistant public key cryptography with similar properties of elliptic curves?

Not at the level you're asking about.

The issue is that Shor's algorithm can generically solve the problem "given $A, x \times A$, recover $x$" for any finite group (and going to an infinite group looks problematic for large $x$).  Hence, we'd need to base the algorithm on a different hard problem, and I don't know of any suitable one that fits in the framework you're looking for.

In any case, basing things on a different hard problem would imply that the crypto would look quite different (even if it happens to satisfy the identities you're looking for)

  How existing solutions map to the same properties?

They don't satisfy those identities; instead, they use different properties to provide public key encryption and signatures (and more advanced primitives, such as IBE and PAKE).


RC4 Keylength Limits While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits.

Why is that? Is there a reason it can't have a lower or higher length?

The minimum of 40 bits is conventional; below 40 bits of key material, RC4 (or practically any cipher without some built-in key stretching) is just too unsafe.
At some point in history, in many countries, ciphers with a key above 40 bits where illegal in some usage (in USA: export; in France: use, sale, export); thus cipher designers wanting to prescribe something as secure as possible often used that 40-bit limit.

The maximum of 2048 bits is a consequence of RC4's key scheduling. Quoting Wikipedia's page on RC4

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

We see that 256 passes are made, and each pass manipulates 8 bits of key; above $8\cdot256=$ 2048 bits, extra key material would be ignored.

Anyway, array S[] remains a permutation of 256 distinct values, hence can hold a maximum of $\log_2(256!)\approx$ 1684 bits of entropy, and that key size limit of 2048 bits is only a practical issue when the key is not truly random in the first place.

In order to strengthen RC4 against weakness in its key scheduling / setup (leading e.g. to break of WEP encryption), it is advisable to stretch the size of the key material (e.g. to the maximum of 2048 bits) using a pseudo-random transformation (alternatively, or in combination, the first 256 or 512 bytes generated can be discarded). And if the original key is low-entropy (e.g. a password), it must be strengthened by a slow key derivation function in order to resist brute-force password cracking. Both can be done using scrypt with dkLen=256, and other parameters set as appropriate for the environment.


Nothing Up My Sleeve Lim-Lee Primes A few days ago I asked a question about the security of the Lim-Lee Prime Generation algorithm used by GNU Privacy Guard’s libgcrypt library.  L. Carvalho provided a good answer to that question.

As a follow up question, I am wondering whether one could use Lim-Lee Prime Generation as a means of creating a “Nothing Up My Sleeve” prime for use in Diffie-Hellman key exchanges?

It seems to me that if one wanted a 2048-bit prime (p) with no prime (other than 2) dividing p-1 less that 256 bits in length then by choosing a set of maximum prime divisors of p-1 that give a prime p, one would have a good construction of unique, "Nothing up my Sleeve" (NUMS) numbers for a given prime size and prime order subgroup size.

I'm thinking that for a 2048-bit Lim-Lee Prime (p), p-1 could be divisible by 2, the largest 255-bit prime, and the 7 largest 256-bit primes such that p is prime. That would be unique – right?

While I agree that there exists a largest Lim-Lee prime I think it may be computationally infeasible to construct/find this prime in a provable way.  The set of 256-bit primes is very large and you would need to search through every product of 7 such primes to find the greatest such product that makes the resulting number a prime.

You could add an additional though rather artificial constraint to make the problem tractable.  You could say that you want to look at products of 7 primes chosen from the 20 largest 256-bit prime and choose the largest such product such that when multiplied by 2 times the largest 255-bit prime (2^255 - 19) and added to 1 the result is a prime number.

There are 20 choose 7 or 77520 products of 7 primes to look at. One would expect there to be many primes formed from these products.

Your criteria for the NUMS prime would be:

Pick the size of the prime.  This size is chosen to make the cost of the Number Field Sieve Discrete logarithm prohibitively high
Pick the size of the sub-primes in the Lim-Lee algorithm.  The base 2 log of this size should be twice the desired security strength.  For 128-bits of security one should use 256-bit primes.  For n bits of security one should use primes of 2n bits.
Pick the size (n) of the set of primes to examine. Given the size of the desired prime (a), the size of the sub-primes (b), c = the greatest integer less than (a/b)-1, you choose n such that n choose c is large enough to expect a prime in the set of putative primes that will be generated.
Choose the n largest primes of size b for the set.

You have then described a family of primes that are unique given choices of

a = size of the prime

b = size of the sub-primes

c = size of the pool of primes

With those three constraints you will have a unique result.  For some sets of parameters there will be ZERO primes that satisfy the criteria.
....
Looking back on your question about Lim-Lee primes from several days ago, many people would recommend staying with the original idea of Lim-Lee's algorithm for ephemeral prime generation rather than using fixed NUMS values.  If you were going to use a NUMS value you might consider using a 3072-bit prime to give an extra hedge against rich adversaries.


chaining rsa with ecies In an answer to a previous question it was suggested that one way to protect your asymmetrically encrypted AES-256 keys, from say a solution to prime factorization, would be to chain asymmetric algorithms. Having read about the meet-in-the-middle attacks here and there I am a bit worried that if I chain, say RSA with ECIES (and why not add an ElGamal?), that I would somehow be undermining my own efforts or  just doing an exercise in futility. Would such a system be more secure over the long-run (i.e. 30 years) than just going with one asymmetric encryption scheme?

You could protect the ECIES ciphertext with a superencipherment of DLIES, and you would not be weakening your security unless you slipped up and reused keys or used related keys.  That means each step should be done carefully and thoughtfully as if it was the only protection step you would be taking.  For example, when generating the cryptographically random value to serve as the session key protecting your data it's not the time to use a SHA-1 hash of "password1".  Don't use one algorithm to protect both the key and the data of the next algorithm.  Don't use ECB mode encryption.  Simple, but important steps.

The key protection algorithms chosen don't necessarily all have to be asymmetric unless that best meets your business needs.  The threat you're trying to guard against is that of a break in one of the algorithms, so the defense your building should include choosing each algorithm from different algorithmic families.  The first algorithm protecting the data should be something venerable and trusted, such as TDEA (3DES).  TDEA is used by IBM mainframes and cryptographic co-processors to encrypt their databases of keys - if it's good enough for IBM and their giant corporate customers, that's a good sign.  To protect the TDEA key as a session key, choose a non-Feistel algorithm, such as AES, to superencrypt it.  Then, choose your asymmetric algorithm such as RSA or ECC to encrypt the AES superencrypted data.

Is this much security necessary to last 30 years?  The idea is that if a class of algorithms suffers a massive failure that you've other algorithms that haven't also fallen remaining in place.  Let's say someone comes up with an instant factoring algorithm, suddenly rendering every RSA encryption ineffective.  If RSA was the only algorithm protecting your AES key, you're at risk.  Using RSA to encrypt the AES encrypted TDEA key would mean that both RSA and AES would have to fail before the attacker could get to your data.

Given that you're talking about a 30 year life span, it sounds like an application that will not be seeing daily use, so I am assuming performance isn't a concern.  What should be a bigger concern is that you or your heirs will have the software, computing equipment, uncorrupted media, and knowledge available 30 years from now to decrypt it (or at least have enough money to hire an expert in ancient cryptographic data recovery.)  The media is important.  If you burn it to DVD, do you know the DVD's inks will last 30 years?  If you print it on a barcode, will they still have a barcode scanner that can read those olde-timey QR codes?  Those are real questions: if my father's will had been encrypted and stored on 96-column punch cards in his safety deposit box, or on a ZIP drive, or an old 9 track tape, or an 8-1/4" floppy, or even printed on cheap fading greenbar, I know I wouldn't have a reader for any of them today.  That suggests you create a test plan that can be periodically executed to ensure future decryption will be successful.  The test doesn't have to decrypt the actual sensitive data, but it has to prove the hardware and software required for the decryption still works, and that the media is still viable.

Regarding the software, you have choices to make there, too.  You need to have faith that if you write a complex unchaining decryption application in .Net that there will be a .Net runtime environment available on Windows 15.1.  Will tiny 64-bit CPUs still be infesting the planet for any purpose other than cell phone CPUs?  Will Microsoft even exist?  If you get 15 years down the path and .Net has evaporated from the face of the earth, what will you do?

And where are you going to store the keys for 30 years?  Are you going to split them, keeping the RSA private key in one place, and the AES key in another?  Are you going to commit one to memory?  If so, are you going to be around in 30 years, or are you OK if the data is lost forever?

Finally, I come back to what should be your first step:  go over your business requirements again and determine if you really need this much over-the-top protection, especially considering the costs of developing and maintaining some non-standard forms of encryption.  Who are the attackers and what is their motivation?  What's the value of the data you're protecting?  How badly will someone really need it in 30 years?  This kind of long term storage is very, very expensive.  Are you willing to commit someone to 30 years of babysitting these secrets?  Let's say the secrets are guarding an account number in an overseas bank.  What happens to the protected assets if your heirs can't peel this onion apart?


Counter Mode: how to choose the nonce part of the counter? Suppose:

The "counter field" is about: NONCE || CTR-VALUE.
I have multiples messages $M_a, M_b, M_c, \dots$
Each message can be divided into x-bits blocks ($M_{a1}, M_{a2}, M_{a3}, \dots$).

Each message $M$ (for instance $M_a$) is encrypted following a randomly and uniquely generated key. In this case, does I really need the NONCE part of the "counter field" ?
If I really need a nonce, and knowing that each key is again unique-per-message, is there a secure way to derivate the nonce from the key ?

The once part inside of the nonce in CTR mode means effectively "once for this particular key".

If you use a fresh key for each message (e.g. by encrypting it using public-key crypto or similar), you can use the same nonce for all the messages (or a size-zero nonce).

The important part is that the combination of nonce and ctr-value (i.e. what is input into the block cipher) is not repeated while using the same key.


Is there an advantage to using a hash in combination with a key-derivation function? Note: This question was originally asked at Information Security Stack Exchange, but was moved here due to a topic overlap.

It is currently recommended by OWASP to use an adaptive key-derivation function, such as Argon2, PBKDF2, scrypt or bcrypt, when storing passwords securely.

Is there any advantage or disadvantage to combining such a key-derivation function with a traditional cryptographic hash (SHA-family, etc.)  function, such as follows: $hash,$salt = kdf(hash($password), $salt).

Attempts at answering the question

Before writing this question, I attempted to find a solution myself. Since cryptography is somewhat famous for being difficult to "get right", I was still uncertain if my reasoning is applicable.

My reasoning was as follows:

  Let's assume that the chosen hash algorithm were completely broken,
  meaning that an attacker could easily calculate a value1
  that would match a given hash. If the used key-derivation function was
  secure, the attacker would not be able to gain any advantage compared
  to a system where the plaintext password would be directly supplied to
  the key-derivation function.

1: Not necessarily the original value, but a value which would result in the same hash.

There is no advantage. A password-based KDF already behaves a lot like a hash function.

There is no weakness to pre-hashing a password if you use a proper hash function.

If the probability of a hash collision is small then hashing does not reduce a cracker's search space.

However, if the hash had a 16-bit output, then you would have a problem. A cracker would just guess-and-check each 16-bit KDF input, skipping prehashing, rather than guess-and-check different passwords.

On the other hand, if you use SHA-512 then you are not reducing a password cracker's search space. Hash functions aren't truly one-to-one functions, but we can safely say we have never hashed two distinct inputs that have the same SHA-512 output. You would expect humanity to have to hash around $2^{256}$ different messages  (give or take slightly on that exponent) before it becomes probable that we would have two messages collide by chance. (That $2^{256}$ makes astronomically large numbers look infinitesimal by comparison.)

Until we generate that many distinct passwords we can get away with approximating the relationship between prehashed "passwords" and pre-prehashed passwords as a one-to-one mapping. That makes the prehashed password basically equivalent to the user's password. (Just in a different format.)

Guessing random 256-bit strings isn't a shortcut or a smart strategy. It still makes sense to guess and check plausible passwords by brute force. Again, the cracker's search space isn't reduced, so there is should be no impact on security.

Note that I said a hash with a low collision probability would be safe (but still pointless). You don't actually need collision resistance. If you used SHA-1 instead, that collision attack wouldn't necessarily have any impact on security. In most real world scenarios that would just mean a user could use more than one password to login to the same account or decrypt the same files. User chosen passwords or randomly generated passwords still won't result in SHA-1 collisions in non-adversial settings.

Aside: The security of password hashes and KDFs in general don't  rely on collision resistance. You just need a function that is preimage resistant and that does not have any biases that reveal information about inputs. (Actually, for KDFs at least, biased output in general.)

A hash that wasn't preimage resistant would not work for user authentication. (A hacker could find a password that hashes to the same value. It wouldn't matter to him whether it was the same as the original password.)

A hash with biases might make a password cracker's search easier.

Password based KDFs like Argon2 utilize hash algorithms with these requirements.

Finally there are two scenarios where prehashing passwords might help. Just not for reasons based in cryptography.

First, there might be quirks in a KDF or password hash. For example, there might be a length limit on the password (as in bcrypt). Prehashing transforms the user input into a fixed length bit string.

Bcrypt has several issues related to user input. If you had to use bcrypt it would be a good idea to prehash a user's password with a 256-bit hash and encode the output using base64. That results in a pure ASCII string with no stray null characters that's small enough to be used with existing bcrypt implementations. (You should still use Argon2 because it's much better for password hashing.)

Second, you may opt for the client to prehash users' passwords before sending them to the server. Web applications typically receive the user's plaintext password, whether they use HTTP or HTTPS. Sending a hash of the password is not a substitute for encryption (because eavesdroppers can just send the same hash without ever requiring someone to log in with the actual password), but it potentially obscures the user's actual password.

If the user's password is weak then the server can guess the original just the same as any other password cracker would. If a password is inhumanly strong then the server won't ever know the user's actual password.

(Although that's unrealistic. If passwords are assumed to be that strong then there isn't the need to use a dedicated password hashing algorithm instead of an inexpensive hash. It's likely better to do client-side password stretching for non-web-applications if the server shouldn't be trusted with actual passwords. Or use an alternative authentication method.)


Is it possible to use the root function to attack RSA? Sorry for my silly question, but I have some doubts on this point. I'm trying to explain it better with an example.

Suppose you use RSA to sign a package and you have the public key. If the signature is generated by the server with its secret key you are able to decipher it because you have the public key and verify the integrity of your package. Suppose I make a "fake" package and I'm able to create a correct signature like this:

00 01 FF .. .. FF 00 ASN.1 SHA1

due to the deciphering process:

cleartext = C^e mod n

I can encrypt my signature in this way:

C mod n = root(cleartext,e)

and make a correctly padded signature without knowing the private key?

Example:

e = public exponent = 3

C mod n = cubicroot (cleartext)

If root is just the function from calculus, then

at most ceil(root(n,3)) elements cleartext of  {0,1,2,3,...,n-2,n-1}

are such that root(cleartext,3) is an integer
and
when its output is not an integer, that output is not a valid signature,

since valid signatures must be elements of  {0,1,2,3,...,n-2,n-1}

.

If root is modular, then for carefully chosen large moduli n, there's no publicly known

feasible classical way to have a non-negligible probability of computing root.

However, quantum computers change things quite significantly.


Combining algorithms for password storage? Is it more secure to combine algorithms for password hashing, for example, Scrypt, Bcrypt, SHA-3, etc.? If an attacker wants to use dedicated hardware, he would need one for each algorithm. However, I know having multiple algorithms increases the probability of having bugs and leaks.
If having multiple algorithms for EACH password can create leaks, what about having different algorithms for different passwords: If the attacker only has hardware for Bcrypt, he can't brute force passwords hashed with Scrypt.
EDIT : By combining, I mean, hash2(hash1(hash0(password))). In the second paragraph, I mean hash0(P0), hash1(P1), hash2(P2), hash0(P3), hash1(P4), hash2(P5).
EDIT : What about hash0(P0), hash1(P0), hash0(P1), hash1(P1), ... ?

The combination of different schemes may be somewhat advantageous with regard to certain custom hardware (ASICs), but I think that the disadvantages outweigh them.

I assume that there is some kind of fixed time that is acceptable to the user. Nobody will use a procedure where she or he has to wait several minutes.
Modern password hashing schemes are characterized by the fact that they are not only time intensive, but also memory-hard. To put it simply, a vector is created in RAM in the time acceptable to the user. If less time is available, this vector is smaller. Splitting the acceptable time over several password hashing schemes results in less time to generate the vector for each single scheme. So the whole process becomes less memory-hard.

Password hashing schemes, like all cryptographic procedures, are potentially susceptible to side channel attacks. This applies, for example, to cache timing attacks. Several schemes offer more targets.

And as the questioner has already correctly pointed out, the susceptibility to bugs is greater with several schemes.

I would rather rely on one scheme such as Argon2id and spend all available time to make this method as memory-hard as possible.


Calculate entropy of key derived from PBKF2 function I am using PBKF2 to derive a encryption key from a password. suppose entropy of my password is y and my PBKF2 function has x number of iterations. So how to calculate the entropy of finale key derived from the PBKF2 function.

According to the paper “Stronger Key Derivation Via Sequential Memory-Hard Functions”…

If

$$2^k = x$$

the entropy of the derived key (DK) key will be

$$2^{k}+y$$


Public and private key lengths I am generating RSA Public and Private keys with node.js instead of reading them from pem/crt files as I can hide them inside a private object using this module https://www.npmjs.org/package/private

this node.js module https://www.npmjs.org/package/keypair puts text in front and at the end of each public and private (-----BEGIN RSA PUBLIC KEY-----)

Edit: forget this question (thanks D.W.) Is this they way they should look or can I remove the text?

var keypair = require('keypair');

var pair = keypair();
console.log(pair);

outputs

{ public: '-----BEGIN RSA PUBLIC KEY-----\r\nMIGJAoGBAM3CosR73CBNcJsLv5E90NsFt6qN1uziQ484gbOoule8leXHFbyIzPQRozgEpSpi\r\nwhr6d2/c0CfZHEJ3m5tV0klxfjfM7oqjRMURnH/rmBjcETQ7qzIISZQ/iptJ3p7Gi78X5ZMh\r\nLNtDkUFU9WaGdiEb+SnC39wjErmJSfmGb7i1AgMBAAE=\r\n-----END RSA PUBLIC KEY-----\n',
  private: '-----BEGIN RSA PRIVATE KEY-----\r\nMIICXAIBAAKBgQDNwqLEe9wgTXCbC7+RPdDbBbeqjdbs4kOPOIGzqLpXvJXlxxW8iMz0EaM4\r\nBKUqYsIa+ndv3NAn2RxCd5ubVdJJcX43zO6Ko0TFEZx/65gY3BE0O6syCEmUP4qbSd6exou/\r\nF+WTISzbQ5FBVPVmhnYhG/kpwt/cIxK5iUn5hm+4tQIDAQABAoGBAI+8xiPoOrA+KMnG/T4j\r\nJsG6TsHQcDHvJi7o1IKC/hnIXha0atTX5AUkRRce95qSfvKFweXdJXSQ0JMGJyfuXgU6dI0T\r\ncseFRfewXAa/ssxAC+iUVR6KUMh1PE2wXLitfeI6JLvVtrBYswm2I7CtY0q8n5AGimHWVXJP\r\nLfGV7m0BAkEA+fqFt2LXbLtyg6wZyxMA/cnmt5Nt3U2dAu77MzFJvibANUNHE4HPLZxjGNXN\r\n+a6m0K6TD4kDdh5HfUYLWWRBYQJBANK3carmulBwqzcDBjsJ0YrIONBpCAsXxk8idXb8jL9a\r\nNIg15Wumm2enqqObahDHB5jnGOLmbasizvSVqypfM9UCQCQl8xIqy+YgURXzXCN+kwUgHinr\r\nutZms87Jyi+D8Br8NY0+Nlf+zHvXAomD2W5CsEK7C+8SLBr3k/TsnRWHJuECQHFE9RA2OP8W\r\noaLPuGCyFXaxzICThSRZYluVnWkZtxsBhW2W8z1b8PvWUE7kMy7TnkzeJS2LSnaNHoyxi7Ia\r\nPQUCQCwWU4U+v4lD7uYBw00Ga/xt+7+UqFPlPVdz1yyr4q24Zxaw0LgmuEvgU5dycq8N7Jxj\r\nTubX0MIRR+G9fmDBBl8=\r\n-----END RSA PRIVATE KEY-----\n' }

Public key is real short!

I found this code

function bitSize(n){return n.toString(2).length;}

If i give the pub key padding like

1001 0011

or some other random repetition of the same byte until the public key is the same length as the private key. Will that be acceptable padding? I would have to protect my prime numbers with this kind of padding, true?

If I did add padding how would the private key have any relation to the padded public (Could it still decrypt?)

There is no need to manually add padding to the RSA public key.

Normally we'd expect the library to do whatever is needed to make key generation secure.  You shouldn't need to do manual tweaks to the public key it produces.  If the library doesn't do that, the library sucks; throw it away and get a better one.

And, for this specific case, no padding is needed during RSA key generation.  There's no need to add any padding to the RSA public key.  Depending upon how the private key is represented, the private key will often be of different length than the public key, so this is not something to worry about.


Proportion of RSA moduli factorable by NFS with less effort than average? When applied to integers $N$ of comparable size, the Number Field Sieve is notoriously much faster if $N$ is known to be of the form $r^k\pm s$ with $r$ and $s$ suitably small integers, and $k$ an integer: using $L$-notation, the running time of this Special NFS is $L_N(1/3,\sqrt[3]{32/9})$, versus $L_N(1/3,\sqrt[3]{64/9})$ for the General NFS. Correspondingly, public factoring records are higher for SNFS than GNFS (1199 versus 768 bits at time of writing).

GNFS is applicable to most RSA public moduli; but there is some small odd that SNFS is applicable to a random RSA public moduli; and perhaps a more sizable odd that some speedup of NFS is enabled by a suitable form of $N$ (perhaps more general than for the original SNFS).

I'm asking for an evaluation of the proportion of RSA moduli of $n$ bits factorable by NFS with $\alpha\ll1$ times the average GNFS effort.

If that proportion was sizable, and the time to identify such moduli not an insurmountable obstacle, that could matter to situations (which abound) where a potential adversary is content with factoring any of many RSA moduli.

The core difference between the SNFS and the GNFS is that the polynomials $f(x)$ and $g(x)$ for the SNFS have short coefficients, where typically the largest coefficient of $f$ is $O(1)$ and the largest coefficient of $g$ is $O(n^{1/(d + 1)})$. On the GNFS, coefficients are typically closer to $n^{1/(d+1)}$ on both sides, which results in much larger integers to test for smoothness.

So the question is: for a randomly selected integer $n$, can we find a set of polynomials, plus a shared root $m$ modulo $n$, such that their coefficients are significantly smaller than average? The answer is somewhat unsatisfying. I'll exemplify with a simple unsophisticated example, but the principle holds in general.

There are many polynomials that can fit the bill, if we don't restrict their size too much. If we let coefficients be bounded by $n^{1/(d+1)}$, then we have $n^{(d+2)/(d+1)}$ possible $f(x)$ polynomials and shared root, $n^{1/(d+1)}$ of which satisfy $f(m) = 0 \bmod n$. This would be $2^{146}$ for $n \approx 2^{1024}$ and $d = 6$.

But what happens when we try to approximate to the SNFS, by keeping $m$ fixed but reducing the coefficients of $f$? Assuming coefficients are uniformly and independently distributed, the number of available polynomials starts decreasing proportionally to the factor we want to reduce them by. For example, for $n \approx 2^{1024}$ and $d = 6$, as before, if we want to reduce coefficients from $\approx 170$ bits to $\approx 170 - 20 = 150$ bits, we find that there are only $2^{146} / (2^{20})^{6+1} \approx 78$ suitable polynomials! Significantly bigger reductions would be unlikely to exist at all, except for a few rare cases, like SNFS-friendly numbers.

All of the above was simply a counting exercise. But the idea is simple—polynomials with small coefficients, which also satisfy the GNFS requirements, are vastly outnumbered by the number of integers to factor.

Even so, it would be great to be able to find optimal polynomials for any integer $n$, even if they don't approach SNFS quality. But we don't really know how to find such optimal polynomials other than essentially brute force search and some heuristic techniques, which are nevertheless very much worth it. Given the mismatch between lower bounds and current algorithms, if the state of the art of polynomial selection were to suddenly improve significantly the answer to your question would be "every modulus".

In case I failed to convey the argument, I'll refer to §12.12 of Buhler et al., §4 Bernstein and Lenstra, §2.3.2 Murphy, §2.2.4 Coxon, or §6.2.7 Crandall and Pomerance, all of which discuss this polynomial selection issue.

Some fine print: size is not the only factor in practice to select a good polynomial. In particular, having many roots modulo small primes seems to help in finding smooth numbers. But as far as asymptotics are concerned, size is the only factor we're concerned with.


Digital Signature Algorithm for large files - bottle-necked by hash function? I am new to studying digital signatures like ECDSA and EdDSA, and was curious about something.

Lets say hypothetically I want to create a digital signatures of millions of files, with a total size of 10TB.

From what I understand, digital signature algorithms are hash-then-sign, and the hash functions used must be cryptographic hashes such as SHA-2 or SHA-3. However, looking up the typical benchmarks of SHA-2 and SHA-3, their speed in terms of throughput (bytes/second) seem to be well under 500MB/s per core on modern laptop CPUs, which is not bad.

But in environments without hardware acceleration, it is probably at least 4x slower. On mobile devices, SHA-3 seems to perform 20MB/s on my phone according to a javascript benchmark.

It seems like in certain environments, the hash function will be the bottleneck in both creating the signature, as well as verifying it. Especially for mobile devices -- it would take several days to sign/verify a 10TB inventory of files.

Are there any cryptographically secure digital signature algorithms that are optimized for large files in terms of throughput? Or are we always bottlenecked by the hash function?

Are there any fast, non-cryptographic hash function we could use for digital signatures while keeping the cryptographic security?

It is potentially a bottleneck, but will it be a problem in practice?  My phone doesn't have 10TB of storage, and if the files are remote the network speed will be the limiting factor.  There are other strategies possible, like computing hashes as the data is transferred to the device, or hash trees for updating a hash without re-computing the whole thing (for e.g. a small edit to a file).


How large is the Playfair cipher keyspace? In the Playfair cipher, is the key space 5 x 5 = 25 or 25 x 25 = 625? I'm trying to work out the size of the key space if each set of equivalent keys is counted as one key.

The Playfair key matrix contains a permutation of the 25-letter cipher alphabet.  The total number of such permutations is

\begin{aligned}
25! &= 1 \times 2 \times 3 \times \dots \times 25 \\
&= 15{,}511{,}210{,}043{,}330{,}985{,}984{,}000{,}000.
\end{aligned}

However, as I noted in a previous answer, the Playfair cipher has equivalent keys: moving a row or a column from one side of the matrix to the opposite makes no difference to the Playfair encryption process.

By repeatedly moving rows and/or columns around in this way, we can pick any of the 25 letters and move it to any desired position in the matrix.  Doing so fixes the positions of the remaining letters, though, so in effect each key matrix belongs to a class of 25 equivalent matrices.  The total number of such equivalence classes is therefore

\begin{aligned}
\frac{25!}{25} = 24!
&= 1 \times 2 \times 3 \times \dots \times 24 \\
&= 620{,}448{,}401{,}733{,}239{,}439{,}360{,}000.
\end{aligned}

Ps. For what it's worth, $24! \approx 2^{79}$.  That is to say, the number of distinct (equivalence classes of)  Playfair key matrices approximately matches the number of distinct 79-bit bitstrings — comparable to, say, the 80-bit keys of the modern Skipjack cipher.  Even so, in practice, Playfair encryption can be broken using just pencil and paper, whereas breaking Skipjack by brute force (though perhaps nowadays possible for large state actors) would require a massive and expensive computing cluster.

The difference is, in large part, due to the fact that a Playfair key can be attacked incrementally: the encryption of each letter pair is determined by only a small part of the key matrix, and does so in a relatively simple way, allowing that specific part of the matrix to be determined just by comparing individual pieces of the plaintext and the ciphertext.  And since the parts overlap, it's possible to join them together piece by piece, like a jigsaw puzzle, until the whole key matrix (up to equivalence, anyway) has been reconstructed.

Modern ciphers, in contrast, are designed so that every bit of the key affects the encryption of every part of the plaintext, and changing even a single bit of the key changes the ciphertext completely in a seemingly random way.  Thus, such incremental attacks are generally not feasible against modern ciphers, so that the fastest possible attack becomes brute force testing of all possible keys one by one.

(Or, at least, that's how it's supposed to be; every once in a while, modern ciphers do get broken by new cryptanalytic attacks — the fancy modern descendants of the kind of statistical and combinatorical attacks that cryptologists of old employed against ciphers like Playfair.  Still, nowadays, the existence of any practical attack against a cipher that is faster than brute force is generally considered to mean that the cipher in question is broken.)


Talking TLS with EC cryptography and the secp256k1 curve How reasonable would it be to speak TLS over the secp256k1 curve? My initial experiments show that OpenSSL supports it (albeit with special flags, see below): Running an OpenSSL client against an OpenSSL server (or some random node.js server that I found) negotiates the suite ECDHE-ECDSA-AES128-GCM-SHA256 and establishes a regular TLS 1.2 session.

On the other hand, neither curl nor browsers appear to like that particular curve. (Although that is not necessary for my use case.)

The reason I'm using secp256k1 is because there is a nice algorithm to derive new keys from an existing key (BIP 32). Those keys cannot be correlated with each other, which is a big plus in peer-to-peer scenarios.

Now my question is: Is it reasonable to use an uncommon curve like secp256k1 for TLS? Or alternatively, is there a secure mechanism to derive a private key for another (more common?) curve from a secp256k1 private key?

The flags I mentioned above: -curves "X25519:P-256:P-521:P-384:secp256k1"

Edit: My question is less about theoretical weaknesses of secp256k1, but rather what kinds of practical problems to expect.

BIP32 uses secp256k1 because BIPs are for bitcoin and bitcoin uses secp256k1. (I feel like Buffy 1.01: "[the reason I'm here now is] because now is when we came here".) The same approach(es) would work for any elliptic curve, with obvious substitutions for ser256 and parse256, and for serp if using a non-Weierstrass form like X25519.

But TLS in practice requires certificates for authentication keys (or kRSA, no longer recommended and in 1.3 no longer supported) and certificates don't mix well with rapidly or dynamically creating keys, via BIP32 or any other means, regardless of the curve(s) used. ('In practice' because there is an RFC for using raw keys, but I've never seen an implementation, certainly not in OpenSSL.)

PS: nodejs builtin 'tls' is OpenSSL, compiled into node[.exe] underneath. You can get alternative (pure-JS) crypto including ECC, but I haven't seen pure-JS TLS.


Are there any tools to analyze cryptographic algorithms performance? How can I analyze a cryptographic algorithm performance to make a table and charts comparing them. I have seen several papers but there's no paper explaining how it is exactly done.
As comparing data block size through time, etc...
Like key size, block size, power, throughtput, data length, processed bytes (MiB/s) and cycles per byte.
Example papers:

A Survey of Lightweight-Cryptography Implementations

Performance Analysis of Data Encryption Algorithms

Performance Evaluation of Symmetric Encryption Algorithms

It is not given because it is assumed that you either know it anyway, if you deal with cryptographic algorithms, or you don't need it, because its complex and time consuming and only a few people in the world need it, and can properly read the result.
To test throughput (Mb/sec, same as processed data) you need a fast device to write to, usually hdd itself adds too much delay to measure this correctly. You could use ram filesystem for it, and write there. You didn't mention the OS, so I will assume linux.
You write a big file and measure the time it took
Knowing how big the file you've made and how much time it have taken, you can calculate the throughput, dividing file size by time taken.
You could use writing to /dev/null, but its hard to predict how much optimization OS will do, so I would offer to avoid this.
Key size is given in algorithm initialization, you cant start without giving this information. If Crypto++ hides this information from you, try to search for something else. Or look for default values. For AES its 16 bytes.
Same for block size. Same link shows that block size is 16 bytes for AES too. As with the previous case you set it up yourself, and many algorithms accept different versions of key size and block size. Those are given at the start by the user. Or are defaults, that can be found about the particular implementation, algorithm + program that make it work.
Power is hard to estimate because efficiency of devices differ dramatically. Even if you measure it for your device, it will be different for another device. Simplest way is to write a large file in RAM, delete it, write again, in a loop for hours till your laptop battery drains out. Then check how big your battery was.
Or try checking the power consumption of your flat on a power meter, but this is even less precise.
Proper method would use something like this
You could get a bit more precise result if you compare idle operating computer with computer that is doing your task. This way you automatically exclude all the parts that are not working for the cryptographic task, like a screen.
The cycles per byte is the most complex part. For this you actually need to read the code and see how many operations are done from start to finish, and then divide this amount of operations by the size of an output. If an algorithm took 17 operations like addition, xor and multiplication, and a device can do all of them in in one clock time, and output is 4 byte long, then the result is 17/4=4.25 cycles per byte. Keep in mind that modern CPU can operate on a very large words, 128bit (16byte), and that some operations can take a very long time, like exponentiation, that can take a 100 operations. You need to find the cost of each operation on a given machine. Usually it is 1 for addition, bit operations, multiplication, about 10 for division, sqrt, 100 for more complex operations like exponentiation, trigonometric functions for a modern CPU. Microcontrollers may only have fast addition. GPU may have fast division, but not bit operations. By fast I mean one cycle operation. So that in one clock step it will make one action like addition.
You may also be interested in checking how strong an algorithm is. This is done by reducing the key size and using a program that analyses the patterns in the output, TestU01 for example. Here is my favorite work on this topic, I like it for simplicity and visualisations mostly:
And this website in general. It allows to see how the cryptographic people think in general, what tools they use, what they value in an algorithm.
TLDR: you are asking about a lifetime worth of time spent collecting tools needed for a very complex task. I cant give you all of them. And there is no ready solution. Very few people need this.


Is it safe to derive two different keys with the same password and key derivation function using two different salts? I would like to know if the following process would harm the security of a fictional system if the persisted data would be stolen: in this system a user has a single password. The password will be used in order to derive two different keys using the same key derivation function (PBKDF2/bcrypt/scrypt) with the same parameters but using different salts. One of the keys will be persisted on the system, the other will not. Both salts will be persisted, too.

Would the persisted key, besides allowing the theoretical brute forcing using the corresponding salt in order to retrieve the password, allow the attacker more information regarding the second key? Does it depend on the actual KDF?

With a KDF meeting its objectives, the only way the leak of the persisted key compromises the confidentiality of the other is correctly identified in the question: a password guess can be checked at the cost of one evaluation of the KDF based on the leaked key and its corresponding salt (and assuming the password's entropy is significantly less than the leaked key's width, it's unlikely there's a false positive); so when and if the password is found based on that, the second key is trivially found.

All KDFs have the objective that knowing the output with one salt, it's impossible to find (or otherwise obtain information about) the output for another salt with significantly less cost than testing the passwords (or more generally: than testing values fed to the key input of the KDF, for those KDFs that are not purposely slow in order to stretch a password's limited entropy). PBKDF2, bcrypt and scrypt convincingly meet that objective.

So the answers to the questions in the last paragraph are no, and no for a good KDF. For the question in the title, I'd answer yes, for a good KDF, and within the fact that the common password can be brute-forced with enough effort.


Quadratic residue zero knowledge proof - simulator with identical distribution I am looking at the zero knowledge proof for quadratic residues and am confused when it comes to showing a simulator that can give a transcript of the proof with the same distribution as the proof output itself.

In all explanations/proofs I have seen online the simulator has an element of iteration in it. For instance, taken from here:

Why is that iterative aspect needed?
I don't quite understand whose distribution we are trying to show is identical to whose too.

The first message from the prover is random just like it is in the protocol itself, b is a random value in both cases too. The second message from the prover to the verfier is distributed like b. what is this simulator gaining from generating two different messages based on b' and then executing something different based on b?

I've read the paper and other sources too but none seem to directly explain the need for this looping and what exactly it is that we want to be distributed the same way.

Any help is greatly appreciated.

Zero knowledge simulator (not honest verifier zero knowledge) is required to produce simulated session transcript that must be indistinguishable. Challenge of Verifier $b$ is the part of the transcript. For identical distribution, real Verifier is invoked to produce the challenge. First message of the protocol $y$ is passed to the Verifier. Simulator-chosen challenge $b'$ is here to properly compose first message $y$ so that it would fit the verification relation. Simulator is looping until it would guess the challenge of real Verifier.

Let me repeat it: query Verifier to pick a challenge with otherwise unknown distribution; the rest of algorithm follows.


Is this number used for factoring challenge only? Lets say one day a VERY VERY lucky guy just GUESS the factor P and Q correctly will there be any security issue in the world. Is anyone using this particular RSA 2048 for anything?

I don't believe so.  On occasion, the need for a composite of unknown (to anybody) factorization comes up; someone might be using it for that.  Such numbers are harder to generate than you might think;  if you just select a random 2048 value, find that it is composite, and run ECM on it a bunch, well, you won't know whether running ECM a bit longer would find the factorization.  Using one of the RSA challenge numbers would make sense in that case, but again, I don't know of anyone who's actually doing it.

On the other hand,

  Cracking this one by luck doesnt mean much right?

While there isn't a great deal of significance to this specific number, if someone did manage to factor it, it would certain raise the issue whether other 2048 bit numbers were hard to factor (which, incidentally, is precisely why RSA generated their challenge numbers in the first place)


Possible to identify cryptographic keys in non-random binary data? From my understanding, a well-generated cryptographic key would be indistinguishable from randomly generated binary data. However, I also know that most cryptographic keys do not appear surrounded only by random noise in practice but rather by structured program data. Are there any demonstrable techniques from practically identifying likely AES keys, for example, in a typical firmware binary (or device memory)?

I think that the problem with your sneaky technique is in the first sentence - "a well-generated cryptographic key would be indistinguishable from randomly generated binary data"  That's absolutely true, and I'm extremely confident that 625,000 well generated unique keys concatenated together will form sufficient data for a Diehard test.  And that data sample would pass, probably with flying colours and no dodgy ps.

However you're only trying to find a single key that's perhaps only 128 bits of data.  That's 16 bytes.  16 random bytes can be anything ('cause it's random).  They could be 101010... or any other non random looking sequence.  That's the pesky nature of true randomness.  Who would have thought that 999999 is totally random, yet it famously is and clearly exhibits very low entropy.  This will easily be lost in all the different micro variations of entropy that constitute a computer application.

This is further camouflaged by things like compressed data structures.  Almost all parts of a JPEG are totally random as a result of lossless Huffman coding.  This might resemble an AES key, and readable high level disassembly is extremely difficult.

The only approach I can find is the brute force extraction technique.  Knowing that your thing is AES encrypted, I'd scan though the application from beginning to end, extracting every consecutive and overlapping 16 bytes.  They run them through the decoder to see if your thing decodes to something understandable.

Now since a complete dummkopf like me thought of this, clever application developers /cryptographers though of it too.  It would be very simple to obfuscate the raw AES key somehow.  Simply XOR it beforehand with another array or distribute the individual bytes randomly throughout the entire memory map.  You could even encrypt the encryption key with another algorithm.  This might be one of the few perfectly valid examples of rolling your own crypto to create security through obscurity.  I'm sure that there are even more complex obfuscation techniques in use - no body wants you to play Halo for free after all.


Deciphering “easy” ciphers without hints I've been keen on IT Security for a long time now and I've learned a lot about networking & security. However trying a "decryption challenge" I'm lacking what I think is basic encryption/decryption knowledge.

So I've got a ciphertext without knowing about the algorithm or key used encrypting the plaintext. I assume that this cipher is not "too hard" (no AES e.g.) to crack, because it would be an overkill for a simple challenge.

I want to mention that I would like to crack it on my own, but I need advice in which direction I should go - what's most likely to be used, how I can verify if some encryption algorithm is used or not, etc.

About the cipher: The Cipher contains [cghijklmnopqrsuvwxyzABCDEFGIJKLMNOPQRSTUVWYZ0-6+] without whitespaces, while some patterns are recurring (same characters are repeating in the same order a few times in the cipher).
 I'm also quite sure the ciphertext isn't hashed as I'm supposed to read what the result is. Cracking a 1000+ characters cipher won't be the "challenge".

What I've already done:

I tried a frequency analysis to see if it's just substituted
monoalphabetically sign for sign - without success (many results
staying at ~8%, no one above 10%)
I had a look at classic transpositioning and substitution methods which lead me to encryptions like Vigenére, Autokey, Beaufort and so
on. However, those are designed to work with non-numeric alphabets as
far as my understanding goes.
I calculated the "Index of Coincidence" being about 0.06, which should tell me that problably a substitution is used (I haven't yet
figured out completely how this works in detail)
I already tried to separate the cipher at points where suspicious, recurring "words" are, just to find something that seems
like separator-signs. However it's not much clearer afterwards and
I'm not sure how to go on.
I did already base64 decode as suggested, but the result was even less helpful. Looks more unrelated than before, just many special characters mixed up with periods and numbers here and there.

What I need would be a good advice on how to find out which cipher may be used as I'm currently running out of ideas what to try.

I hope somebody can help me out here as I'm really interested in the topic, but somehow stuck.

Thanks in advance!

I had a look at classic transpositioning and substitution methods which lead me to encryptions like Vigenére, Autokey, Beaufort and so on. However, those are designed to work with non-numeric alphabets as far as my understanding goes.

While most classical ciphers are applied to the usual alphabet (without different cases), they are not limited to that. It's perfectly fine to have exactly that alphabet you mentioned. In your cryptanalysis you will most likely use number representations of characters anyway (to use addition and modulo), then it just comes down to ordering the alphabet.

  About the cipher: The Cipher contains [a-zA-Z0123456+] without whitespaces, while some patterns are recurring (same characters are repeating in the same order a few times in the cipher).

If there is structure like this, it's very likely to be Vigenere or something similar, operating in fixed "blocks". The distances from the repeating patterns will indicate the block size, as they are multiples of the blocksize.

  I tried a frequency analysis to see if it's just substituted monoalphabetically sign for sign - without success (many results staying at ~8%, no one above 10%)

If you have the symbols a - z, A - Z, 0 - 6, how can  58 symbols have "many at 8%"? Still, it looks like Vigenere fits.

A few things to consider:

Having different cases can imply, they have an alphabet of 2 * 26 (and then add the numbers), or they just use the case of the plaintext, but that should be quite obvious (the distribution is more even in the first case). Alternatively they could just have used a single alphabet and randomly used upper or lower case.
Focus on finding out the block size first. You mentioned index of coincidence, but I guess you meant the "Friedman test". And you have to keep in mind, that your alphabet might be different than the standard one. Use the actual index of coincidence to find out the block size. As an algorithm, you can also calculate the autocorrelation directly (for shift $i=1,2,\dots$, count the positions where the text and the shifted text have the same symbol). The correct block size (and its multiples) will be a outlier(s) from what you would get from a uniform distributed alphabet (for all the wrong block sizes).

From there on, it's just frequency analysis for each position in the block.


RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime? I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement  "$p+q-1 < 3\sqrt{N}$".
No proof is given for this, and I can't seem to figure out why this statement holds. Could anyone help me figure this out or point me towards the relevant theorems?

There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q<p<2q$.

With that assumption, we can prove the inequality.

We know that

$$p+q < 2q+q$$
$$p+q < 3q$$

Furthermore, since $N=pq$ and $p>q$, we have that $\sqrt{N} > q$, or $3\sqrt{N} > 3q$. So

$$p+q < 3q < 3\sqrt{N}$$

In your inequality, you have $p+q-1$ which is clearly smaller than $p+q$, so everything works out, $p+q-1 < 3\sqrt{N}$.


AES CTR - Counter Management Let ssuppose that we are using AES in CTR mode to encrypt a number of blocks ($x$ bytes each).
How is the current used IV (nonce+ctr) synchronized among both communicating entities?
I suppose that the Nonce can be exchanged in advanced in plaintext. The ctr value can then be appended to each cipher as plaintext. In that way both, sender and recipient can always generate the correct nonce by using the pre-exchanged IV and the appended ctr. Even during the event of packet loss, the received packet can always be decrypted.

How is the current used IV (nonce+ctr) synchronized among both communicating entities?

In CTR mode the counter starts from $0$, therefore one doesn't need to send the initial value in the CTR mode.
$$\text{64 bits nonce}||\underbrace{\text{00000...00000}}_{64 \, zeros}$$

Using the nonce more than one file ( a derived question )

If you want to use the nonce ( yes it is nonce in the CTR mode) in more than one file, then make sure that the counter is not repeated. This can be achieved by encrypting the next file's counter to the previous file's last counter plus 1. I.e., the previous file used the counter from $i$ to $j$ than the next file's counter must be started from $j+1$, and make sure that $j<2^{64}$, and no round to $$0 if it exceeds $2^{64}$.
By using the counter's remaining values, you need to send the start of the counter, too, and store it locally, you and the other side!. One can prepend this, too. Prepending is useful since it is at the beginning of the stream/file.
$$\text{nonce}\|\text{counter Value}\|\text{encrypted Message}$$
Sending the start of the counter doesn't cause any insecurity problem, otherwise, we should already have with the CTR since we all know it starts from 0.
There is, however, a danger to use in this form. During a system failure, you may lose the last value, and instead, you may use the previous values of the counter. This can result in a catastrophic failure of confidentiality since an observer will notice this and they will use the crib dragging technique. This doesn't mean that the AES will be lost, remember the CTR mode is CPA secure. The mitigation is using a new nonce, the best is exchanging a new key with ECDH and use a new nonce.
An interesting case of the danger is if both parties send a new message at the same time with the same counter, nonce, and key value. That is catastrophic! Therefore, if the messaging is in two directions with the same key, nonce, and counter continuation, it is not advisable to continue the counter where it is left. At least, generate a new nonce.
Remember, the CTR mode has many disadvantages with AES, as the lack of integrity and authentication that AES-GCM handles. And the AES-GCM is hard to use instead use ChaCha20-poly1305 where AES is not obligatory.

Updated for answers to comments;

Nonce in context of CTR means that I can use it together with one AES key as lons as a counter value is not used more than once, right? I.e. the combination of (key, nonce, counter) must not be used multiple times. Am I correct?

Yes, see it in this way.
In the CTR mode, the nonce and counter is encrypted with the AES
$$ c_i = AES(k, nonce\|counter_i).$$ Therefore under the same key any repeat of the $nonce\|counter_i$ can result in the crib-dragging attack.

What do you mean with "...more than one file."? I don't get this point. I guess the nonce doesnt have to be used (so only counter), if you are only encrypting one file using a given AES key. However, for each different file we shall use a new nonce (and start the counter from 0 again), if we do not want to establish a new AES key So in terms of the counter and –

I think I've over-read your question about sending the counter. Since the counter always starts from 0 there is no need for sending. It is only necessary if you are using it mode than one file.
The correct usage is using a new nonce for each file. If you don't establish a new key, generate a new nonce, and send it with appended. Make sure that you don't generate the nonce again.


How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field? I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete logarithm problem and find private key $x$. In ElGamal scheme I have $a^x\equiv b\ (mod\  p)$ where $a,\ b\in \mathbb{F}_p$ and in Pollard's Rho Method I have $Q=dP$ where $P,Q\in E(\mathbb{F}_p)$.
So how can I get $P,\ Q$ from $a,\ b$ and, after I get $d$, how can I get $x$ from it?
Is it even possible or am I totally wrong?

In the question you said that $a^x\equiv b\ (mod\  p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups are not isomorphic and your question is wrong.

If $\#E(\mathbb{F}_p)=p$ the curve is called anomalous and we can find the map $\psi :  E(\mathbb{F}_p) \to \mathbb{Z}_p$ in polynomial time. In this state, $a=\psi(P),b=\psi(Q)$ and $x=d$.

The main idea behind Pollard’s rho algorithm is to find distinct pairs $(c' , d' )$ and
$(c'' , d'' )$ of integers modulo $n$ such that $c' P + d' Q = c'' P + d'' Q$. So $(c' − c'' ) = (d'' − d' )d \pmod n$. Hence $d$ can be obtained by computing
$$d = (c' − c'' )(d'' − d' )^{ −1} \pmod n.$$

For more details you can see page $156,168$ of "Guide to elliptic curve cryptography", Hankerson, ....


Standard for asymmetric encryption based on elliptic curves Most parts of public key cryptography has established standards which are in turn used in a large amount of real world applications. There is PKCS#1 for RSA based encryption and signatures and there is DSS for ECC based signatures.

But for some reason, I never came across a proper standardised form of a ECC based encryption scheme. Whenever I look at software trying to use, it usually is some homebrewed El-Gamal variant.

Am I missing something? Or is there a reason for that gap?

There is a scheme called the Elliptic Curve Integrated Encryption Scheme that has been "standardized". It is described in section 5.1 of SEC1v2. It is commonly used with EC to create an encryption scheme.

ECIES is a hybrid scheme that depends on a symmetric cipher (and a KDF and MAC algorithm) to encrypt the actual data. Generally that's fine as EC / ElGamal is very limited in what it can encrypt anyway. It is based on ephemeral-static DH, where the ephemeral private key is only used during encryption. You can see it as a delayed key agreement scheme, followed by data encryption.

There are a few problems that makes it trickier than just plain RSA encryption, disregarding the fact that most people find EC cryptography trickier anyway:

some validation of the public key values may be in order if decryption is automated;
the algorithms for the KDF, cipher and MAC are not standardized, so they need to be established in advance;
the ciphertext consists of multiple parts instead of one: the ephemeral public key and the actual ciphertext + MAC value.

The problem that you have to specify the symmetric cipher yourself is why I put "standardized" between quotation marks: you cannot just say that it is ECIES encrypted and expect the other party to be able to decrypt. The configuration parameters for ECIES - and possibly the parameters of the configured algorithms - need to be described.

The benefit is that the ciphertext is generally somewhat smaller and that the decryption operation is more efficient. It is also much easier to have e.g. 256 bit security for the EC keys: just use 512 or 521 bit ECC key pairs (rather than > 16 Kib RSA keys). Besides that, RSA itself is also used in a hybrid scheme since messages are often larger than the modulus minus the required overhead for the padding (PKCS#1 v1.5 or OAEP padding).


How to verify the AES Key? I'm Encrypting the data using AES-128 bit Encryption. I need to check whether the key is correct at the receiver side. How can I do that?

Suppose At the receiver The user is asked to enter the KEY for decrypting. As far as I know giving a wrong key generates some gibberish data. How can I prevent that and report back to user that the key provided is incorrect?

Use AES 128 in GCM mode. This will generate a tag during encryption. Send that tag along with the ciphertext to receiver. If the receiver decrypts it with the wrong AES key, the sent tag and receiver computed tag will differ. Alert your user that the AES key is incorrect OR that the encrypted data is corrupted.