Why are cryptography algorithms not exported to certain countries? There have been strict laws about the export of crypto software to certain countries. I can understand the intent, but never gauged the fact that there is nothing stopping these countries from developing their own crypto software. So why limit the export?

And in light of the recent NSA revelations, of backdoors being engineered into crypto algos, wouldn't the export of such compromised algorithms have helped to unravel secrets?

Re: "So why limit the export?"

The laws you're talking about are generally part of the laws that control the export of weapons and of dual-use goods. Dual-use goods are things that can be used both for a military and for a civil purpose… cryptography is such a dual-use good.

In fact, the classification as dual-use good is logic when you think about the fact that cryptography was born out of military needs hundreds of years ago.

In the recent decades since World War II, many governments (including the U.S. and its NATO allies) have regulated the export of cryptography for national security considerations. The cold-war era didn't really lift paranoia and security worries of countries worldwide. As late as 1997, NSA officials in the US were concerned that the widespread use of strong encryption could void their ability to provide SIGINT (signal intelligence) regarding foreign entities… including terrorist groups operating internationally.

It's just since the development and public release of asymmetric key techniques and the Data Encryption Standard (DES) in the 1970s, and later the rise of the Internet, combined with the willingness of some to risk and resist prosecution, that eventually made the policy of regulating cryptography impossible to enforce. As a result, it was being relaxed in the late 1990s by the US. Several countries (but not all of them) followed their lead.

Yet, up till today, most countries have unpublished cryptographic protocols and algorithms in place that are considered top secret and are only known to and used by military intelligence and alike institutions.

Re: "…wouldn't the export of such compromised algorithms have helped to unravel secrets?"

From a civilian point of view, that indeed would make sense… and we would make my cipher public according to Kerckhoffs's principle. But you need to consider the question from the viewpoint of a state or country. If you use an algorithm to encrypt and decrypt Top Secret information which - according to your security classification - could endanger your state/country as soon as anyone gets his/her hands on that information, would you publish it?

After all, if you put your military crypto in the hands of the crowd, the crowd (including every adversary) might be able to find a flaw in your crypto. The crowd would most probably tell you by publishing successful attacks all over the internet, but your adversary would most certainly keep his mouth shut to be sure you're not aware he/she is reading everything you've encrypted.

Remember WW2, where the UK could read Enigma messages from a certain point on. They didn't tell the Germans about that for a good reason. Today, a state/country that is able to successfully attack and decrypt another state's/country's crypto would not tell anyone either.

The reasons are simple:

it is an "attack" and therefore it could cause diplomatic issues (up to a war).
the attacking state would lose the advantage of being able to read the attacked state's/country's message without them knowing about it.

No state/country will ever risk a war or risk losing a strategic advantage. And on the other side of the coin, no state/country will ever risk losing the secrecy of it's most valuable, top secret information.

If you dive a bit into the history of diplomacy, secrecy and war, you'll soon discover that states/countries always consider ignoring Kerckhoffs's principle a small price to be paid when it adds another layer of security (through obscurity).

The reason is that — from a military point of view — every layer of security (no matter how small) adds security. Sometimes, the smallest layer of security represents the fine line between life and death.

And for the same reasons, no other state will ever rely on another's crypto to protect it's Top Secret information. Yet, note that doesn't mean the cryptos by NSA and others don't contain backdoors or planned weaknesses in case an adversary should use that crypto. A nation will (most of the time) make sure there is a way to access encrypted information under worst case scenarios… especially when that nation defines such a scenario different than another state (or a regular civilian).


Hard-core predicates: should the adversary be given $1^n$? In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus:

  A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a function $f$ if for every probabilistic polynomial-time (PPT) algorithm $A$, every positive polynomial $p$ and all sufficiently large $n$,
  $$\mathsf{Pr}\left[A(f(U_n)) = b(U_n)\right] < \frac{1}{2} + \frac{1}{p(n)}.$$

However, in the more recent book of Katz and Lindell (2015 for the second edition), $A$ is also given $1^n$. This seems to make a difference, for example for the following exercise:

  Show that any injective, polynomial-time computable function which has a hard-core predicate is one-way.

Under the Katz-Lindell definition of hard-core predicates, this is trivial: given a PPT adversary $A$ which can successfully invert such a function $f$, we construct a PPT adversary $B$ which can successfully compute any predicate $b$ for $f$ as follows. On input $(y, 1^n)$, $B$ runs $x' \gets A(y, 1^n)$ and outputs $b(x')$ if $f(x') = y$ and a random bit otherwise.

However, if $B$ is not given $1^n$, then it is not clear to me that it can determine in polynomial time the correct value of $n$ on which to run $A$. Goldreich also gives this exercise, but adds that "you may assume for simplicity that $f$ is length-preserving", which again makes it trivial.

In general, giving $1^n$ to the adversary seems to make the situation simpler, mainly because it makes the definition of hard-core predicates mirror that of one-way functions more closely, and if we assume (as is common) that $f$ is length-preserving, it is just redundant. I guess my question is: is there currently any consensus among researchers in this regard? Or are the two definitions actually equivalent (in which case I probably need to give in more thought...)?

First note that it is not necessary for $B$ to guess the correct $n$. To see this, you can think of the PPT adversary $A'$ that on input  $(y, 1^{n-1})$ outputs $A(y, 1^n)$. The sole purpose of the input $1^n$ is to allow $A$ to run in polytime in $n$.

However, if the input (i.e., the output of $f$) to $B$ is of size, e.g., a constant $k$, then $B$ can not run an adversary $A$ running in polytime of $n$. But in this case it should not be problem for the following reason.

I assume $U_n$ here roughly means a $n$ uniformly random bits? In that case you have from $f$ being injective and pigeon-hole principle that with high probability (at least $\frac{1}{2}$) $|f(U_n)| \geq n$. I.e., $B$ will be allowed to run in polytime in $n$ at least on these inputs.

EDIT: Note that the above is slight sloppy and simplified argument. You do not strictly need $|f(U_n)| \geq n$, it could be smaller. You just need it to be large enough for $B$ to run in poly time of $n$.


Is it a good or bad idea to include a password's salt in the calculation of a MAC? Say there's a cryptosystem where encryption and authentication of data is done using a key derived from a user-given password using something like PBKDF2. Is it a good or bad idea to include the PBKDF2 salt in the MAC?

In other words, which of these two systems is better?

$$Packet = Salt + IV + Enc(Data)$$
$$Output = Packet + MAC(Packet)$$

Or

$$Packet = IV + Enc(Data)$$
$$Output = Salt + Packet + MAC(Packet)$$

Assuming $Output$ is the value being transmitted.

A real system like this would obviously be more complicated. This is just to give a rough idea of what I mean.

One argument for this is that it prevents the salt from being modified without notice. But you already get this from the salt deriving the MAC key.

One argument against this is that it allows for a piece of the MAC'd data to have influence on the derived key to calculate said MAC. But this shouldn't be feasible to attack given good KDF and MAC functions.

Which is better? Is there a difference?

It seems unwise to give an attacker enough information to run an off-line attack against a password even if you're using a good PBKDF. PAKE would probably be better.

Assuming you have a strong key your question still holds. I interpret it as:

Given a key $k_1$ and a salt $r$ you derive $k_2 = KDF(k_1|r)$. You then send $m, r$ and $MAC_{k_2}(m|r)$.
Is it safe to do this given that a change to $r$ will change both $k_2$ and $m|r$ or is there a chance that $MAC_{k_2'}(m|r') = MAC_{k_2}(m|r)$?

And my answer is, there is no chance of that happening because it would constitute a forgery. Given a good KDF $k_2'$ will be indistinguishable from random so a valid MAC for anything under that key including $MAC_{k_2'}(m|r')$ would be a forgery.


Would adding more rounds to AES increase security? As the title states, would increasing the rounds by doubling them to Bruce Schneiers recommendation of 16, 20, and 28 increase security? And how much?

As a bit more, would increasing rounds, keys, blocksize, or almost everything increase security?

Would adding more rounds to AES increase security?

Not really.

The cheapest known attacks on AES today are essentially generic key searches.  That is, they don't really depend on the details of AES itself.  If you increased the number of rounds, that would slightly raise the cost of testing each key, but it would also raise the cost of using your AES variant.  Raising the number of rounds doesn't meaningfully affect the cost of generic key searches.

With fewer rounds, there may be shortcuts to attacking AES that do depend on the details of AES itself.  But the number of rounds we settled on two decades ago seems to have held up quite well.  If someone suddenly came up with a new brilliant idea for a cheaper-than-generic attack on AES that eluded the world's best crypanalysts for two decades, maybe more rounds would thwart that, but that's all.

  As a bit more, would increasing rounds, keys, blocksize, or almost everything increase security?

In principle, assuming no specialized attacks, increasing the key and block size does increase security in the following senses:

The cost of an attack on AES-128 can be much less than $2^{128}$ AES evaluations—specifically, an adversary attacking a batch of $t$ different AES keys need only spend cost proportional to $2^{128}\!/t$ to find the first key.

That's why you should use AES-256, not AES-128, for a ‘128-bit security level’ against all adversaries (including quantum adversaries).  This one is an easy choice for you to make.

(If AES-256 is too costly in software, maybe you should use Salsa20 or ChaCha instead, and really an authenticated cipher like crypto_secretbox_xsalsa20poly1305 or ChaCha/Poly1305, which as a bonus avoids timing side channels that plague software implementations of AES.  But you should also measure measure measure.)
The block size of a permutation like AES affects the birthday bound for protocols, which is why Sweet32 hurts 64-bit block ciphers much more than 128-bit block ciphers no matter what the key size is—an adversary's advantage at breaking an application that handles $q$ blocks of data of $b$ bits apiece is usually around $q^2\!/2^b$.  A 128-bit block size makes Sweet32-type attacks much harder to pull off.  But the birthday bound of around $2^{64}$ blocks is still within the realm of feasibility—for example, the Bitcoin network today computes more than $2^{64}$ SHA-256 hashes every second.

If AES had a 256-bit block size, then the birthday bound would be around $2^{128}$, which is so large you never have to worry about it.  But it doesn't.  The original Rijndael proposal supported 256-bit blocks, but they weren't included in AES as adopted by NIST.  There's no easy choice you can make here without using a nonstandard AES variant that has received relatively little scrutiny—which means it is more likely to have specialized attacks cheaper than generic key searches that we don't know about.

(Again, maybe consider using crypto_secretbox_xsalsa20poly1305 or ChaCha/Poly1305 so that you don't have to worry about the AES block size either!)


When is the public ECC key generated? I have been learning about the fundementals of ECC and I'm a bit confused on this point: What makes up the public key in an ECC key exchange, and when is this public key generated?

In the video at https://www.youtube.com/watch?v=F3zzNa42-tQ and the StackOverflow Q&A Basic explanation of Elliptic Curve Cryptography? , it is stated that the public key is generated when the key exchange takes place. The public keys are the Generator point "times" the private key of each party. Because the Generator point changes for each handshake, the public key must not be generator beforehand.

If this is the case, then what is the purpose of ever generating an ECC public key? For a project I am working on, it is necessary to generate a public key to be placed in a certificate signing request to connect with AWS. Also, there is openssl functionality for creating ECC public keys:

  openssl ec -in ecc_private.pem -pubout -out ecc_public.pem

Is the word "public key" being loosely used? Are there multiple public keys?

As already indicated in the other answer $A$ and $B$ in the video are the public keys of Alice and Bob. The public keys are part of the key pair generation by each one of the parties, usually denoted $\operatorname{Gen}$. With ECC the keys can be generated from the private key at any time, as the public key is generated after the private key within the $\operatorname{Gen}$ function, namely by multiplying the private key value with the base point $G$.

The base point is part of the domain parameters agreed upon by client and server during the handshake and is not expected to change for ECDH. When performing ephemeral-ephemeral key agreement a key pair is regenerated by each party. In that case the key agreement does not perform authentication of any party as the public key cannot be trusted by the other party; authentication is performed separately. That authentication could be performed using any means, including ECDSA with a different, static key pair. In that case the static public key is commonly within a certificate signed by a certificate authority.

What you are generating is a static or key which has the life time displayed in the certificate (after which it isn't trusted anymore, it doesn't self destruct). That key is still just the the private key $s$ multiplied with $G$ of the domain parameters. This is a deterministic calculation: there is therefore only one public key per key pair. The parameters used for this key can be different from the parameters used for the ephemeral key pair used for key agreement; the parameters are indicated by the encoding of the public key in the certificate.

So no, the term "public key" is not used "loosely" here.

There is also ephemeral-static and even static-static Diffie-Hellman, although neither of them is often used. In that case the static public keys can be part of a certificate and trusted. So the entities holding the static keys are then authenticated. A party with an ephemeral key pair isn't authenticated and may need to log in, in case it is a website user, for instance.

As indicated, this isn't used as much; ECDH certificates are not commonplace and static Diffie-Hellman doesn't offer forward secrecy - the session data will become known if the confidentiality of the static key is compromised.

You're generating a static key pair which can be used for authentication. When using a ECDHE ciphersuite you'll need to generate a ephemeral key pair as well, but this is hidden in the TLS implementation. Fortunately generating ECC key pairs is relatively fast: just randomization and point multiplication. This is one of the main benefits of using ECC.


MAC algorithm difficulties Can anyone explain to me why this is a bad idea? I cannot see anything wrong with it except that key K should be different for MAC and AES.

MAC algorithm consists of letting the MAC of message M
(which consists of message blocks M1,M2,... ,Mn) be the AES encryption with key K of the XOR of all the message blocks.

i.e. MACK(M)=EK(M1 XOR M2 XOR ... XOR Mn)

It's trivial to calculate collisions because the message blocks M1..Mn can be interchanged without issue. So EK(M1 XOR M2) = EK(M1' XOR M2') where M1' = M2 and M2' = M1. Different messages should obviously not calculate to the same MAC authentication tag.


Length of message in RSA and splitting of long messages If I understand correctly in (unpadded) RSA the length of message M must be shorter than modulus n.

Encryption gives ciphertext that is also shorter than n.

Let's say I want to send a message of 2.5x length of n.

Is the split of message into chunks inferred somehow, or is that encoded somehow within ASN.1 keys? What are the different options/standards for this?

EDIT: Probably RSA is not used for messages longer than n but symmetric keys are generated with RSA and then they are used for longer messages?

Yes, hybrid crytography is generally used; hybrid crypto combines asymmetric cryptography with a fast symmetric cipher to do the bulk of the work.

Either the keys are generated using RSA-KEM (and a Key Derivation Function) or - and this is much more common - a random symmetric key is encrypted using RSA with PKCS#1 padding or the more secure OAEP padding - the key encapsulation talked about in the Wikipedia article.

Messages are usually not split at all; most cryptographic libraries do not directly support concatenating blocks of RSA ciphertext. That is not a standardized mode of operation for RSA.

Keys are not specific to the RSA mode used (just like you can use an AES key for about any kind of mode, ECB, CBC, CTR etc.). Sometimes X.509 certificates do contain a specific signature generation / verification algorithm to be used, but the key is usable for any RSA based algorithm.

Notes:

With most RSA modes for encryption the padding which is required to make RSA secure introduces overhead. The ciphertext will be of the same size as the modulus (in bytes), but the amount of plaintext that can be encrypted is reduced by at least 11 bytes for PKCS#1 v1.5 padding and even more for the OAEP padding modes. Of course for any secure RSA key size there will be plenty of room for a symmetric key - or even an IV, encryption key and authentication key if the protocol requires it.
The message (+ padding overhead) can be of the same size as the modulus, as long as the numerical representation of the input to the RSA modular exponentiation is smaller than the modulus. Otherwise the modular reduction will be performed on the input, which means you would get a value that is one or more times the modulus smaller than the input. RSA modular exponentiation is about numbers, not bits; there are special functions called OS2IP and I2OSP in RSA PKCS#1 to convert between binary and number values.


Is RSA with SHA1 broken? I am using CryptSignMessage to sign a string/file. Is using RSASha1 insecure?

I know Sha1 is broken as a hashing algorithm, but does that also mean that using it for signing with RSA is broken?

To start with, it's certainly not a bad idea to avoid SHA-1 when other algorithms exist, which do not have the SHA-1 weaknesses to anyone's knowledge.

The security of SHA-1 depends on how you're using it. The vulnerability is what's known as a collision vulnerability: an attacker has the ability to create two input strings with the same SHA-1 hash with less computational power than it should take him for a good hash function. However, he does not get to freely pick what either of those input strings is, and he does not necessarily have the ability to feasibly find a string whose hash matches that of any particular string.

If the attacker has any control over anything you're willing to sign, collision attacks might be exploitable. The classic example is two PostScript files; one is a letter of recommendation for an employee named Alice, the other a security clearance for Alice, and they hash to the same MD5 value. Alice presents file 1 to her boss, and then affixes that signature to file 2, now having obtained a security clearance. Likewise, with TLS certificates, security researchers made 2 colliding-under-MD5 certs, one a legitimate one and one a CA one, got the former signed by a real CA, and that signature was valid for the latter. What these have in common is that someone is signing off on something that they did not entirely create. If that describes what you're doing, you should certainly not use SHA-1.

If you entirely create the files you're signing, it's probably fine for now; in that case, the only person who could exploit a collision attack is you, and you're the person who doesn't need to exploit it (you could just sign whatever you want). Also, as far as anyone's aware, no one yet has the hardware to exploit the collision attack (that's likely at least a year off, and more till it's cheap enough for non-high-value targets).

But honestly, why risk it? Just use SHA-2 instead. CryptSignMessage supports it as well, it looks like.


GPG & Mcrypt - difference? in short I'm learning GUI programming in python and thought it could be interesting to make a small GUI for symmetric encryption. Not being mad/mathematical/experienced (take your pick) enough to try to implement ciphers myself I figured I could create a GUI that just sits on top of an existing program (on Linux). So I found gpg and mcrypt.

I have been googling like mad but finding very little information about mcrypt other than it is "a replacement for the old crypt program in Linux". Also mcrypt seems to list Rrijndael in stead of AES (so guessing it is the Rrijndael cipher rather than the AES implementation of it?)

Now, save that mcrypt has an implementation of Serpent and gpg comes with the ability to sign/verify the encrypted file, is there any great differences or advantages/disadvantages to one or the other? currently finding mcrypt fascinating.

Any thoughts would be appreciated.

GPG is an implementation of OpenPGP, which is a higher level protocol than e.g. mcrypt. So use GPG for PGP compatibility and mcrypt or related libraries for more direct - lower level - access to algorithms.

AES is Rijndael for a block size of 128 bits and the 128, 192 or 256 bit key sizes. So you are OK there. Learn about modes of operation and something about key management before creating the GUI. Possibly take a look at Password Based Key Derivation Functions such as PBKDF2 if you want to use a pass phrase.


What is the major difference between FIPS 186-2 and FIPS 186-4? Can anyone please tell me the major difference between FIPS 186-2 and FIPS 186-4?

I know with FIPS 140-2 they want the DSS standard to be FIPS 186-4, but what difference does it make?

To clarify scope:

FIPS 140-2 itself doesn't say anything about DSS, though it has 186-2 as a reference. It was published in 2001, before 186-3 and -4, and has not been superseded. After 140-3 spent 8 years in draft they recently decided to consider using ISO/IEC 19790 instead!
140-2 Annex A (Approved functions) is updated frequently and does now reference 186-4.
most people don't want just 140-2 implementation but rather 140-2 certification under the Cryptographic Module Validation Program (CMVP) and that is controlled by the 140-2 Implementation Guidance linked at that page (currently and usually under 'Announcements' because it keeps changing, and always in 'Standards').

The current IG has a section on 'Validating the Transition from FIPS 186-2 to FIPS 186-4' in W.2; formerly it was G.15. As indicated there, the technical changes between 186-2 and -4 were, if I haven't missed any:

delete several specific RNGs and instead require RBGs Approved by a separate standard, currently SP800-90A
DSA: add cases for $p$ size 2048 with $q$ size 224 or 256, and 3072 with 256, using hashes from FIPS 180 (now SHA-224 SHA-256 or SHA-512/224 SHA-512/256). Note 186-2 change notice 1 already eliminated $p$ sizes below 1024 which were in -0 through -2 original.
DSA: expand the parameter generation algorithms to prefer Shawe-Taylor provable primes while still allowing Miller-Rabin with optional Lucas probable primes, and use a strength-matched hash; explicitly specify parameter validation (including legacy parameters using the -2 and earlier method) which had been implicit
DSA and ECDSA: more robust privatekey and $k$ (nonce) generation
RSA: allow RSA signature schemes PKCS1-v1_5 and PSS from PKCS#1v2.1 (with a constraint on salt for PSS) in addition to previous X9.31. Note these were already Approved in 140-2 Annex A, so this just moves them to the correct place in the document set.
RSA: restrict $n$ size to 1024 2048 3072, restrict $e$ to $2^{16}+1$ to $2^{256}-1$, and specify RSA privatekey generation in detail with several options. This prohibits one traditionally popular $e$ namely 3; F4 (65537) is allowed and IME more popular anyway.

There were also major editorial changes between 186-2 and -3, reorganizing some things, changing notation, and adding a lot of explanation about what digital signatures are and aren't good for, and why privatekeys must be private, and so on. I'm not going to try to cover all that; get the docs and read for yourself if you want.


Is there a way to find $a$ and $b$ keywords in an affine cipher when only ciphertext but no plaintext is known? I know simple formulas like

$$E(x) = (ax+b)\pmod n$$

where $E(x)$ stands for encryption,

$$D(y)= z(y-b)\pmod n$$

where $D(y)$ stands for decryption,

and

$$ax==1\pmod n$$

Assuming someone gives us an encrypted string, is there a way to find $a$ and $b$ from that string? If not, what informations we should have to find $a$ and $b$ keywords from the encrypted string? Is there a way to find a and b keywords in an affine cipher when only ciphertext but no plaintext is known?

Note that this is not a duplicate of Affine cipher: calculate the key from a known plaintext/ciphertext pair. In that other question, the user knows beginning of both encrypted and decrypted message.

There are several ways to break an affine cipher without any known plaintext.

First of all, for the common case of $n = 26$, there are only $12$ possible values of $a$ (since $a$ and $n$ must be coprime) and $26$ possible values of $b$, for a total of $312$ possible keys.  That's small enough that you can easily test all the keys and simply inspect the results to find the most plausible plaintext.

Even if the alphabet size is larger (say, $n = 256$) you can let a computer try all possible keys and use statistical frequency analysis to sort them by plausibility.  Manual inspection should then let you pick out the correct plaintext from among the few dozen ones rated most likely by the statistical test.  Of course, to set up the frequency model, you'll need to have some idea of what the plaintext might be (e.g. English text, executable binary code, base64-encoded data, etc.) and it must not be too random-looking.

More generally, an affine cipher is a type of monoalphabetic substitution cipher, and so any techniques that can break general monoalphabetic substitution ciphers (such as manual step-by-step frequency analysis) can certainly also break an affine cipher.  Also, many techniques that work on simple Caesar shift ciphers can also be adapted for affine ciphers.  For example, you could try:

Simple frequency analysis: Find the two most common ciphertext symbols, and guess that they correspond to the two most common letters in English (E and T).  That should give you a system of linear equations that you can solve for $a$ and $b$.  If the results don't make sense, try switching the letters around; if that doesn't help, try the next few most common ciphertext symbols and/or the next most common English letters (A, I and N).
Crib dragging: Guess a word of two or more letters that likely appears in the plaintext, and try matching it with different parts of the ciphertext.  Common words like "the" are particularly useful here: if the plaintext is supposed to be English, and there's a particular sequence of three symbols that occurs often in the ciphertext, there's a pretty good chance that it decrypts to "the".  Conveniently, since "the" has three letters, you get a system of three equations and two unknowns, so you can check it for consistency before even attempting actual decryption.


Point-at-infinity and error handling I'm looking at a piece of (non-object oriented) code where functions return point-at-infinity for a specific prime curve if a calculation errors out. This is even the case when validating arguments to the functions; obviously the point-at-infinity is used as a "magic value" (comparable with returning nil when a function fails).

Can I assume that each and every one of the occurrence of point-at-infinity is actually an error in the code itself? Should I just create an error each time I find point-at-infinity?

Or, if above is not the case, are there any valid EC calculations that may result in point-at-infinity? If yes, what would be an appropriate action when this occurs? Does it make sense to validate each time that a function never returns point-at-infinity (assuming that I get rid of the code-generated point-at-infinity return values, of course)?

This would of course depend on your protocol and or algorithm, so it's hard to give too specific advise without details of those.

Returning the point at infinity is not necessarily an error. The usual scenario would be a point $P$ of order $n$, and some secret scalar $k$. You would want to choose $1\leq k\leq n-1$, so that $k\cdot P$ will never end up being at infinity. However, one common scenario is side-channel sensitive implementation, where we would want to blind the scalar $k$. That is, we compute $(k+\lambda n)\cdot P$ for some random $\lambda$. The result will be the same, since $P$ has order $n$, but in this scenario you could run into the point at infinity at some intermediate step.

Another case would be a computation of the form $k_1 P+k_2 Q$, which is commonly done in signature verification. Also here it is not true that you never run into the point at infinity. A more general case of this would be when you start using endomorphism-based routines. Essentially the more complex the algorithm, the harder it is to prevent running into the point at infinity.

Note that for large primes, this will never happen (that is, it is extremely unlikely). However, there may be scenarios where an attacker can control input. In that case it is possible to force the algorithm to end up at the point at infinity, which may be exploitable.

How would you deal with this? It depends. If a 30-50% slowdown is not of crucial importance (I'd argue it rarely is), then there are complete formulas. These work even when you input the point at infinity. It is well-known for Edwards and Hessian curves, but a rather recent result shows that you can also do this on prime order curves. This would solve all your problems.

If you don't want to do this, you'd have to take a close look at your protocol. Is there any possibility of a scalar becoming larger than the order of a point? Is there any point where the attacker has influence on the input data? If so, is it exploitable?


RSA: must $d$ be an integer? I am only taking baby steps in RSA.

If $p=11$, $q=7$ and $e=3$,

$$\phi(n) = 10*6 = 60$$

Then:

$$d = (2 (\phi(n)) + 1 ) / 3 = 121/3$$

Should $d$ be kept as a non-integer or is such a $d$ invalid?

$d$ must indeed be an integer.

To calculate $d$ you need to calculate $d=e^{-1}\bmod{\phi(n)}$ which is called the modular multiplicative inverse of $e\bmod{\phi(n)}$. For $d$ be computable you need to ensure that $$\gcd(e,\phi(n))=\gcd(e,(p-1)(q-1))=1$$

holds, which isn't the case with your sample parameters as $\gcd(3,60)=3\neq1$.

As fgrieu pointed out in the comments you can find the private exponent by finding the smallest $k$ for which $(k\cdot\phi(n)+1)/e$ is an integer. The run-time of this approach likely will grow linearly with the size of the $e$ value which is in the order of $2^{16}$ usually.

Of course $k$ isn't unique unless you take the smallest possible $k$, meaning there will be other (larger) values of $k$ yielding a valid decryption exponent.


When knowledge soundness implies soundness In the work of Bellare–Goldreich that defines knowledge soundness BG92, the discussion of Section 4.5 specifically decouples knowledge soundness from soundness. That is, proving knowledge soundness for some verifier $V$ says nothing about the soundness of some pair $(P^*, V)$, for arbitrary (cheating) prover $P^*$.
However, in various works, notes, and related notions, knowledge soundness is taken to imply soundness.
In Lin03, arguments of knowledge are defined in Definition 9, and in the discussion below are said to directly imply soundness error at most the knowledge error.
In GI08, their particular notion of Witness-Extended Emulation, a more robust notion of knowledge, implies soundness.
Finally, in the notes of Bar07, the definition of knowledge soundness given is said to imply a soundness error at the most the knowledge error, just as in Lin03.
The one thing all the above examples have in common, which also differs from BG92, is that they restrict the class of provers $P^*$ against which knowledge soundness is proven for $V$ to at most expected polynomial time.
Intuitively, this seems like it should be the reason for knowledge soundness implying soundness, especially in light of the discussion in Lin03. Can anyone give a more a explicit answer about why Section 4.5 of BG92 is not relevant in these cases?

The difference is that in Section 4.5, knowledge soundness (i.e., extraction) is required to hold only for every $x\in L_R$, and so there is no requirement at all for the case that $x$ is not in the language. In contrast, in Definition 9 of Lin03, the knowledge soundness (i.e., extraction) is required to hold for all $x$. This implies soundness since you cannot extract a witness for $x\notin L_R$, and so the verifier cannot accept in this case (except with probability of the knowledge error).
Note that this is orthogonal to the question of whether or not $P^*$ is efficient (i.e., whether it's a proof versus an argument).


where should private and public keys be stored? I am kind of confused whether should a newly generated key pair be stored in a keystore or in just a normal plain text file?

From what I read from online source, there are serveral explainations about what the keystore actually store.

some says it stores the certificates only while some says it stores the key pair as well as the digital certificates.

and if the answer is storing in a normal plain text file, won't that be insecure?

You should keep the private key as safe as possible. How safe depends on the security requirements and risk assessment. A key store, such as a PKCS#12 key store or Java key store enables you to store a key protected by - usually - a password. This is obviously more secure than storing it as plaintext at the same location.

It is possible to mitigate the risk of storing in plain by using e.g. a thumb drive as storage device, and only use the storage instead.

Another form of key store may be present on a device such as a TPM, a HSM or smart card. Such devices usually protect against dictionary and brute force attacks by minimizing the attack surface - e.g. by blocking after a maximum incorrect log in attempts.

A key store may contain a certificate chains for private keys of the user, but it may also store trusted certificates. Trusted (root) certificates are for instance used to create TLS connections from your browser to websites. TLS can also be configured to use client authentication; in that case the key store contains both the private key + certificate chain and trusted certificates.

If a key store just contains certificates then it is usually called a trust store instead.

Use a key store if you can, especially those provided by the runtime system. A runtime system can often make use of lower level security mechanisms and provide a higher level of trust than mere applications can.

Note that some API's such as Microsoft .NET  act as if private keys are part of a certificate. They are not; although the public and private keys are part of one key pair, the private key and certificate are distinct. In Java the (E)JKS key stored contain a private key and certificate chain per key entry but they are retrieved separately.

These key stores are not really generic, they have been build for X509 compatible PKI (as used in browsers).


Hashing Algorithm Integrity Validation I am developing an application that will need to store a very large volume of hashed data per user for which I want to ensure I am doing everything possible to maximize security.  At this point I believe I will be utilizing SHA3-512 + randomized salts over a yet-to-be determined number of iterations.

Is there a standard application level accreditation that exists to verify the security of my data encryption methodology, or is FIPS the only prevailing authority on encryption standards?

While there are no prevailing private entities associated with the accreditation of security standards, the NIST does provide the Cryptographic Module Validation Program that "validates cryptographic modules to Federal Information Processing Standards (FIPS)140-1 Security Requirements for Cryptographic Modules, and other FIPS cryptography based standards.." (http://csrc.nist.gov/groups/STM/cmvp/index.html)

As I understand it, one could seek the status of a Validated FIPS Module via an NVLAP accredited Cryptographic and Security Testing (CST) Laboratory.

"Cryptographic modules are tested against requirements found in FIPS PUB 140-2, Security Requirements for Cryptographic Modules [ PDF ]. Security requirements cover 11 areas related to the design and implementation of a cryptographic module. For each area, a cryptographic module receives a security level rating (1-4, from lowest to highest) depending on what requirements are met." (http://csrc.nist.gov/groups/STM/cmvp/standards.html)

As such, one could leverage the FIPS security level validation from the NIST to publicly validate the security of their solution.


How to "score" partially decoded ciphertext? I am attempting to write a basic codebreaking program to break simple ciphers (think caesar cipher & railfence) such as these here https://en.wikipedia.org/wiki/Classical_cipher.

The program will make semi random attempts at decoding the ciphertext, and I need a way to "score" these attempts on how close they are to fully decoded plaintext.
For example "hello world" would score higher than "Kello woHld" or "aellp wprld" which would both score higher than "KRYYP ZPHYI", thus the program can use a hill-climbing or similar method to converge on decoded text.

I am unsure how to score text, perhaps using a dictionary (+regex?) to check for decoded words, or counting occurences of common letters and common groups of 2,3 & 4 letters, then perhaps comparing to known frequencies.

I am not asking for a finished algorithm, just some pointers of how to score text on its "decodedness" / closeness to plaintext.

Edit: I am working with ciphertext 500 to 1000 characters long, would like the system to work with or without word boundaries preserved.

You are looking for a way to measure the similarity between strings, which is usually refered to as string metric. Now in your case one of the strings is the original plaintext and the other is a (more or less) similar string generated by encrypting and decrypting only partially correct. But actually, it doesn't really matter where the other string comes from, you just need to measure how similar they are.

However, there are many string metrics, and it's possible to adapt them to your specific needs. Here are a few common ones:

Hamming distance: Number of mismatching characters
Levenshtein distance: Number of insert/delete/substitute operations

There are countless other ways to measure the similarity between strings, and it has to be determined what is considered similar and what isn't.


How relevant are hardware implementations of crypto algorithms? All of the SHA-3 finalists discussed speed and efficiency of a hardware implementation of their algorithms. How relevant are such details?

I'm curious about who commercializes hardware that implements specific hashing algorithms, and who uses them. In what situations is this worth a dedicated chip, vs. just running it through the CPU / GPU / whatever?

Hardware implementations are common, and likely to become more common as security needs increase, rather than less common.  One place they're used is in the digital signature of messages, such as messages going to/coming from a Smart Card used for banking.  Those are tiny, slow, limited processors, and a hardware implementation has the potential to improve their performance.  Americans aren't used to the slowness that Chip and PIN will bring to the checkout experience, so anything that speeds up that process is going to be of great value.

Security is also becoming more critical for other embedded devices.  Smart homes use secure communications to tell door locks to unlatch, and alarms to disarm.  And in any battery operated device, such as an alarm sensor, power efficiency is often the top requirement.  If a hardware implementation saves a few milliwatts, that could extend the life of a battery in an alarm sensor by a month, which is a huge benefit to the homeowner.

With all the talk of cyber-terror attacks on Industrial Control Systems, the individual controlling hardware devices may soon need to validate signatures on each instruction they receive.  They need extremely fast response times to perform real time controls of manufacturing equipment, and must be able to quickly process an emergency shutdown request.  Encryption and authentication is always a bottleneck, so a high speed hardware implementation could help maintain near-real-time response times.  Look for those algorithms to be baked into the communications chips.

At the other end of the computing spectrum, giant web servers use HSMs to perform the encryption and decryption of thousands of https: sessions per second.  Dedicated hardware implementations make such devices far more efficient than general purpose CPUs.

In the middle, you have PCs and laptops, where encryption on the CPU is fast enough for the end users, and the performance benefits of hardware implementations is negligible.  But they're also the most subject to malware like viruses, and embedding the security features in a chip could prevent malware from accessing sensitive data like private keys.  (If TPM wasn't all about enforcing DRM and other forms of rights restrictions, it might have been useful for actual security functions.)


Engima machine decoding with PC and GPU I saw this answer at this site about decoding a 3-rotor Engima machine's settings:

How cryptographically secure was the original WW2 Enigma machine, from a modern viewpoint?

And did some math for the decoding method in the highest ranked answer:

$2^{20}$ * $2^{19}$ * $2^{9}$ * ("run Index of coincidence as statistical test again, deriving of the trigram information of the underlying language")

To get an estimate of the number of operations to be 281,474,976,710,656. Googling Nvidia GTX 480 graphics card says that it can do about 1.3 teraFLOPS, so I got about 4 minutes as an estimate for running the decoding.

My question is approximately how many minutes would it take to decode a few sentences of text encrypted with a 3-rotor Engima machine simulation with a PC with a GTX 480 GPU without a crib with this index of coincidence method? I'm guessing maybe 10 minutes?

I haven't found a GPU based solution online yet and am hoping reinventing this wheel won't take too much effort to code and run.

Seen this? http://www.cvnguyen.ngocnga.net/tech/enigma/

This guy seemed to have it working on GPU back in 2009


Why is DES not an ideal cipher? From Cryptography I on Coursera, Week 2, "Exhaustive Key Search Attacks":

  Now let's assume that DES is what's called an ideal cipher [...] Of course,
   DES is not a collection of 2^56 random functions

Prof. Boneh doesn't offer any explanation of that, he mentions that in passing like something obvious. But why exactly DES is not an ideal cipher? Is it simply because there are no ideal ciphers at all?

And a follow-up question, if DES is not a collection of 2^56 random permutations, then how many permutations does it actually offer? And how do I calculate that number?

DES uses a 56-bit key (formally, a 64-bit key, out of which 8 bits are simply ignored), so it represents a family of exactly $2^{56}$ permutations(*).

If you were to select a permutation at random among all the permutations of a space of 64-bit blocks, then there are $2^{64}!$ such permutations, a truly huge number, and you would need, on average, $\log 2^{64}!$ bits to simply represent such a permutation, i.e. about 144 billions of gigabytes. Now, DES for a given key can be represented in a much more compact way (the code that executes DES fits in a couple of kilobytes, and an extra 56 bits for the key). In that sense, DES selects permutations out of the very very few (relatively speaking) that can be represented in a few kilobytes of code.

If you prefer, if you have a computer with a budget of 2048 bytes for code and data, then there are at most $2^{16384}$ possible programs for that computer, that can thus represent only $2^{16384}$ different functions (most of them won't actually run or do anything useful, and even for those whose execution terminates, most won't be permutations of a given space of 64-bit blocks). $2^{16384}$ is already a mind-bogglingly large number, but it is insignificantly small compared to the number of permutations over 64-bit blocks, which is about $2^{1153978594521722658473.7}$ (I computed that with Stirling's formula).

An "ideal cipher" is supposed to be a family of permutations, such as each key represents a random choice among the whole set of possible permutations. That set is immense. Concrete block ciphers, in order to be actually implementable, must necessarily be restricted to a very small subset of such permutations, i.e. the one for which there can exist some code that implements them within a given budget. In that sense, no concrete block cipher can be "ideal".

(*) To my knowledge, it is not proven that all of them are distinct; however, it seems improbable that any two match exactly.


Recommended password complexity for SSH key encryption using AES-256-CBC When protecting SSH private keys with password-based encryption, what would be a good minimum password complexity+length standard to make cracking the password too difficult to be worthwhile anytime in the near future if the key got stolen / disclosed somehow.

For the purposes of this question, the private key is a 2048 bit RSA key (I don't think that matters for this question but FYI in case there's some relevance I'm not aware of), and it's being encrypted by AES-256-CBC.

I'm assuming of course the key isn't getting stolen by a computer being hacked to a degree that a keylogger could just be installed but rather for example being stolen by some vulnerability like the recent Firefox pdf.js vulnerability that was being exploited in the wild and looking for SSH keys.

Both the AES key size and the RSA key size matter, because it's no use adding security beyond the weakest link. Here the weakest link is 2048-bit RSA, which is considered roughly equivalent in security to 100-128-bit symmetric keys (depending on who you ask). So having a password with much more than 100 bits of entropy would be fairly useless.

In practice, it depends on how much you value your security. 80 bits is enough to be secure against most, but a large adversary like NSA might be able to crack it if they put enough resources to it. 100 bits should be secure against anyone for several decades at least.

For what that means in practice, some examples:

80-bit password: 14 random alphanumeric characters (upper and lowercase).
80-bit passphrase: six diceware words.
100-bit password: 17 random alphanumeric characters.
100-bit passphrase: eight diceware words.

However, there's one important fact missing here: key derivation. The AES-256 key must be derived from the password, and with a good password hashing function this effectively adds "computational entropy" to your password choice. Unfortunately, the default for SSH is still, as far as I can tell, a non-iterated KDF that adds nothing.

If you choose to use the stronger (PBKDF2-based) format (Google should help you), you can add 10-20 bits to the password security, depending on the number of iterations. That means you can skimp a bit on password length or just accept the extra security.


How can fully homomorphic encryption ever be secure? Perhaps I am misunderstanding FHE, but from my knowledge, an FHE system is theoretically capable of arbitrary computation. Since this is theoretical talk, let's forget the practicality of actually implementing that today.

A common use case of FHE is secure cloud computation:

1. Encrypt M, call this E(M)
2. Send E(M) to cloud to compute f(E(M)), where f is some arbitrary computation
3. Cloud sends back result and we decrypt to get f(M)

In principle, the cloud never knew M or f(M) as it only operated on ciphertext.

Now my question is: Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M. What part of FHE prevents the cloud service from doing this?

Interpreting the question

Firstly, I should state that I interpreted

  "Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M"

to mean something equivalent to

  "What if the cloud service uses the homomorphic properties of the ciphertexts to evaluate a search algorithm which outputs True if the searched substring is contained in the message, or alternatively outputs the matched substring, or returns any arbitrary information about the message. Why can't they abuse this feature to find the message?"

I mention this up front because there appears to be confusion about what exactly the question is asking. This answer will assume that the unspecified homomorphic encryption scheme fulfills its promise of data confidentiality, which for a fully homomorphic scheme, includes evaluating arbitrary circuits while revealing nothing of the plaintext value without evaluating the decryption circuit. Obviously, this does not extend to constants introduced during the evaluation that are created by the service provider via the public key (which they only know because they created the ciphertext).

Answer

With homomorphic encryption, the data is confidential to everyone but the key holder. Anyone can manipulate ciphertexts and evaluate functions on them, but they cannot decrypt the ciphertexts to obtain the result.

What part of FHE prevents the cloud service from doing this?

So the answer is that nothing prevents the cloud service provider from computing a search on the encrypted data - it may compute the search, but it cannot decrypt and view the result of the search. This is because the output of the circuit that is computed is also a ciphertext. The cloud service provider may compute any circuit it wants (assuming the scheme supports it), but the output will always be a bunch of random noise as far the cloud service provider is concerned.


Predicting values from a Linear Congruential Generator I have learnt that Linear Congruential Random Number Generators are not cryptographically secure - my understanding is that given an LCG of the form:

X_n = (aX_(n-1) + c) mod m

It is possible to predict future X_n given a number of past X_n (even without knowing a, c, m).

In most implementations however there are a couple of complicating factors:

The values returned usually hide a certain number of the least significant bits of X_n
In most cases the values are returned modulo a small integer p.

So rather than the internal states themselves we often have only the high order bits modulo p of each state.

My question is: is it tractable to predict future values given a number of past values with these restrictions - with proof?

I have found this paper by J. Boyar, from what I can work out it only considers point (1) though.

edit

@fgrieu has shown that is is indeed quite trivial if we know a, c and m and m is a power of two. I'm still interested if there is a more general solution.

This answer relates to an earlier variant of the question, which at one point gave an example problem with a, c, m known, as follows:

  Consider the following in Java that prints 100 random numbers from 0 to 5:

  Random r = new Random(); // seeded by system time
  for (int i=0; i<100; i++) System.out.println(r.nextInt(6));

  where r.nextInt(6) is essentially the following:

  seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
  // i.e. seed = (seed * multiplier + addend) $\bmod 2 ^ {48}$

  int bits = (int)(seed >>> (48 - 31));
  return bits % 6;

Yes, it is possible to predict the output of that Linear Congruential Generator variant from its first outputs. For a start, the only unknown is the original value of seed, which is 48 bits. That could be brute-forced, given moderate resources (some CPU.days), and that we have plenty enough outputs (if the output was truly random, we'd have about $100\cdot {log}_2(6) \approx 258$ bits of information). However there are much better attacks possible, succeeding in seconds.

That problem itself has varied. Originally it used a small integer (the final modulus) of 8, instead of  6. We first study that, because it turns out to be easier, and a good intro for the version with 6.

Original problem, ending in return bits % 8

Here seed has 48 bits, bits is its leftmost 31 bits, and the result bits % 8 is the 3 lower bits of that. The top 28 bits of seed never have an opportunity to influence the output of the generator (in a LCG with modulus m a power of two, a bit change in seed never propagates to lower-order bits of seed). Thus for the purpose of predicting the output, seed behaves as a 20-bit (not 48-bit) state. Further, the 3 high bits of that reduced 20-bit state are directly known from the first output.

Now, since everything except the initial state of the RNG is known, brute forcing the remaining 17 bits is almost instant. There are smarter methods that avoid the guesswork.

This illustrates that when the output of a LCG using a power of two as its modulus m is taken modulus some power of two n, the output has a much smaller period than the original LCG (and other weaknesses that may be a disaster even for simulation purposes).

Update: It turns out that Java's nextInt(int n) method special-case what happens when n is a power of two, and then does something very different from what was shown in the original question. That's in order to avoid the effect described above.

Other problem, ending in return bits % 6

Here, all 48 bits of seed have an influence on the output sequence. But there is an easy way to break these 48 bits into two separately attacked segments.

Because the final modulus 6 is even, the low bit of bits is also the low bit of the output, and leaks directly. It is the high bit of the main LCG, reduced to the low 18 bits of seed. That allows recovering the low 18 bits of seed from the low bit of the first outputs (slightly more that 18, I guess). A simple approach is enumerating the $2^{18}$ values of the low 18 bits of seed and, for each, check which gives the correct parity of the first output values. That will recover the low 18 bits of seed well under a second, and is enough to predict the parity of further output. Again, there are smarter methods that avoid the guesswork.

Now we are left with the 30 high bits of seed unknown; that can be brute-forced in seconds. Likely there are smarter methods.

Update: It turns out that Java's nextInt(int n) method does not work exactly as was shown in the original question, even when n is not a power of two; that's in order to remove a bias in the output. However, the simplified description given is good enough that the cryptanalysis described has fair chance to work as is, and can be adapted to work reliably.

Update 2: The above works because m is a power of two, and the final modulus n is divisible by $2^k$ with $k>1$. This allows a separate attack of the $k+r$ lower bits, where $r$ is the number of right bits of seed not used to produce the output ($k=1$, $r=17$ in the above example). If a and/or c and/or $r$ was unknown, it would still be possible to make this separation, and find the $k+r$ lower bits of each of seed, aand c, and the value of $r$, from a number of consecutive outputs considered $\bmod 2^k$, irrespective of the other unknowns.

A more general approach, applicable also to odd n, and perhaps to unknown a and/or c, would be to encode the problem under the formalism of boolean satisfiability, and use one of the many automated solvers available. I can't predict the runtime, though. This flexible approach has broken some mildly serious ciphers, see e.g. this cryptanalysis of A5/1, or this one.

LCGs are seriously bad for cryptographic purposes. They are fine for continuous simulation purposes (where the output is turned into the mantissa of a floating-point number and used as such), but brittle for discrete simulation purposes. In particular, if the LCG uses a power of two as its modulus m, do not take its output modulus an even number and expect the result to behave as a dice with that number of faces: that assumption is incorrect, and many simple tests will show that.

For example, the imbalance between the number of odd and even results in consecutive (simulated) dice throws is exactly zero after $2^{1+r}$ throws. This could be detected with even less samples with a bidirectional Chi-squared test of nextInt(6)%2 or even just nextInt(6). The incredulous can run this test code; it almost always outputs 0 (exceptionally, another single-digit value), when true random would usually give a 3-digit value.

import java.util.Random;
public class diceparity {
    public static void main(String[] args) {
        final int m = 262144; // number of dice throws
        Random rand = new Random();
        int s = -m/2; for (int i = m; i != 0; --i)
            s += rand.nextInt(6)%2;
        System.out.println("Deviation from expected: "+s);
    }
}

Also, the parity of throws repeats after 262144 throws (or slightly less).


Should I use self generated or predefined RFC 7919 DH groups? On a wiki page, archived by now, Mozilla switched from recommending self generated DH groups to the ones predefinded in RFC 7919.
The recommendation was accompanied by the statement

These groups are audited and may be more resistant to attacks than
ones randomly generated.

Unfortunately, this – often cited – statement comes without any reasoning as to why these groups need an audit to be more resistant. A specification of how probable "may" is, is missing, too.
Can you explain why one should prefer RFC 7919 groups over self generated ones? What might be the reasoning behind this change? How likely is it that a self generated group is worse than one of the predefined ones? In particular, I am wondering because predefined keys are so much more likely to be precomputated by someone.
Edit: The parameters are assumed to be generated with (a recent version of) OpenSSL which is ubiquitous in publications about TLS setup: openssl dhparam 2048 which generates safe primes (p = 2 q + 1).
I am asking this question more for academic interest than for an actual real world application.
There is another question which gives some insight into the topic but it is focused on the question if 1024-bit parameters are enough while this question is about using self generated random DH groups or pregenerated ones.

Well, it's one less thing for the server to get wrong; I'll be giving my answer in the context of TLS 1.2 (as that was the context Mozilla assumed); remember, in TLS 1.2, it is the server that proposes the group, and Mozilla makes clients.

A "randomly generated group"; there are a number of ways of generating such a group, and they vary both in complexity, and (less obviously) the security.  Depending on the algorithm, you could generate a random prime, a "DSA prime"[1], a "Lim-Lee prime" [2], or a safe prime [3]; I have arranged the types of primes in order of both increasing security and increasing cost to generate.

The group includes the generator - how is that selected?  Ideally, we want to select a generator with a large prime suborder; does the server do that?

When you use the group, will you ever reuse the private exponent?  If you do, well, DSA primes can be weak in that scenario.

So, depending on the algorithm the server uses, the group has variable security characteristics; worse yet, the TLS 1.2 protocol does not give the client enough information to vet the proposed group (it can determine whether the server proposed a safe-prime, but since TLS 1.2 doesn't mandate safe-primes, there's little it can do with that information); in particular, it cannot determine the order of the proposed generator.
Hence, if Mozzila supported  server-generated groups, they'd be trusting that random servers did this rather subtle process correctly (without any way for them to verify it).  In contrast, the 7919 groups are known to be correctly generated, so that's one less  thing they need to depend on.
And, if you're worried about someone computing a factor base, well, I recommend you switch to ECC groups.
Also, I should list things which were likely not a part of the Mozilla decision:

The possibility that the server could accidentally select an SNFS-friendly group, that is, a group where the Special Number Field Sieve algorithm was applicable (which would allow computation of discrete logs considerably faster than the standard GNFS (aka NFS) algorithm can).  However, the probability that a SNFS-friendly group is selected is sufficiently tiny that, in practice, we don't need to worry about it.

The possibility that a malicious server could generate an "easy to solve" group.  However, there are lots of other ways a malicious server could foil security (for example, by selecting the private exponent in a guessable way, or just publishing the symmetric encryption keys); we need to assume that the server is honest (and so we need to protect only against accidental errors).

[1]: DSA prime is my terminology of a prime of the form $kq+1$, for $q$ a prime of perhaps 256 bits (and $k$ being an arbitrary even integer of the appropriate size).  The point of this is that it generates a group with a subgroup of a known size, and are essentially as cheap to generate as a random prime.
[2]: A Lim-Lee prime is a prime of the form $2qr+1$, for $q, r$ both primes about the size of half of the full prime.  The point of this is that it gives you most of the security advantages of safe primes, and are much cheaper to generate.
[3]: A safe prime is a prime of the form $2q+1$, for prime $q$.  This is standard and common terminology (compared to the other two); since I did define the other two, I thought I'd define this as well.


RSA factorization challenge I'm in a teacher-like position and would like my students to practice certain classes of RSA attacks. However I don't really know how to go about it and how to sensibly choose the parameters such that they have to practice the attack I had in mind when creating the challenge.

As two very concrete instances of this issue, I'd like to ask for advice on how to choose parameters such that my students have to (or are at least reasonably pushed towards) using

The chinese remainder theorem and / or
Wiener's attack on small-decryption exponent RSA.

So, how does one create RSA parameters to let them practice these two methods?

So you want them to practice using the CRT and Wiener's attack. I can now explain you how I would create a challenge in this direction.
As a side note please tell your students that they have to approach these problems with CRT / Wiener or they'll be very frustrated and maybe post here to ask for solutions which we can't offer because we don't which attack has to be applied which leads to frustration on all sides.

CRT
The main benefit of the CRT is that it provides a speed-up when we can piece our modulus into many small prime factors. As such I'd like to propose the following methodology:
Pick a small bound $B$ (less than $2^{20}$ so even trial division works). Pick your desired modulus size that rules out anything but small-factor-based factoring attacks (something like 100k bits, please also tell your students that they should use a small-factor attack here). Successively pick 100-10000 random primes smaller than $B$ and apply small exponents to each of them until you are satisfied with the resulting size of the modulus. Pick a valid $e$ and a message and textbook-encrypt the message. Provide the students with $e$, the modulus and the ciphertext and ask them to recover the message. Now to get the decryption done, they'll have to factor first and then use CRT. If they're not using CRT they'll have to wait a significantly longer amount of time (minutes as opposed to seconds at least). To fine-tune these parameters I suggest you try them out with and without CRT on your personal machine until you're satisfied with the time difference.
Wiener's attack
Pick an ordinary RSA modulus, ie a 2048-bit modulus with balanced primes that withstands all known factoring attacks just like you would for a production keypair. Now pick the private exponent first, such that it satiesfies the condition for Wiener's attack, i.e. it is small enough. Then construct $e$ as you normally would $d$, encrypt a message and provide the students with the ciphertext, $e$ and the modulus. Their task is then to recover the message. Test it yourself that one can actually recover the private exponent from this given set of data. And tell your students that they need to apply Wiener's attack or "one of the attacks we discussed in class previously".


Extracting a WinRAR password? If I have an original file and a WinRAR password protected .rar file containing that file, can I extract the password?

No, in general you cannot.

WinRAR uses AES (128 or 256 depending on version) for encryption, which does not allow key recovery even with know plaintext and ciphertext.

It also uses key stretching to derive the encryption key from a password. The algorithm used in newer versions is PBKDF2 with a version dependent iteration count. So a key-guessing attack is only possible for low entropy passwords. There is a verifier in the file format that allows checking password guesses, so knowing a plaintext and/or ciphertext does not give any advantage there either.


Security of DES P_BOX I'm curious about the design of the P_BOX of DES.
I found a paper on this topic, but it dates back to 1989.
This means the effect of p-box values of the cipher immunity against Differential Cryptanalysis and linear cryptanalyisis is not mentioned since they were Publicly discovered during the 90's (According to Bruce Schneier's book "Applied cryptography , the NSA and IBM knew about the attack since the 70s). I tried to look online, but it seemed to me that unlike the S-boxes which have considerable amount of literature, there are no good resources on the p_boxes.

The placement of the p_box in the Feistel function is shown here:

The permutation itself is shown here:

Previously on Crypto.SE, we explored the roles of the initial and final permutations and how they impact security. What about the permutation in the Feistel function? What impact (if any) does it have on security?

Note: you should also take into consideration the Expansion table, as it glues together with the Pbox.

The simplest thing you would like to want from a Pbox is to provide a good diffusion on the inter-sbox level. That is, a single sbox should have an effect on many sboxes in the next round. This is not sufficient, for example you could have some indepent groups of sboxes. So you need to see how many rounds are needed to prodive full diffusion, for each of the sboxes.

For example, PBoxes which make some independent groups of sboes, do not provide full diffusion at all and are considered unsecure. Also, consider Pbox which matches sboxes like $(2, 3, 4, 5, 6, 7, 1)$ (e.g. 1 shift left). You need at least 7 rounds to provide full diffusion.

For DES I think 2 rounds are enough for full diffusion, so that is at least acceptable.

Of course I described the very basic property of the PBoxes, which is not sufficient to say that a PBox is secure for a cipher. For another example, you can consider weak sboxes, for example if 2 sboxes are weak. Some PBoxes may resist it, some PBoxes may make the cipher much more weaker.


Why can't the IV be predictable when its said it doesn't need to be a secret? I heard multiple times not to reuse the same IV and IV should be random but doesn't need to be secret. I also heard if the IV is something like sequential numbers or something predictable I should hash(salt+pepper) it. Why on earth should i be doing that if they don't need to be a secret?

In this specific case i am encrypting rows with one secret AES key and i am using a fixed IV but xor-ing it with the row id. Its predictable and not secret but by doing this it isn't reused which i thought was the important part.

Are IVs suppose to be secret? Are predictable IVs ok? Should i be hashing predictable IV?

The requirements for an IV depend on which encryption algorithm you are using (AES is not an encryption algorithm by itself, since it can only act on 16-byte strings, but it can be used as a building block in a variety of different encryption schemes), specifically on the mode of operation.

Roughly speaking, the role of the IV is to insert some "new" randomness into the process each time a message is encrypted. That way, the same message encrypts to a different ciphertext each time, and similar messages to not result in similar ciphertexts. This is the reason why IVs often need to be random, but never need to be secret.

To answer your questions:

IVs do not need to be secret. In fact, they are often considered part of the ciphertext, and it is assumed that in adversary will see them.

Predictable IVs can sometimes be harmful. If you are using AES inside of Counter mode (CTR) encryption, predictable IVs are fine (the IV acts as a counter that gets incremented with each 16-byte block you encrypt; the important point here is that a counter value should never be repeated). On the other hand, if you are using Cipher Block Chaining mode (CBC), a predictable IV can allow some chosen-plaintext attacks. Preventing this is usually considered the ideal goal of an encryption scheme, since it implies the attacker can't do other, more harmful, things. Depending on the specific context, predictable CBC IVs can definitely cause problems.

Hashing doesn't necessarily make IVs more unpredictable. Hashing an otherwise predictable IV can make it look "more random", but where are you getting the salt and pepper? If these are also predictable, then hashing hasn't gained you anything. If they are random, then why not use this random number generator to make your IV directly?

You can play it safe by always generating random IVs. This can be "overkill" for algorithms such as CTR mode, but it will still be safe.

For more information:

Blockcipher modes of operation (Describes CBC, CTR, and some others)
Initialization vectors

Based on my understanding of what you're doing (I'm not to clear on the details), I'd recommend that whenever you update or create a row, generate a new, random IV for that row, and then use that IV for the encryption. The IV can be concatenated to the ciphertext, or stored in a separate location.

If storing IVs is impractical, a better alternative to hashing would be to use a second key $K$ to generate IVs; for example, the IV for row i could be $\textrm{AES}_K(i)$ or $\textrm{HMAC-SHA256}_K(i)$. The reason for this is that hash functions are not the same thing as pseudo-random functions from a cryptographic perspective, and so hashing something doesn't really give you a random IV. This approach is not secure if you need to update rows (or rather, if an adversary could potentially see two different ciphertexts for the same row), since repeating an IV is bad, bad, bad.


Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure I recently started studying cryptography but I am not sure I quite understand the concept of proof by reduction. Question I am trying to solve is as follow:
Suppose $\Pi$ is a symmetric encryption scheme which $ C \subseteq M$ ($M$ is message space and $C$ is ciphertext space). then we have $\Pi'$ with same key generation and decryption algorithm as $\Pi$ ($K' = K , D' = D$) with encryption algorithm as follow
$$E_k'(m) = E_k(E_k(m)).$$
I am trying to proof or reject:
a ) if $\Pi$ is indistinguishable in presence of an eavesdropper (simplest case when attacker can only see a ciphertext) then $\Pi'$ is indistinguishable.
b ) if $\Pi$ is CPA-secure then $\Pi'$ is CPA-scure.
for case a using proof by reduction i came up with solution

$ C \subseteq M $ implies a bijection between $M$ and $C$ so whenever $A'$ guess the chosen bit correctly $A$ will do as well so we have
$$Advantage\: of\:  A \geq Advantage\: of\:  A'$$
So if $A'$ be a attacker with non negligible advantage $A$ will be as well so a is true.
Am I using reduction correctly? What bout part b? Can we use almost same reasoning or there is an attacker for this case to prove $\Pi'$ is not CPA-secure?
EDIT :  regarding @Ievgeni answer for part a one time pad is a counterexample and regarding @Mikero comment i think reduction for part b might be something like below

conclusion :
part a : wrong . and one time pad is an counterexample and first picture is totally wrong.
part b : right . and proof is by reduction(picture two). for this reduction we have
$$Advantage\: of\:  A = Advantage\: of\:  A'$$
so if advantage of $A'$ be non-negligible advantage of $A$ will be too.

As Mikero noticed, the problem in your first proof is the fact that you can't suppose that $\mathcal{A}$ knows the secret $k$, and thus it can not encrypt the challenge.
And if you don't encrypt the challenge, then the input is not what is expected by $A'$. $A'$ is waiting $Enc^2_k(m)$ or $Enc^2_k(m')$ as a challenge not $Enc_k(m)$ or $Enc_k(m')$.
When you are doing a game-based proof, an important notion is the notion of
indistinguishability. For example If you are using an algorithm $\mathcal{A}$ as an oracle. And if you want to use some properties about the output of $\mathcal{A}$, it is important to check that the input of $\mathcal{A}$ follow the distribution which is mentioned in the property.
In your example, you are giving to the adversary $Enc(m)$ and not $Enc(Enc(m))$, it's completely different in the general case.
Let consider the xor encryption $Enc_k(m)= k\oplus m$.
It's really easy to build an attacker (let say a powerfull attacker who decrypts the ciphertext without the secret key) against $Enc^2$, it's just the identity function (Because $Dec_k^2=Enc^2_k$ is the identity function for all $k$.)
Then even $Enc$ is semantically secure, then $Enc^2$ could not to be. So a) is false.
But your proof about (b) seems correct to me.


Best practices for saving encrypted user data without a database We are setting up a web application which requires users to submit sensitive data. Since entering all the required data may take a long amount of time, we want to give them the option to save their progress. Maintaining a database to store their information is risky for us, as it opens up our servers to potential attacks. We have a small team and would be hard pressed to maintain the level of security we would want.

Rather than maintaining such a database, we would like to encrypt the user's partial progress (a text string in JSON format) with a password that we provide and that is supplied to them only at the time they wish to save progress. They will be instructed in the UI to physically write the password down rather than save it on their computer. To resume progress, they would supply us the encrypted file and the password. On our end, no data is persisted. If they lose the password they just have to start again.

Is any portion of this method obviously insecure? What encryption algorithms and libraries (Java or Python) are best for performing encryption/decryption?

This answer proposes a solution based on local storage and local encryption.

The data of the forms that the user enters:

Can be locally encrypted whenever the user wants to save...
The encrypted file(s) can be stored locally, if you want to store it to, you can transfer a copy to your server
The encrypted file(s) can be decrypted locally and restored into forms by JScript. You can use NodeJS.
If the user lost their file(s) then if you saved in your server, you can transfer back to the user to resume.

The methods;

From a password to an encryption key, you can use PBKDF2. Ask the user to a good password to increase against the brute-force attacks.
For encryption of the data, you can use AES-CBC with randomly generated IV. If you want to authentication for the encrypted data, you should, you can use AES-GCM.

Don't forget to ask the user to write the password at somewhere.


Deterministic Rand function for Winternitz One Time Signatures Suppose you are implementing a Generalized Merkle Signature Scheme, using the Winternitz One-Time Signature Scheme for the node signatures. Furthermore, suppose the implementation is to be stateless (i.e. you don't keep track of which signatures have already been generated), meaning that you use a deterministic $Rand$ function for generating all private keys, so that any path through the tree might be re-generated on the fly.

Also suppose that the path is selected as a (public) function of the digest to be signed.

The question is, would choosing a $Rand$ function that is not a $PRF$ significantly weaken the GMSS scheme if it is attacked by a quantum computing capable adversary?

For instance, suppose you are using SHA-256/250 for the Message Digest and SHA-256 as the iterated One Way Function. Would choosing the $Rand$ function below be a bad idea? The input value is the binary representation of the path of the private key in the tree.

Let $k_0, k_1$ be two 256-bit AES-256 keys. These keys are the private key for GMSS.

Define function $Rand_{k_0,k_1}:\{0,1\}^{128\times2}\to\{0,1\}^{128\times2}$ as:

$INPUT: x_0,x_1$ (two 128-bit blocks)
$c_0 = E_{k_0}(x_1) \oplus x_0$
$c_1 = E_{k_1}(c_0) \oplus x_1$
$OUTPUT: c_0,c_1$ (two 128-bit blocks)

This $Rand$ function is not a $PRF$ in the random oracle model, because it might be distinguished from a random function with only two selected inputs. But is it good enough to prevent existential forgeries (or other attacks) against GMSS?

The security claim is 250 bit security against classical adversaries and 125 bit security against quantum computing capable adversaries (presuming the adversary can't choose the input message digest to be signed).

Conjecture:
An existential forgery against GMSS is possible iff,

The adversary is able to recreate the Merkle tree(s) above some W-OTS public key $Y_{i,j}$, either because an authentic W-OTS $\sigma_{i,j}$ is part of a GMSS signature that has already been published, or because the adversary has knowledge of a sufficient number of other W-OTS private keys except the one at position $i,j$, and
The adversary either knows the entire W-OTS private key $X_{i,j}$, or the authentic digest signed by the authentic W-OTS $\sigma_{i,j}$ contains at least one zero bit and the adversary knows some of the (at least two) last elements of the private key $X_{i,j}$, corresponding to the checksum part of $\sigma_{i,j}$.

The most probable scenario (in which an existential forgery is possible) seems to be when the adversary knows some part of the W-OTS private key $X_{i,j}$ used for encoding the checksum part of $\sigma_{i,j}$.

Clearly, if the adversary knows one half of $(c_0,c_1) = Rand_{k_0,k_1}(x_0,x_1)$, the other half might be guessed with probability $2^{-128}$. The adversary will know one half of $(c_0,c_1)$ if there exists at least one known W-OTS signature $\sigma^{\prime}$ that signs a digest that contains at least one $b^{\prime}=0$ at a position for which $x_1=x_1^{\prime}$. In such case $c_0 = c_0^{\prime}\oplus x_0^{\prime}\oplus x_0$. Presumably, this will happen with a probability equal to the collision rate $Pr[\exists(x_1,x_1^{\prime})(x_1=x_1^{\prime})] = 2^{-64}$ times $Pr[b^{\prime}=0]=2^{-w}$.

This appears to indicate a security bound that is significantly less than the claim (presuming $w \ll 250-128-64$), but perhaps I am missing something. Or, is it even worse?

Why not use a stream cipher? The requirement for the generating function is not that it is a PRF but a PRG (which in many constructions is build out of a PRF). If you use the key stream of a stream cipher as output then this is a PRG.


Pollard's Rho - Constructing the Random Function Suppose we are aiming to solve the discrete logarithm problem $\alpha^x=\beta$ in some cyclic group $G=<\alpha>$. Then we are looking for a (uniformly) random sequence of elements of the form $\alpha^{a_{i}}\beta^{b_{i}}$, $i=0,1,2,...$ so that we can invoke the 'Birthday Paradox'. Pollard suggested a function which apparently works fairly well but can be improved on.
My question concerns the concrete implementation of Pollard's Rho: if we generated sequences of integers $\{a_{i}\}$, $\{b_{i}\}$ with a random number generator (from any given programming language), would this yield an acceptable 'level of randomness'?
The reason I am asking this is because I stumbled upon articles on 'random walks' for Pollard's Rho, which all seemed rather extensive; this led me to believe that achieving an desired level of randomness is quite tricky, and that there is a flaw in my idea of generating random integers. However, I can't seem to find it.

If you generate group elements at random as you suggest then you can indeed invoke the "Birthday Paradox" to find logarithms in time $O(\sqrt p)$. Unfortunately your storage requirements are the same and for cryptographically interesting group orders your method is therefore far from optimal.

The fastest way for groups with (apparently) no exploitable structure (like elliptic curves) uses "distinguished points" as it allows you to tailor your parameters to suit the storage you have available. Then there are issues relating to whether you're just finding one discrete logarithm or many.

Having said that, I believe that pretty well any reasonable random number generator will be satisfactory for your method. If a particular method of generating random numbers had a performance consistently different from normal then that would probably be of independent mathematical interest, worthy of publication.


Paillier Private $\mu$ and $\lambda$ The Paillier CryptoSystem has a public key that $(g,n)$ and the private key which can be exclusive to $\lambda$, where the decryption scheme is:

$m = L(c^\lambda \bmod n^2)/L(g^\lambda \bmod n^2) \bmod n$

Since $1/L(g^\lambda \bmod n^2)$ is fixed and always needed for decryption, it is usually computed once and denoted as $\mu$.

What information does $\mu$ leaks about $\lambda$? Because at the end of the day, even if I have $\mu$, I cannot decrypt. i.e. Can I get $\lambda$ from $\mu$?

A Side Note on the way $\mu$ is constructed, that I think proves the correctness of the assumption:

\begin{align}
    g &= (1+n)^\alpha \cdot \mathcal{B}^n \pmod{n^2} & & \text{$g$ in the $n^{\text{th}}$ root form} \\
    g^\lambda &= (1+n)^{\alpha\lambda} \cdot \mathcal{B}^{n\lambda} \pmod{n^2} & &\text{so base on carmichael's theorem} \\
    g^\lambda &= (1+n)^{\alpha\lambda} \pmod{n^2} & & \text{again, based on $n^{\text{th}}$ root rule}\\
    g^\lambda &= 1+n\alpha\lambda \pmod{n^2}&  & \\
    L(g^\lambda) &= \alpha\lambda \pmod{n^2}&  &\\
\mu &= 1/\alpha\lambda \pmod{n^2} &
  \end{align}
So, since it is impossible to get $\alpha$ given $g$, the main complexity of the encryption scheme itself, and the last equation is a function of two variable, and there is no way to find either variable.

What information does $\mu$ leak about $\lambda$?

The safe assumption is: all. It must be assumed that knowledge of $\mu$, together with the public key, allows computing $\lambda$ (which allows decryption and factorization of $n$).

At least, that holds in Paillier's scheme as described in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (section 13.2.2). In this we have $p$ and $q$ of equal size, $g=n+1$, $\lambda=(p-1)(q-1)$, and $\mu=\lambda^{-1}\bmod n$. It follows that $\lambda=\mu^{-1}\bmod n$, allowing computation of $\lambda$ from $\mu$ and $n$ (using e.g. the extended Euclidean algorithm, which is inexpensive).

While that does not immediately tell how to compute $\lambda$ from $\mu$ and $n$ in Paillier's scheme as in the question, that's enough to show that we can't safely reveal $\mu$.


Can I construct a PRP by sorting results of a PRF? I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output.

For example, if $x_1$ mapped to $4$ under a specific key in the PRF, and $x_2$ mapped to $2$, then the PRP for $\{x_1, x_2\}$ would be $\{x_2, x_1\}$ under that same key.

Does that make sense? Is this PRP construction secure, or do I have to implement a Luby-Rackoff construction using the PRF?

Even if this worked in principle, I don't see how this could possibly be practical to implement for any but the smallest sets, since it requires you to enumerate (and sort) the set you want to permute.

Also, it seems to me that, unless the codomain of the PRF is much larger than its domain, you're going to have an issue with ties, i.e. with inputs $x_1 \ne x_2$ for which ${\rm PRF}(x_1) = {\rm PRF}(x_2)$.  I don't see any obvious way to break such ties that could not be potentially used to distinguish the resulting PRP from a random permutation.

All that said, if you really just want to pseudorandomly shuffle a small set of values, feeding each of them to a PRF with a sufficiently large domain (like HMAC-SHA256) and sorting the values by the result should be a perfectly good and secure solution.  Specifically, consider an adversary that tries to distinguish your pseudorandom shuffle from a truly random shuffle.  For such an adversary to succeed (with probability greater than ½), they must either:

somehow distinguish the PRF from a random function, or
observe a collision among the PRF outputs.

The probability of option 1 will depend on the PRF (and on the assumed capabilities of the attacker), but it must be negligibly small for all practical attackers for the PRF to be deemed secure.  On the other hand, assuming that the PRF is not distinguishable from a random function, the second probability can be calculated:

Specifically, given $k$ inputs to a PRF with an $n$-element codomain (where e.g. $n = 2^{256}$ for HMAC-SHA256), the probability $p$ of observing at least one collision is less than the expected number of collisions, which itself equals $\frac{k^2 - k}{2n} < \frac{k^2}{2n}$.  Thus, for example, if $k \le 2^{64}$ and $n = 2^{256}$, then $p < \frac{(2^{64})^2}{2\cdot2^{256}} = 2^{-129}$.


Difference between implicit signature and explicit signature In most of time, what I see is explicit signatures such as ElGamal, it's rare to see the implicit signatures. So I wonder

why it's rare to be seen?
what aspect is it mainly used?
what's the difference between implicit signature and explicit
signature?

P.S. I want a detailed answer, better give some examples of implicit signatures

Actually, I never heard of the notation of an implicit signature before. However, when looking at MQV, there is a quantity which is denoted as an implicit signature, which is nicely described here:

  The MQV elliptic curve key agreement method is used to establish a shared secret between parties who already possess trusted copies of each other’s static public keys. Both parties still generate dynamic public and private keys and then exchange public keys. However, upon receipt of the other party’s public key, each party calculates a quantity called an implicit signature using its own private key and the other party’s public key. The shared secret is then generated from the implicit signature. The term implicit signature is used to indicate that the shared secrets do not agree if the other party’s public key is not employed, thus giving implicit verification that the public secret is generated by the public party.

Nevertheless, this only seems to be a terminology in context of MQV and not a common concept.

Edit (a more general justification of the wording)

A generic way to realize an authenticated key exchange (AKE) from Diffie-Hellman is to execute a Diffie-Hellman key exchange and to sign all the communication sent between the parties, i.e., party Alice and Bob own a key pair of some secure digital signature scheme each (where the authentic public verification key is known to the other party) and every party signs each sent message using its private signing key. Such an AKE protocol is sometimes also referred to as Signed Diffie-Hellman. I assume that this sometimes may also be referred to a as explicit signature, since every party computes explicit signatures for the messages and the construction is generic, i.e., every secure digital signature scheme such as ECDSA may be used.

MQV also assumes the possession of trusted copies of the other parties static public key ($A$ of Alice and $B$ of Bob in the referenced link). The respective secrets $a$ and $b$ are used in steps $3$ and $4$ (in the link) and the respective quantities $S_a$ and $S_b$ seem to be denoted as implicit signature sometimes, since they are no explicit digital signature schemes involved, but messages $3$ and $4$ achieve the same goal. Namely, the messages $3$ and $4$ prove to party Bob and Alice respectively, that the respective secret ($a$ and $b$) corresponding to the authentic public key is known to the sender of message $3$ and $4$ respectively.


Does not using padding mean a lack of security? I've read several texts which say that if the entire plaintext is a multiple of the block-size padding is not required (and not using padding would not mean a loss of security).
I generally disagree on this. In some special cases, for example in CTR of OFB mode padding could even unveil more information about the block-cipher output than not using it. But many currently used paddings are randomized.

When using a randomized padding with modern block ciphers the smallest change in the block-cipher input will change the entire block-cipher output. Therefore the randomness of the padding contributes to the encryptions security.

My first question is whether the above statement is correct or not and why.
And second: Are modes like CBC/PCBC more secure than modes like CTR/OFB? Or does it depend on the used padding?

I've read several texts which say that if the entire plaintext is a multiple of the block-size padding is not required (and not using padding would not mean a loss of security). I generally disagree on this.

In modes where padding is used (e.g., CBC), padding is mandatory. This is per spec. Not including the padding is simply not an option.

  In some special cases, for example in CTR of OFB mode padding could even unveil more information about the block-cipher output than not using it. But many currently used paddings are randomized.

It's a bit confusing what you're actually asking here, because CTR and OFB don't use padding, as they're stream ciphers. You could pad them (for instance, to make traffic analysis more difficult), but whether or not to do so is a decision completely independent of the block size of the underlying cipher. Padding to the block size is done for block modes like CBC.

  When using a randomized padding with modern block ciphers the smallest change in the block-cipher input will change the entire block-cipher output.

For the final block only. Unless you pad at the front, which isn't done by any modes I'm aware of. For streaming modes of block ciphers, padding doesn't change any of the bits of the actual ciphertext. Unless, again, you pad at the front.

  Therefore the randomness of the padding contributes to the encryptions security.

No, not even slightly. Even if you did pad at the front of a block cipher and get a completely new ciphertext as a result, this doesn't directly contribute the security of the block cipher in the least. If the block cipher was secure beforehand, you simply have a different stream of bits that are equally secure. If the block cipher was insecure beforehand, you still have a stream of bits that is (generally) going to be vulnerable to the same set of attacks as before.

Padding like this might change some bits, but it doesn't improve the actual security of the cipher. In fact, some times, it can weaken it (see CBC padding oracle attacks). Padding in block ciphers isn't done for security, it's done because block-sized inputs is required by the underlying block cipher.

  My first question is whether the above statement is correct or not and why. And second: Are modes like CBC/PCBC more secure than modes like CTR/OFB? Or does it depend on the used padding?

Your question doesn't really make sense as asked. These modes have different security properties and fail in different ways. CBC can fail catastrophically to padding oracle attacks because of its padding. CTR can fail catastrophically when IVs are reused, but padding won't help solve this problem. Both are equally secure when used correctly, but CBC is somewhat harder to use correctly in common use-cases.


Question about using Montgomery form for elliptic curve operations on bls12-381 Since the prime for bls12-381 is not of a form to allow easy modular reduction , is the best approach to use the Montgomery multiplication + reduction algorithm?

(q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab)

If I do this, can I convert the affine point coordinates into jacobian projected and then into their Montgomery form at the very start, so all modulo multiplications inside the point double / add algorithms use the Montgomery algorithm? Then only convert out of Montgomery form and then back to affine coordinates at the very end.

I figured this out, the best approach is to use either Montgomery or Barrets algorithm for modulo reduction, Barrets requires a slightly higher bit multiplication but not pre-transformation, while Montgomery has a pre-transformation but multiplications are slightly faster.

And if you use Montgomery you can do the entire point double/add in Montgomery form using jacobian coordinates and just convert back at the end.