Questions about BCrypt and PBKDF2 I would ask you some questions about users' password storage in a login system.

What algorithm do you suggest me to use? bcrypt or PBKDF2?

I was looking for a way to implement them client-side and i thought this way:

The client computes 10.000 iteractions of user's password with PBKDF2 and username (or email) as SALT and the server will store in the DB the salted SHA-512 digest of the PBKDF2 result.

Is it a good way?
Is client-side key stretching good in general? Does it have some disadvantages compared to the server-side implementation?
Is there a better way to implement PBKDF2 client-side?
And what about bcrypt?
If I use bcrypt server-side, what's the best way to add a pepper?
Adding pepper has some disadvantage?

What's your motivation for slow-hashing on the client-side?

It may well be slower than if performed server side (if you're referring to a browser-based application, and the hashing is done with javascript, then it will certainly be slower, even more so if it's a mobile device)
it doesn't provide any extra security, the credential(s) (password, hash of the password, salt derived from password which will be used for hashing the password, whatever...) will still need to be transmitted to the server - there's no way to avoid that

Keep it simple - you're much less likely to introduce some sort of vulnerability into your system.  The following protocol is pretty standard:

send the client's username/password to the server over TLS/SSL (it's worth the effort, really)
slow-hash the client's password with either Scrypt (preferable), or PBKDF2-SHA256 (at least 100'000 iterations) and a user-specific salt (stored in the DB with the hash)
for each login attempt, compare the output of the above with the hash you have stored in the DB

Note: Bcrypt is fine, some people fetishize it, others prefer PBKDF2 because it's more 'standard' (and it's output length is configurable).  Scrypt is the state-of-the-art, although it's less widely used, and can be more complicated to implement.

EDIT

After further consideration, and better understanding exactly what you're asking (I think), I'm going to say yes: what you're proposing is fine, provided certain conditions are met.  The issue that @StephenTouset pointed out is valid, and has to be avoided.  However, if I understand your question correctly, then you're already mitigating that weakness.  Consider the following:

Client slow-hashes password with PBKDF2 or Scrypt (use of email address or username as salt is questionable - email addresses change and usernames could be used in dictionary attacks).  This initial slow-hashing mitigates dictionary attacks, and offloads the heavy work from the server to the client
Client submits the output of the slow-hash (256 bits) to the server (over TLS/SSL), where it is then hashed once with SHA-256 (no salt necessary) and compared with the hash stored in the database.

Should the database be compromised, an attacker would still need to brute-force the hash of a 256-bit value (the client-side slow-hash output) to verify a correct guess at the password, pretty much rendering the hashes stored in the database useless to an attacker.

I think the theory is fine.  In practise, I think it's a bit messy and maybe unwarranted (your comment mentioned up to 1000 login attempts per second, are you really anticipating up to 86 million logins per day??).  Only you can decide whether you can justify it.


Only remember part and format of BitLocker password I am a complete novice to the field, however I made the mistake of locking my Macbook bootcamp partition with a bitlocker password which I cannot remember entirely.

There isn't much irreplaceable data on the partition, but I would like to know whether there's any way to recover the password.

the format was :

Dictionaryword&dictionaryword301

What I have forgotten are the two words, which were standard English words (albeit long ones). The first one was capitalised.

I would greatly appreciate any suggestions,

Thanks in advance

Well, this isn't really on topic for our site, so it will probably be closed.

But you might want to look at something like John the Ripper.

Either that or just grab a dictionary of English words and write a program to put combinations of them together and submit them as password guesses.


Application of cryptographic hash functions which do not require collision resistance property I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we open the file and recalculate the hash and compare it to the trusted one, do we need it to be collision resistant?

The two cases for stored files/programs;

On your files/programs
In this case it is the secondary pre-image attack that is given an input $m$ and a hash value $h =Hash(m)$ find another input $\bar m$ such that $m \neq m'$ and $h = Hash(m')$. As long as the hash value $h$ is not under the control of the attackers, they need to find the second input. In this case, we don't need the collision attack that is

Collision attack is finding two inputs $a$ and $b$ with $a\neq b$ such that $Hash(a) = Hash(b)$. To have collision resistance, finding such a pair must not be lower than $\mathcal{O}(2^{n/2})$ for hash functions with $n$ bit output size for any probabilistic polynomial-time adversaries. The bound comes from the birthday attack on the hash functions.

If the attackers can control the hash value, it may be possible to use to their advantage. To prevent this we need to use a keyed hash like HMAC, KMAC.

Third-party files/programs
If you accept the files/programs from the third parties, the classic attack that uses collision of two or more files/programs works as in Luis Casillas's answer and addressed well in Squeamish Ossifrage answer with good, bad, and sneaky versions. Therefore a collision resistance is required. You can mitigate this with HMAC.

Collision resistance is not necessary all the time.

A good example is the HMAC  expanded as either keyed-hash message authentication code or hash-based message authentication code). HMAC is a PRF under the sole assumption that the compression function is a PRF [1] proved by Mihir Bellare in 2006. A PRF doesn't need to have collision resistance. And, usually, we instantiate the HMAC with good hash functions like HMAC-SHA256 or, HMAC-SHA3-256.

Another example is password hashing, although we don't use standard cryptographic hash functions since they are fast and not memory-hard functions - Scrypt, PBKDF2, or Argon2 is preferred -  they are still considered hash functions. In password hashing, the pre-image and secondary pre-image attacks are considered to be important. The collisions are not applicable in password hashing.


Prove that some Cyphertext C encrypts some plaintext D I have a Paillier Cyphertext C and a counterparty that controls the keypair that was used to encrypt the data D to arrive at C.

How can they prove to me that the Cyphertext C is actually the encryption of a particular value, e.g. how can they prove that D=0 without giving me the secret key?

Equivalently, how can that counterparty prove to me that the decryption of C is some value V or not?

Assuming that $D$ is the correct decryption, we have

$$C = g^D r^n \pmod{n^2}$$

for some value $r$.

Someone with the private key can easily recover $r$; hence they can just display it (and you can easily verify the above equation).

Learning the value $r$ does not allow you to derive the private key (if it did, you could encrypt values yourself using a known value $r$, and then use that to recover the private key).

Alternatively, if you need a zero knowledge proof (for example, if the value of $r$ would tell you something about the internal computations that the other side doesn't want you to know), you can do something like this cut-and-choose protocol several times:

They pick a random number $r'$ with $\gcd(r', n)=1$, and send $a = r'^n \bmod n^2$
You then choose either 0 or 1
If you pick 0, they output $r'$, which you can verify by checking if $a = r'^n \bmod n^2$
If you pick 1, they output $b = r \cdot r'^{-1} \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$


How does chosen ciphertext attack on Elgamal work? Can it be proven that attacker can obtain the full message if he knows some plain-ciphertext pairs?

Assuming you don't use counter-measures against this kind of an attack, a chosen-ciphertext attack works as follows:

Variables: $p$ is field prime, $\alpha$ is the chosen generator, $a$ is the private key, $\alpha^a=\beta$ is the public key. $k'$ and $m'$ are chosen at random.

Note: all the following equations are $(mod$ $p)$.

Suppose you want to decrypt the ciphertext $C=(\gamma,\delta)=(\alpha^k,m*\beta^k)$
Now calculate $C'=(\gamma*\alpha^{k'},\delta*\beta^{k'}*(m'))$
Now give $C'$ to the decryption oracle, you'll get $m''$ in return.
Finally calculate $m=m''*(m')^{-1}$

Why does this work?

Observe that $\gamma'=\gamma*\alpha^{k'}=\alpha^k*\alpha^{k'}=\alpha^{k+k'}=\alpha^{k''}$.
Further observe that $\delta'=\delta*\beta^{k'}*(m')=m*\beta^k*\beta^{k'}*(m')=(m*m')*\beta^{k+k'}=(m'')*\beta^{k''}$

If you let this pair get decrypted, you'll get $m''=m' * m$ in return an hence $m=m''*(m')^{-1}$ holds.


How to specify a NIST SP 800-108 KBKDF Strange question maybe, but say I want to specify a protocol that complies with NIST SP 800-108. This lists a whole set of key based key derivation functions, with a very loose set of parameters.

How should I identify the KDF used? It seems that the KDF's in this document have neither a name, an OID nor an ASN.1 module. Are there any compliant KDF's in the world that comply to the descriptions and that do have a name/OID/ASN.1?

Or do I have to do this  work myself and then test myself against the available test vectors?

Background

When defining protocol compliant with NIST SP 800-108, you just need to pick suitable options, which work well with your protocol.

If there is a need to be compatible with a specific pre-existing protocol, you may want to take a look at NIST SP 800-135Rev1, which defines application specific key derivation functions. It is notable to recognize that some of the NIST SP 800-135Rev1 key derivation functions are valid NIST SP 800-108, with specific options selected.

The best way to identify the KDF is to actually list all the applicable options from NIST SP 800-108 KBKDF. (What of three functions to use (CTR, FB, Pipeline); order of components, what is the content of label, and if the label is terminated by zero etc.) It is likely best to illustrate the protocol specification with clear examples which show the correspondence of NIST SP 800-108 functions (or alternative show invocations of underlying MAC function) as used in key derivation.

Testing NIST SP 800-108 implementation

The recommended way to test is via CAVP (Cryptographic Algorithm Validation Program). Testing takes a long time and will be performed by a CST (Certified testing Laboratory), which costs money. But you get to choose pretty specifically what to test (from reasonably large option space) and if you pass the testing, you will get a algorithm validation certificate.

For most common options, less expensive and quicker way could be to test against pre-existing unofficial test vectors from NIST/CAVP.

If the implementation needs not only to be FIPS compliant, but also is required to have US government certification (FIPS 140-2), then algorithm certificates for the applicable algorithms are needed.

If you need a set of test vectors for your KBKDF "instantiation", one way to do it is to first ensure correctness of implementation using one of the above mechanisms, and the use that "appears to be correct" implementation to generate the official test vectors, and attach the test vectors with the protocol specification.

The way to determine order, sizes of elements etc. used in the test vectors is explained in KBKDFVS (KBKDF Validation System).

The parameters KBKDFVS uses for Feedback Mode are (extracted from KBKDFVS):

Pseudo-Random Function supported by the IUT

List CMAC AES 128, 192, 256
CMAC TDES 2, 3
HMAC SHA1, SHA224, SHA256, SHA384, SHA512

L-length of the derived keying material K0 in bytes – Enter all that apply:

A minimum and maximum value for full block lengths supported
A minimum and maximum value for partial block lengths supported

Method(s) supported to generate K:

SP800-56A
SP800-56B
SP800-90A
an Approved RNG
N/A – Out of the scope of the algorithm implementation

Does the IUT support the counter being used as an input? If yes, what is the length of the binary representation of the counter i.

8 bits.
16 bits.
24 bits.
32 bits.

Does the IUT support the counter coming before and/or after the iteration variable and/or after the fixed input data?

The information for other modes (i.e.) counter and double pipeline is similar.
This information is not sufficient to encode all that can be known about the KDF function, but is already a good start.

Finally addressing your questions

Identify the KDF by specifying options from NIST SP 800-108. You should also have examples (and possibly test vectors), which allow correct implementation.
The name is of NIST SP 800-108 and the name (or section) of the mode used.
I'm also not aware of OID/ASN.1 applicable. (But maybe somebody has defined something for their implementations of NIST SP 800-108. There are no OID/ASN.1 which covers all the possible options of NIST SP 800-108.)
If you need OID or ASN.1 module for your protocol, it is likely easiest for now to define your own.
Implementations of SP 800-108 likely can be tested using CAVP or unofficial CAVP test vectors.
KBKDFVS can be good example to see how NIST specifies the parameters in context of test vectors. Maybe you can use similar approach and terminology for the protocol?

HKDF

Side Note: Depending on how you use HKDF, you are often using either NIST SP 800-108 or NIST SP 800-56C: HKDF "expand only" can be considered to be a variant of NIST SP 800-108 KBKDF. NIST SP 800-56C is basically attempt to define full HKDF in NIST terminology (and add AES-CMAC).


What is 'order' in More Modular Exponential (MODP) Diffie-Hellman groups? I am investigating on source code of a program called hostapd. And I am looking into Diffii-Hellman part of it.

/* RFC 3526, 3. Group 14 - 2048 Bit MODP
 * Generator: 2
 * Prime: 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }
 */
static const u8 dh_group14_generator[1] = { 0x02 };
static const u8 dh_group14_prime[256] = {
  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  ...
}; /* too long */
static const u8 dh_group14_order[256] = {
  0x7F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  ...
}; /* too long */

I understand that dh_group14_generator is a generator and dh_group14_prime is a prime for 2048 bit MODP from RFC 3526.

However, I can't find any clue of dh_group14_order. What does it stand for?

Order here is not anything to do with how you might "order" a row of pencils in order of height (or some similar behaviour) -- but the number of elements in the group in question.


Verifying a Signature Alice publishes $(n,e)$ where $n$ is exponential modulus and $e$ is the public key. We have $n=80$ digit number and $e=3$. Bob, in correspondence with Alice, asked Alice to prove she is really Alice, by making her signature on the following five numbers: $m1, m2, m3, m4, m5$. Then Alice sent 6 numbers $y1, y2, y3, y4, y5, y6$ where all the 6 numbers are really long, around 80 integers.

How do verify that these five numbers are indeed signed by Alice?

Alice will have computed

$y_{i} = m_{i}^{d} \,\mbox{mod}\, n$

and Bob will compute

$d_{i} = y_{i}^{e} \,\mbox{mod}\, n$

If Bob finds $d_{i} == m_{i}$ for every $i$, he will probably conclude that they were indeed signed by Alice. His conclusion however, is very unwise, since for this special case where $e=3$, the numbers $y_{i}$ can be easily forged by an attacker even if he does not possess the private key $d$ of Alice.


Why is sharing the seed and using SecureRandom "deterministically" so bad? I've recently been reading an article about "using cryptography to store credentials", and I would love it someone explained this in more detail…

Up until Android 4.1, Android used a SecureRandom provider, that, given the same seed, after using setSeed(seed), it would generate the exact same stream of bytes. Because of this, people used this fact to generate AES keys for encrypting, only sharing the seed between users.

Google found out about this and introduced a new SecureRandom provider in 4.2 (based on OpenSSL's PRNG), which, for the same setSeed(seed) generates different outputs. They also recommend using PBE (PBKDF2 etc) for doing key generation, which is a fair recommendation (due to bruteforcing protection).

Why is sharing the seed and using SecureRandom "deterministically" so bad? Is it a bug?

This technique is even mentioned in the RFC1750

  It should be noted that if your technique for generating a sequence
         of key values is fast enough, it can trivially be used as the basis
         for a confidentiality system.  If two parties use the same sequence
         generating technique and start with the same seed material, they will
         generate identical sequences.  These could, for example, be xor'ed at
         one end with data being send, encrypting it, and xor'ed with this
         data as received, decrypting it due to the reversible properties of
         the xor operation.

Both determinism and non-determinism are useful. The question is which one you use for which purpose.

Determinism is generally useful for expanding a short secret to a long one. For example, you may keep a short random secret and use it to generate a long keystream that you can XOR against messages for encryption and decryption (such as described in the RFC quote). When one string is generated deterministically from another, then the derived string is considered no more secure than the original since knowing the original allows the derived one to be calculated.

Non-determinism is generally used to generate a random value that no one else knows (yet). If you need to generate a key and don't want someone else to guess it, you need a non-deterministic (or at least something that we feel is close enough to non-deterministic) process. If you instead used a deterministic one, then the output no stronger than input and the problem hasn't been solved since you need an strong input. Somewhere in the derivation chain you need something strongly non-deterministic so that the output can't be guessed.

Generally, cryptographic keys are derived non-deterministically and then the cryptographic operation (such as encryption or signing) performed by them is deterministic. (At least, you can think of it as being deterministic, technically it's still supposed to be randomized in some way.)

One last piece of the puzzle: In practice, non-deterministic random number generators accumulate non-deterministic entropy and use that to seed a deterministic process that generates output. This is because non-deterministic entropy is relatively hard to come by and it generally needs to be compressed/whitened before being output. The output was generated deterministically from a non-deterministic source, so it is considered non-deterministic itself.

All of that is a very high overview and is light on details, but the concepts are necessary to understand recent issues on SecureRandom.

So what happened with SecureRandom?

SecureRandom provides random output for things like key generation, so it needs to be non-deterministic. SecureRandom keeps an internal random state that it deterministically generates output from, and that internal state is supposed to be non-deterministic. So although the output is deterministically derived from an internal seed, when the seed is non-determinstic we consider the SecureRandom output to be non-deterministic. SecureRandom also allows the user to provide their own input seed as well.

SecureRandom had a bug where the internal state, if not seed was provided by a user, was automatically filled from a random source like /dev/urandom, but it was done improperly. The amount of random data actually used was much smaller than it should have been. Not having enough random input lead to cryptographic problems.
Another problem was that when a seed was provided by the user to SecureRandom, that seed would override the existing internal state. This meant that if the user called SecureRandom without seeding it they got deterministic output from a non-deterministic source, but if they provided a seed then they got deterministic output from their own input and their input (very likely) wasn't strong enough to be cryptographically strong itself. I don't think this behavior was a bug, but it was changed anyway to prevent innocent misuse. The fix was to add the seed to the internal state, rather than to use it to replacing the state.

Summary: When SecureRandom was used without a seed, the output was supposed to be non-deterministic, but it was based on too few non-deterministic bytes to be secure. When a seed was provided, the output only depended on the seed which was behavior that might confuse developers who thought a custom seed would add to the internal state rather than replace it.


Is AES-256 consistent? I ran into an issue with my server that made me ask a question - is AES-256 encryption reliably consistent?

So my node server, to avoid DDOS vulnerabilities while keeping user data anonymous, takes an IP from the request, encrypts it, and stores the number of times it has made a request in the last 24 hours.

It checks if the user had made a request in the last 24 hours by re-encrypting the IP using the exact same password. It then, takes that and matches it with the first stored IP.

But then:

Error: Can't find data: /ipcount/d00c526612cec9e5d3e201af35993c75. Stopped at ipcount

d00c526612cec9e5d3e201af35993c75 should be the encrypted string, but the database is acting like it's never seen it before. So can I have it encrypt consistently with the same password?

Thanks in advance.

AES-256 is a function from a 256-bit key and a 128-bit plaintext block to a 128-bit ciphertext block.  Same key and plaintext, same ciphertext.

But it is unlikely that your application uses AES-256 directly—most applications don't, because most applications are concerned with encrypting messages, not with permuting the set of strings of 128 bits.  From the information you've given, there's no way for us to know how you use AES-256, or even if you do use it directly, whether there's an application bug that just causes some wrong IP address to be stored or retrieved or causes some IP addresses to be dropped on the floor.


Are digital signatures using preprocessed paper pads possible? My idea was, given that a computer could produce some sort of lookup tables on paper, could then a human use those lookup tables to create a system for digital signatures?

This was really an idea for fictional writing. I was trying to figure out whether it could be possible in a society at sort of 1950s technology to create a more secure alternative to handwritten signatures.

E.g. that people could order paper pads produced by a computer as service and use those to sign contracts etc with a number rather than a handwritten signature. Another paper pad which was public should be used for verifying the authenticity of the paper.

Could anything like this be done. We assume that given that processing power availability in such a society is much worse than today, this system does not need to be nearly as secure (require as much computation) as today.

The best answer I can come up with is using some sort of Geometric cryptography. It is based on the difficulty of trisecting an angle using a ruler and compass. So you could hand over people a triplet of some secret angle.


Does SHA-512 leak info about SHA-256? Does the SHA-512 value of an input leak any information about the SHA-256 value of that same input?

Specifically, if I'm using SHA-512 to derive encryption and HMAC keys from a 256 bit ECDH shared secret (by splitting it into two 256 bit chunks), does publishing a SHA-256 fingerprint of that shared secret reveal any useful info about the derived keys?

does publishing a SHA-256 fingerprint of that shared secret reveal any useful info about the derived keys?

No such leakage is known, and it would look quite unlikely.  The SHA-256 and SHA-512 compression functions (which process the hashed messages) differ in a number of significant details (including the size of the words being processed); any such correlation would be quite surprising.

So, your approach looks reasonable.  Of course, if you want to be totally cautious, you can rely on a similar mechanism which has been cryptography studied for this specific security property; you could do:

$EncryptionKey = HMAC( ECDH, \text{'Encryption'} )$

$MacKey = HMAC( ECDH, \text{'Mac'} )$

$Fingerprint = HMAC( ECDH, \text{'Fingerprint'})$

An explicit assumption with HMAC (as a Message Authentication Code) is that if you get the HMAC of one message (say, the string "Fingerprint"), that doesn't help the attacker determine the HMAC of another message (either "Encryption" or "Mac")


Two-dimensional S-Box Consider the following simple cipher:
$$c_1 = S(m_1 \oplus k_1) \oplus k_2$$
Where $S$ is S-box, $m_1$ - 16-bit plain text, $k_1$ and $k_2$ is two parts of 16-bit key.

If S-box is standard then this cipher is quite easy to hack by differential analysis. But consider $m_1$ as two-dimensional array 4x4 bits and S-box as combination of two same 4-bit S-boxes. In the first S-box input is 4 rows of plain-text, in the second S-box input is 4 columns of output of first S-box:
$$c_1 = S''(S'(m_1 \oplus k_1)) \oplus k_2$$

Can you help me analyze this algorithm against the following problems:

Are there any advantages and disadvantages of this algorithm to the following:
$$c_1 = S(m_1 \oplus k_1) \oplus k_2$$
where $S$ is a 16-bit S-box.
How resistant is this algorithm to differential analysis.
Is this "two-dimensional s-box" is used somewhere?

I understand the question as you have a single 4-bit S-box, which you first apply rowwise, and then columnwise.

As already mentioned, this is equivalent to a large S-box $\mathcal{S}$
$$
c = \mathcal{S}(m\oplus k_1)\oplus k_2.
$$

This is a well-known Even-Mansour cipher, and it can be broken with complexity $2^{n/2}$, which is $2^8$ for your $n=16$. The idea by Daemen is to try $2^{n/2}$ plaintext pairs with the same difference $\Delta$ both for the entire cipher $E$ and the S-box $\mathcal{S}$.

So the answers to your questions are

No advantages.
Breakable in seconds.
Maybe in some marginal ciphers or hash functions. Note that it is quite inefficient in software.


Why are bitwise rotations used in cryptography? Any understanding I have of cryptography stops right around the cipher level. As such, I'm just curious as to why bit shifts and moreover circular bit shift are so prevalent in cryptography.

A bit rotation of a $w$-bit word by $r$ bits to the right transforms a $w$-bit word $X=(x_{w-1},x_{w-2},\dots,x_1,x_0)$ into the $w$-bit word $\operatorname{ROTR}(X,r)=(x_{r+w-1\bmod w},x_{r+w-2\bmod w},\dots,x_{r+1\bmod w},x_{r\bmod w})$.
Depending on context, $r$ is arbitrary in $\mathbb Z$, or constrained to some interval thereof, e.g. $0\le r<w$.
Rotation to the left can be defined as $\operatorname{ROTL}(X,r)=\operatorname{ROTR}(X,(-r\bmod w))$.

For any fixed $r$, $X\mapsto \operatorname{ROTR}(X,r)$ is a bit permutation. Under function composition, bit permutations of $w$-bit words form a finite group of $w!$ elements, of which bit rotations of $w$-bit words for fixed values of $r$ form a commutative subgroup of $w$ elements, isomorphic to $(\mathbb Z_w,+)$.

Bit permutations of $w$-bit words, including bit rotations by a fixed $r$, are not by themselves useful cryptographic transformations, because the above groups are so small subgroups of the group of bijections over $w$-bit words (which has $(2^w)!$ elements), or of the monoid of functions over $w$-bit words (which has $2^{w\cdot 2^w}$ elements).

However, bit rotations are useful in cryptography when combined with other common operations on $w$-bit words, such as other bitwise operations ($\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$..), and addition modulo $2^w$. That's for a number of reasons:

Rotation combined with other operation(s) allows to build arbitrary transformations of $w$-bit words. For example, by combining (a sufficient number of) $\operatorname{ROTR}$ (with $r=1$), $\operatorname{NAND}$, and some fixed constants, any function over $w$-bit words can be constructed (thus including any bijection, thus any bit permutation). By contrast, when $w>1$, this can not be achieved using any combination of $\operatorname{AND}$, $\operatorname{OR}$, $\operatorname{XOR}$, $\operatorname{NAND}$, $\operatorname{NOR}$, and addition modulo $2^w$ (because none of these operations can make bit $x_1$ on input influence bit $x_0$ on output). Stated otherwise: rotation is one of few ways to achieve diffusion from high to lower-order bits (right-shift, division, and table lookup are others).
More generally, rotation allows a cipher designer to create diffusion, at will, among bits of different rank in computer words, as emphasized in this other answer. Shifts allow that too, but when shifting by more than a few bits are too strongly surjective have too many distinct inputs reaching the same output for many cryptographic uses. Other techniques are used to create diffusion among different computer words.
Availability, speed and low cost: on many CPUs, rotation is the only bit permutation available as a single native CPU instruction (discounting the possibility to implement a permutation by a table read for small $w$). All modern computer CPUs, and many modern embedded CPUs, have a dedicated barrel shifter that can rotate over its natively supported word size(s) $w$, for any $r$, as fast as any other data manipulation goes. Rotation for other width $w$ not supported in hardware can be efficiently constructed in software. In hardware, rotation by a fixed $r$ requires no gate at all (like any bit permutation) thus is extremely fast and cheap.
No timing dependency: on all CPUs, rotation for fixed $r$ has duration independent of the data manipulated; this extends to variable $r$ when there is a barrel shifter. By contrast, table-lookup (another popular way to achieve diffusion to the right) often exhibit timing dependency, due to cache misses or memory alignment, which might allow timing attacks.

Many symmetric cryptographic primitives (hashes, block ciphers..) make heavy use of rotation by a fixed $r$, for the above reasons. Some (notably RC5) use variable rotation, though I have not seen this trend catching. I guess that could be (rightly) for fear of timing dependencies and other side-channels on CPUs without a barrel shifter supporting the rotation's width.


Protecting my message without encryption I am studying Information Security, and I am wondering if I can send a message to my friend X and keep the message confidential without using encryption?

I think this is a question that comes down to understanding the basic Alice, Bob and Eve diagram from cryptography textbooks, like this one from Wikimedia that I've chosen because of its license and no other reason:

Alice and Bob are communicating over a channel, depicted as the green line, and Eve is eavesdropping on that channel, metaphorically depicted as if there was a blue cable that plugs into the channel and carries its signal to Eve.  The reason Alice and Bob use encryption is because they're worried that the diagrammed situation might occur, and the goal of encryption is to make it so that, in that situation, Eve cannot learn much about their communication.

So it's hard to answer your question how to protect your messages without encryption other than by saying this: prevent any situation like the one described by that diagram from ever arising.  But that's not a concrete or actionable recommendation—it depends on the physical details of whatever scenario you're considering.  But to give one concrete example, the United States government uses something called a Sensitive Compartmented Information Facility (SCIF) to physically protect officials using sensitive information from being eavesdropped on.  Example passage from the article:

  Because SCIFs are supposed to distance sensitive information from the
  rest of the world, the Directive begins with architectural
  details—like adding a vestibule and extra interstitial reception
  spaces as "padding" between the SCIF and the outside. If the SCIF is a
  building (rather than a tent), it has to be reinforced concrete or
  lined with solid steel. Everything from the depth of the drywall to
  the thickness of the insulation is mandated by the document, too.

  The first—and most traditional—surveillance threat is sound, so SCIFs
  are lined with thick acoustic piling. In most cases, noise-masking
  devices like transducers are installed to garble what's going on
  inside, too. According to the BBC, another type of wave-emitting
  device creates a ring of electronic signals around the space, blocking
  other types of electronic surveillance, while a lining of special,
  foil-like material also blocks more traditional audio surveillance
  (similar to an average Faraday Cage).

That's an extreme example, of course, but (a) without details it's basically impossible to make concrete recommendations and (b) specific recommendations would likely be off-topic here.


Safety of encryption when knowing part of the content I want to encrypt a JSON file while exposing its interface (the name of the object fields) in clear text.
Since this exposes part of the content of the file, my guess is that an attacker could use this to hack the encryption key.
Are there encryption methods that can circumvent, or at least be safer for cases like this?
I am mostly convinced that knowing part of the content of an encrypted file can make attacks easier, but I do not know if there is a technical term for such conditions or how to evaluate if some algorithms are safer or not. So far I am specially interested if using aes-192-cbc or gpg would be OK.

If you use any reasonably standard modern encryption scheme, there's no need to worry. Ideally you should be using authenticated encryption like AES-GCM.
In modern cryptography we generally require an encryption scheme to at least have IND-CPA security to call it secure. IND-CPA stands for "indistinguishability under chosen plaintext attacks".
This security notion is defined as a game between a challenger and the attacker. The challenger chooses a key for the encryption scheme. The attacker can then query any ciphertext of their choice to the challenger and receives an encryption that plaintext. Eventually, the attacker outputs two challenge plaintexts $m_0,m_1$, the challenger flips a random bit $b$, and gives an encryption of $m_b$ to the attacker. The attacker can continue to make queries as above and eventually has to guess which message was encrypted. In an encryption scheme that is IND-CPA secure an efficient attacker can essentially do no better than guessing randomly.
The attack you are worrying about is much much weaker than what we consider the minimal security required of an encryption scheme. Any sane implementation of AES-CBC, AES-CTR or a modern stream cipher like Salsa/Chacha would be secure in this sense. (Even 3DES in CBC or CTR mode is fine, though horribly slow.)
In practice malleability of ciphertexts is often an issue, which is why it's generally advised to use "authenticated encryption", which prevents any modifications of the ciphertext.


Construct a random permutation from a random function? How can we construct a (pseudo) random permutation from a (pseudo) random function ?

I've seen a method from Luby-Rackoff which allows to construct a PRP of length $2N$ from a PRF of input/output length $N$. Is there a method to keep the same length $N$ ?

I'm looking for a method that has better security bounds than truncating the output of a $N$-bits output pseudorandom function to obtain an output of $N/2$-bits and using the Luby-Rackoff construction.

There are so many possible solutions here.  Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution.  Here are a bunch of schemes that offer better security than simply truncating to $N/2$ bits and applying 4 rounds of Luby-Rackoff:

For instance, one approach is to truncate the random function to $N/2$ bits, then use 6 or more rounds of the Luby-Rackoff construction.  Paterin has a paper at FSE 1998 that apparently proves that 6 rounds gives security for up to $O(2^{3N/8})$ chosen plaintext/ciphertext queries.  He also has a later paper at Crypto 2003 that apparently proves that 10 rounds is enough for security for up to $O(2^{N(1-\epsilon)/2})$ chosen plaintext/ciphertext queries.  Don't ask me to explain the proofs; I don't understand them.  I am not aware of any concrete-security versions of these results, so it's hard to know exactly how much security this gives you in practice.
Another approach is to truncate the random function to 1 bit of output (and $N-1$ input bits), then build a maximally unbalanced Feistel network that uses $4N$ rounds.  Naor and Reingold showed (Journal of Cryptology, Jan 1999) that this will give security for up to $O(2^{N/2})$ chosen plaintext/ciphertext queries.  (Technically speaking, their result assumed that you used a pairwise-independent permutation, then $2N$ rounds of unbalanced Feistel, than another pairwise-independent permutation, so if you really care about provable security, you could use that: but I suspect their results would likely apply to $4N$ rounds of unbalanced Feistel as well.)
Even better yet, if you do enough rounds of maximally unbalanced Feistel network, you can get arbitrarily close to $O(2^N)$ security.  Truncate the random function to one that takes $N-1$ input bits and has 1 output bit, and use it in an unbalanced Feistel network.  Morris, Rogaway, and Stegers proved at Crypto 2009 that, if you do $4RN$ rounds of this, you get security up to $O(2^{N(1-1/R)})$ chosen plaintext/ciphertext queries.  For instance, if you do $40N$ rounds, you get security up to something like $O(2^{0.9N})$ chosen plaintext/ciphertext queries.  That's a very impressive result.  If maximizing security is your goal, this might be your best bet.
Another approach is to truncate the random function to one on $N/2$ bits, then apply a suitable Benes network construction.  Aiello and Venkatesan proved in Eurocrypt 1996 that, with four rounds, this gives you security for up to $O(2^{N/2})$ chosen plaintext/ciphertext queries.

One keyword that may help you find still more results is "Luby-Rackoff beyond the birthday bound".


Finding the probability of a message encrypting to a given ciphertext I have been watching a crypto course and when they wanted to prove that the OTP is a secure cipher they refer to the probability and what I can't get so far is the understanding of this notation ?

$$P(E_k(m)=c)$$

The probability of a message encrypted to a cipher? How is that?

The general formula is:

$$P(m=m∗|E_k(m)=c)=P(m=m∗)$$

where

$m$ is the message to be encrypted
$m∗$ is the message that the attacker guesses
$c$ is the cipher text
$E_k$ is the encryption function

Part of your confusion is coming from ignoring the distinction between random variables (e.g., $K$) and their values (e.g., $k$).

Let $p$ be probability distribution of the keys $k\in {\cal K}$ and let $q$ be the probability distribution of the messages $m \in {\cal M},$ assuming both sets $\cal K$ and $\cal M$ are finite. The encryption mapping $E_K(M):=E(K,M)$ is a mapping  $$E:{\cal K} \times {\cal M} \rightarrow {\cal M}$$
where we assume the ciphertext space is also $\cal M$ for simplicity. Clearly a well defined cipher would select keys independently of the messages.

Then, using the definitions of conditional probability all quantities can be evaluated. In particular, the ciphertext distribution is directly obtained from the other two distributions since it is completely determined by them.

In general one could have $m$ mapping to $c$ under different key values $k$ and these will need to be summed, each admissible choice weighted by $p(k)q(m).$

Clearly, $P(m=m_1)=q(m_1),$ while $P(m=m_1|E_k(m)=c)$ is $$P(m=m_1|E_k(m)=c)=\frac{\sum_{k\in {\cal K}:E_k(m_1)=c}p(k)q(m_1)}{\sum_{k\in {\cal K},m\in {\cal M}:E_k(m)=c}p(k)q(m)}  $$
where the numerator is taken to be zero in case of an empty sum, and $c$ is fixed.


Why should the RSA private exponent have the same size as the modulus? Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes numbers of size $n/2$ (or very close), and check at least that they are probable primes and that $\mathrm{gcd}(e, (p-1)(q-1)) = 1$. Once $p$ and $q$ have been vetted, from what I've seen, the other parameters (the private exponent $d$, or the CRT parameters if desired) are computed but not subject to any extra check.

I have met an extra requirement whose purpose I don't understand. In the Référentiel Général de Sécurité (something like the French equivalent of FIPS), annex B1 §2.2.1.1, a rule states:

  [RègleFact-3] Private exponents must have the same size as the modulus.

What is the purpose of this rule? I know that small private exponents are bad, but here small means something like $d \lt N^{0.5}$. Even allowing for a security margin, this is a far cry from requiring $d \gt N/2$. What can go wrong if the size of $d$ is not verified (so the probability that $d \lt a N$ is close to $a$)?

Well, first off, it appears that these requirements are a bit confused.  If the requirement is that for a given modulus $N$ and public exponent $e$, that the corresponding private exponent $d$ satisfies $d > N\!/2$, that rules out all public keys (!).  You can see that from the necessary and sufficient relation $de = 1 \mod \operatorname{lcm}( p-1, q-1 )$, and so if $d$ exists (which it will of $e$ is relatively prime to $\operatorname{lcm}(p-1,q-1)$), then there exists a $d > 0$ with

$$d < \operatorname{lcm}(p-1, q-1) = (p-1)(q-1) / \!\operatorname{gcd}(p-1, q-1) \\ \le (p-1)(q-1) / 2 < N\!/2.$$

So, what other interpretation can we give to this rule?  Well, one alternative is that you must use a private exponent $d > N\!/2$, even though it is not the smallest possible.  However, as such a $d$ always exists, that actually mandates no requirements whatsoever on either $N$ or $e$ or the generated signatures or encrypted messages, and so cannot affect the security of a generated public key.  In any case, when you're doing the RSA private operation, you generally use the CRT optimization, and so you don't actually use the value $d$ directly (and a larger than necessary value of $d$ would give you exactly the same CRT parameters).

The bottom line is that if you need to conform to these requirements, you'll need clarification on what the requirements actually are; the literal interpretation doesn't make sense.

Now, for your actual question: what is the purpose of this rule?  Well, the document does go on to give this justification (if I remember my French correctly):

  "Using specific private exponents (for example, small private exponents) to improve performance is forbidden because of practical published attacks in this area"

It appears that they are indeed worried about the published attacks against $d < N^{0.5}$, and possible refinements on that attack that might work for larger $d$.

As for the probability that a random public key will yield a small value of $d$, well, it turns out to be quite unlikely (if $e$ wasn't chosen specifically to make $d$ small).  The easiest way to see this is to assume a modest $e$ (for example, 65537), and note that

$$d \cdot e > \operatorname{lcm}(p-1, q-1)$$

and hence

$$d > \operatorname{lcm}(p-1, q-1)/e \approx \frac{N}{e \cdot \gcd(p-1, q-1)}.$$

Hence, $d$ cannot be small unless $\gcd(p-1, q-1)$ is large; that is, if $p-1$ and $q-1$ share a large common factor.  Because the probability of $\gcd(p-1, q-1) > k$ is $O(1/k)$, this means that in practice, a small $d$ never happens by chance.

Lastly, it isn't quite true that with other standards, there's no check on the value of $d$.  For example, FIPS 186-3 does have the requirement that $d > 2^{\mathit{nlen}/2}$.


Proof that Niederreiter Cryptosystem is correct I read about Niederreiter Cryptosystem. I understood the Key Generator, encryption and decryption of the cryptosystem, but if I want to prove that is a correct cryptosystem, what should I do?

To prove the correctness of an encryption scheme (not necessarily Niederreiter), you have to prove that for a honestly generated key pair, any honestly generated ciphertext decrypts correctly.

Formally, let $(pk, sk) \leftarrow KeyGen(1^\lambda)$ be the public and private key pair, and let $m$ be uniformally random in the (finite) plaintext space, and denote by $c \leftarrow Encrypt(pk, m)$ an encryption of message $m$ (pseudo-random in the ciphertext space) under the public key $pk$. Then you have to show that $Decrypt(sk, c) == m$ with overwhelming probability, meaning that either the decryption always succeeds if all steps were executed honestly, or it fails with probability negligible in the security parameter $\lambda$.

For instance, you prove the correctness of textbook RSA by showing that $(m^e)^d == m \bmod n$ for honestly generated $n=pq$, $\varphi(n)=(p-1)(q-1)$, $e$ coprime with $\varphi(n)$ and $d = e^{-1} \bmod \varphi(n)$.


Can AKE keys provide PFS Can the channel keys that are derived from an AKE (authenticated key exchange) protocol be used in a secure channel that wants to have perfect forward secrecy?

If the goal of AKE is to establish channel keys and provide authentication of the entities at the same time, then this implies that the long term key used for authentication is contributing to the shared channel key.

But if we want PFS, then the long term key should not be contributing to the channel key.

Meaning that if we want PFS you can not rely on AKE, but you should use a key establishment protocol that does not provide authentication and just authenticate the transcript afterwards.

So my question is: if we say that we use AKE to create our channel keys, does that mean that by definition of AKE we can no longer claim PFS of our secure channel?

In fact, if you use the first described password authenticated key exchange protocol (Encrypted Key Exchange, by Bellovin and Merrit, in 1992), it is quite clear that you get forward secrecy for free. Roughly put, this is a Diffie-Hellman key exchange with ephemeral keys, whose messages are then symmetrically encrypted, using the shared secret (the password) as key (this symmetric encryption must be such that decrypting with the wrong password still yields syntactically valid DH public keys). Even if an attacker learns the password, all he can do is to recover the inner DH exchange, that used ephemeral keys.

This is in fact a general property for all PAKE. The point of a PAKE is that both parties have only one long-term secret (the password), so everything else is ephemeral; moreover, since that secret has low entropy and is thus in range of exhaustive search (a "dictionary attack"), a strong PAKE must be such that whenever the attacker tries a potential password, he can never know whether he got the right one. This implies, in particular, that even if the password is revealed after the fact, the key exchange itself must remain impregnable. That password being the only non-ephemeral secret, the property of forward secrecy follows.

Or, said in the other direction: if a PAKE protocol is not forward-secure, and obtaining a copy of the shared password allows unraveling the subsequent data encryption, then that mechanism can be used to "test" passwords (run the break-the-encryption attack for each potential password, see if that yields a key which makes sense); in that case, the PAKE protocol does not fulfill its PAKE properties.

To sum up: contrary to what you fear, you will get forward secrecy because you use a PAKE protocol.

(Of course either party can still do something stupid and, for instance, save the secret key resulting from the PAKE into a file, which then breaks forward secrecy.)


Using a derived key for CMAC Consider the following authenticate-and-encrypt scheme that uses AES-128 in CBC mode for encryption and AES-128 - based CMAC for authentication:

Two keys are derived from the master key k (16 byte): SHA256(k) = k1 || k2 (k1 and k2 are each 16 byte long)
The plaintext x is encrypted using AES-128 and key k1: E_k1(x) = c
The CMAC is computed using AES-128 and key k2: CMAC_k2(x) = m
The result is the concatenation of the ciphertext and the MAC: c||m

We are asked to use this method and I am wondering if there are any problems with deriving the keys for the encryption and the MAC using SHA256 hash?

(I am aware of the discussion around authenticate-then-encrypt vs. encrypt-then-authenticate vs. authenticate-and-encrypt)

I see no reason why that would not be secure.  If you want to play it safe, though, you could always go with a standardized key derivation function, such as HKDF (RFC 5869) or one of the other KDFs listed in this draft standard.  (The draft itself seems to be expired, but it's the most convenient list of standardized key derivation functions I could find.)


How to let CA signed x509 key work in OpenPGP mailing system? So let's say we have a OpenPGP mailing system which all mails are signed and encrypted with OpenPGP keys. And now you bought a CA signed x509 certificate and you want to imement into the mailing system. What should you do is the best?

First option is stripping out the public/private key pair as both system uses RSA. But will this method also take away the fact that the key is certified by a CA? Like I mean how is the x509 system verify the key is certified? Do they confirm the public key with CA (which won't matter)? Or does they also rely on data includes in x509 certificate (which will matter as converting those into asc file might lose them).

Another way is to sign your OpenPGP public key with your x509 private key and send it with the mail. But is this method working as I thought? Supposing the receiver do have the system to verify the public key signed by x509 certificate. Also is there software(s) that can make it an automatic workflow like showing messages "the mail is signed with the public key attached", "the public key is signed by certificate signed by XXX" when the mail is opened.

The fact that you bought a certificate from an X.509 certification authority doesn't matter to any OpenPGP implementations I know of: when your friend opens the message you just sent them in their OpenPGP-enabled mailer, it won't care a whit about the X.509 CA a priori.

Not only would you have to shoehorn your certificate into the OpenPGP message format, but you would have to teach their mailer software to interpret it, and teach your friend to accept that particular CA.  It might be easier to teach your friend to accept S/MIME, if you really insist on this particular X.509 CA, with the caveat that S/MIME is a dumpster fire of shoddy '90s crypto engineering—or it would be easier to just use OpenPGP, which is also a dumpster fire of shoddy '90s crypto engineering but gets incremental improvements from time to time.


Choosing primes in the Paillier cryptosystem In the first step of key generation phase in Paillier cryptosystem given here.

It's given that

$$\operatorname{length}(p) = \operatorname{length}(q) ) \implies \operatorname{gcd}(pq,(p-1)(q-1))=1$$

where

$\operatorname{length}(k)$ = # bits in binary representation of $k$

$\operatorname{gcd}(a,b)$= greatest common divisor of $a,b$

How to prove the above equation, or where has it been proven?
In the third step of key generation, we have to select a random integer $g$ where $g \in \mathbb{Z}_{n^2}^*$ and in the step 2 of encryption we have to select a random integer $r$ where $r \in \mathbb{Z}_n^*$.

What I am wondering is "what is the known efficient way to select $g,r$ randomly". I mean whether we have to check in $\mathbb{Z}_{n^2}^*,\mathbb{Z}_n^*$ for such $g,r$ until $\operatorname{gcd}(g,n^2)=1$ and $\operatorname{gcd}(r,n)=1$ or is there any simple method while coding cryptosystem.
In the first step of encryption, it is given that plain text $m\in \mathbb{Z}_n$ .

So $m < n$ .

Suppose we are going to encrypt $k$-bit messages , so our $n$ must be $l$-bit
number, where $l>k$.

We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes  since $m<n$ .

Is this correct?

Since $p$ and $q$ are primes, the only factors you need to rule out are those two numbers.

Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, so its binary representation is longer.

A similar argument proves $q$ can't be a factor. Thus, the GCD must be $1$.
If you just pick a random $g$ modulo $n^2$ the odds that it is a good choice are high (for large primes), so you usually only have to verify once. However, like your Wikipedia link states, you can just choose $g=n+1$ (when your primes are as long).

For $r$ you are also likely to get a good number randomly, but there you do have to check that neither $p$ nor $q$ divides it.

  We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes  since $m<n$ .

If you multiply two $s$-bit numbers the product is always either a $2s-1$-bit number or a $2s$-bit number. (Here an $s$-bit number means one which has its $s$th bit set.)

To allow any $k$-bit messages, it is necessary that $2s-1>k$, so $s=k/2+1$ is enough.


RSA Inverse Multiplication I have $n,e$ and $c$, $p$ and $q$ are prime, but $q$ is the inverse multiplication of $e$ and $p$ so $$q = e^{-1} \bmod p$$
How can $i$ get $p$ and $q$ back?

If $e$ is not too large, then it is easy.
The relation $q = e^{-1} \mod p$ can be rearranged to $qe = 1 + kp$ for some integer $k$; or in other words, $p/q \approx e / k$; that is, $p/q$ is extremely close to a simple rational, and that makes factorization easy.


How to XOR two hexa numbers by hand fast I have an upcoming exam where I can use a simple Calculator. On some sample questions they ask us to XOR two values (for AES round key) and I know how to write it out by hand but is there any other faster way as the exam is timed of course.

If you are lucky, the definition of "simple calculator" may include all non-graphic calculators. In that case, you can use a Casio FX-115ES Plus, which includes hexadecimal and octal base modes, and has an XOR operator. It can operate on groups of octets up to 32 bits.

If you are not that lucky, the XOR table is your best friend. Depending on how many calculations you need to perform, it may very well be faster to create one on a scratch sheet during the exam. You may even be allowed to bring one with you.

I had a requirement for an XOR table to perform quick calculations on a printed code book for cryptographically strong communication over a public voice channel. It also had to be done quickly without the use of a computer or any electronic device, and had to fit on a small 4x6 sheet in the space under the ciphertext.

I came up with several methods to condense the table and still have it usable. If you are clever and resourceful, the knowledge of how to create the condensed versions can allow you to very quickly perform many XOR calculations. There is a recursive pattern to the hexadecimal XOR table which can be exploited, the table above is color coded to show this pattern, which extends down to the individual characters. Here are the condensed tables:

While the above table takes up less space, it has the same amount of characters, and thus takes about the same amount of time to create. A simple rule is required to select the correct characters.

The next level now takes both half the space of the previous, as well as half the characters. The rule is more complex, but a few minutes of practice makes it almost as fast to use as the full table. Even the rule can be simplified with XOR, the result will be correct if the XOR of the rule selections is 1.

The final level is once again half the space and half the characters (almost) as the previous, while requiring an additional rule to get the job done. If you remember the recursive structure and the basic layout of this table, you can recreate it in under a minute with a pen and paper.

Start with the inner column header, first nibble; 0 1 2 3 4 5 6 7
Then add the 2nd nibble, which is the first nibble + 8; 8 9 A B C D E F
The outer column header is the inner column header with the halves flipped
The inner row header is the first half of the inner col header
The outer row header is the first half of the outer col header
Then you fill in the table with the recursive structure, built from the inner column header.
Creating the double compressed table omits the outer headers but uses a full row header.

A single example on the triple table:

25 XOR B6
2 X B = [2a] X [3b] (1 2 2) = 9
Because 2 is the 1st nibble and B is the 2nd, we use the 2nd nibble of [19]
5 X 6 = [5d] x [6e] (1 1 1) = 3
Because 5 is the 1st nibble and 6 is the 1st, we use the 1st nibble of [3b]
Therefore 25 XOR B6 = 93


Creating own ciphertext after a padding oracle attack? I've written a script that breaks a cipher text based on a padding oracle for an assignment, but was wondering how I would continue on to create my own cipher text with any plain text I desired?

Someone on the class forum mentioned XORing the intermediate step (or the $D(C_i)$ before XOR with $C_{i-1}$) (taken from the process of breaking the original cipher text) with the plain text of my choice to generate $C_{i-1}$. I don't see how this works, or if I misunderstood what the poster was XORing together. I see how $D(C_i) \oplus C_{i-1} = P_i$, but not sure how you can use your own plain text in that way.

I'm looking for hints on how to approach this, or a clarification on the 2nd paragraph.

You should be able to generate a ciphertext for any given plaintext using a padding oracle attack if you are using CBC mode. You'll need to be able to  modify the IV though for it to fully work.

This is because every time you scramble an earlier block, you can just fix it by modifying the cipertext for the block before that (or the IV for the first block). If you can't modify the IV you are stuck with being able to modify all blocks except for the first (and the first one will become garbage).

The idea is to start from the end, and create a random ciphertext block $C_n$ (this can be fully random, a set of zeros, or any particular value you desire). When you then use the padding oracle attack against this block, you'll receive the decrypted value of this block: $\operatorname{Dec}(C_n)$ (as that is what the padding oracle can do for you: decrypt any ciphertext you pass into it, no matter whether it's valid or not).

Note, that $\operatorname{Dec}(C_n)$ will be garbage, but, since you are using CBC mode you can modify the preceding block $C_{n-1}$ in a way so it will actually XOR $\operatorname{Dec}(C_n)$ to your chosen plaintext $P_n$: $C_{n-1} := \operatorname{Dec}(C_n) \oplus P_n$.

Once you're done, continue the steps. You already know $C_{n-1}$, calculate $\operatorname{Dec}(C_{n-1})$ using the oracle, and then set $C_{n-2}$ so the CBC mode will XOR it into $P_{n-1}$, etc.

The only problem is with the first block. If you have access to set the $IV$ then it's not a problem, you just make sure the $IV$ is set to a value so it will XOR $\operatorname{Dec}(C_1)$ into $P_1$. Otherwise you are stuck, and you have to keep the first block as garbage.

See also https://crypto.stackexchange.com/a/50027/34606


Is OpenPGP vulnerable to the "crypto doom principle"? From reading RFC 2015 (MIME security with PGP), and from looking at the raw format of (GnuPG) encrypted and digitally signed email messages, it seems that first a signature is calculated from the plain text message, and then both are encrypted.

My question is why isn't this vulnerable to what Moxie Marlinspike dubs the "cryptographic doom principle" (basically, if you have to do any crypto operation before checking the signature, bad things will happen)? I suppose the reason (alongside the devil) will be in the details, in the particular way the "sign-then-encrypt" operation is implemented. But I've been unable to find (or more likely to make sense) of those details. Can anyone shed some light?

The answer (to the title question) is no, due to a slight mixup in terminology. What Moxie says is (emphasis added)

  if you have to perform any cryptographic operation before verifying the MAC on a message you’ve received, it will somehow inevitably lead to doom.

Notice that he says MAC and not signature. The PGP group has discussed this too, so you are not alone in your concern.

In other words, mac-then-encrypt is not the same thing as sign-then-encrypt. Sign-then-encrypt is preferred to encrypt-then-sign. For more discussion on sign-then-encrypt see this question and answers.


Format Preserving Encryption after compression algorithm? I have large data set which has sensitive information. I want to encrypt different parts of it with different keys. There is also need for compression as data is very large (100s of GB that has to be distributed to users that have got permission).

I have been reading about format preserving encryption and would like to use it. I would like to know if its a good idea to use FPE after compression or would that even make sense.

I have been reading about format preserving encryption and would like to use it.

There are many good reasons for using FPE, but this is certainly not one of them.

It's OK to get excited about a solution but you should not apply that solution regardless if it fits the problem.

This reminds me of a developer I knew that wanted to use each and every pattern he encountered. Pattern driven development: "we have this programming pattern, now which problem do we need fixing?"

  I would like to know if its a good idea to use FPE after compression or would that even make sense.

No, it doesn't make sense. Compression generally compressed to bytes, and bytes can be encrypted fine. FPE is mainly used where there is no easy byte or bit conversion possible, e.g. when the output needs to be a number or a specific range or characters. The most common example is the format of credit card numbers.

Besides that, FPE may add quite a bit of overhead; you certainly don't want to process 100s of GB of data with it.


Does SHA-1024 hash exist? Does SHA-1024 cryptographic hash function exist similarly to SHA-512? If not, what's the reason for that?

Links:

SHA-2 at Wikipedia
SHA-3 at Wikipedia

No, because even SHA-512 was considered overkill from a security perspective. It has 256-bit collision resistance, which is unbreakable. (The link is about keys but a similar argument applies.)

If you think large quantum computers will be efficient, a 512-bit hash makes some sense, but even then a 1024-bit one wouldn't. A quantum computer requires $O(2^{n/3})$ operations to find break the collision resistance of a secure $n$-bit hash.

Finally, SHA-256 uses 32-bit words and SHA-512 64-bit. If you wanted to use the same way to extend SHA to 1024-bit state, you would need to use 128-bit operations which are slow on practically all platforms.


Is the identity function a one-way function? The definition of the one way function says:

it must be verifiable in polynomial time
probability of inverting it less or equal to negligible

Now, I am not sure I fully understand one way functions.

Can I say that $f(x) = x$ is a one way function?
Do we assume that we know how $f$ is defined?
if $x$ is of length $l$, then the probability of guessing it is: $(1/2)^l$ which is negligible.

I am pretty sure that my reasoning is wrong, any hint?

It is not one-way because there is an efficient algorithm which inverts it with probability $1$; namely an algorithm which simply outputs its input.

The fact that we "know the function" is implicit in that no restriction is placed on how the algorithm is "devised", it is only required that such an algorithm exists.


What is the correct test/s to do in asymmetric algorithms to test their security? I would do some test for evaluating security in asymmetric algorithms such as RSA and ElGamal to evaluate which of both are safer.

The basic problem is that I need to test the security of some symmetric and asymmetric algorithms to evaluate their security and to know which algorithm is more secure and his strength against real-time attacks. In both type of algorithms I have made a table with their vulnerabilities, but I want to test their security with some specific test. Then, I need a test that allows me to conclude that algorithm is safer, for both symmetric and asymmetric algorithms.

For instance, in symmetric algorithms the test that you can use is the avalanche effect link, but in asymmetric algorithms I have not found anyone and I only know that the avalanche effect is not for this type of cryptography.

Any suggestions on the possible test?

If you're looking to test the parameters for an RSA or ElGamal implementation, well, that's fairly straightforward (assuming you can look at the innards of the implementation, and ask "are these primes drawn from a random distribution, do you get the RSA padding right, are you secure against the relevant side channel attacks, etc).  You really do need to know your crypto, but it's not that hard.

On the other hand, if you've devised your own public key cryptosystem, well, that's much harder.  Actually, symmetric cryptosystems aren't that much easier; the 'avalanche' test that you alluded to is a very weak test; a cipher can easily pass that with flying colors, and still be very weak.

In both cases, the real test is 'can a clever individual who has access to the ciphertext, possibly some plaintext, and (in the case of public key cryptosystems) the public key find an attack'.  That's not an easy question to answer (or so you hope, if there is an easy answer, it's be 'yes, here's this attack').

With public key cryptosytems, the obvious place to start is the 'hard problem' they're based on; why precisely do we think it's hard.  For RSA, well, it's the "RSA problem" (typically, people say factoring, however that's not proven to be true); for ElGamal, it's the Diffie-Hellman problem.  In your case, you need to consider what problem makes it easy (with a public key) to perform in one direction, and hard (with a public key, but not the private) to perform in the other direction.

Issues with the hard problem aren't the only possible way a system can fail (consider RSA with no padding; the RSA problem remains hard, but we can find ways to break the system by taking advantage of the homomorphic properties of raw RSA); however it's the obvious place to start.


Dependence on Keyed Hash Function I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states:

  With an ACR hash function $F$ the key $K$ is announced and the adversary wins if she manages to any collision $M,M'$ for $f = F_K$. The points $M$ and $M'$ may depend arbitrarily on $K$.

Could you give me an example of messages $M$ and $M'$, so that they depend arbitrarily on $K$?

My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance

Say $F_K(x)$ = $M \bmod K$.

Then after $K$ is announced choose arbitrary $M$ and compute $M' = M + K$.


Any reason to use Shamir given faster XOR threshold secret sharing algos? TL;DR:

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)?

https://scholar.google.com/scholar?q=kurihara+secret+sharing

Background

Shamir's secret sharing algorithm has the desirable properties of information theoretic security (possessing shares fewer than the threshold is no better than random data) and minimal storage (each distributed share is the same size as the original secret).  However, it's very slow to compute, to the point that when dispersing a large file with Shamir you would typically use ordinary symmetric encryption for the file at large and protect only the symmetric key with Shamir.

As of around the year 2007 industrial researchers in Japan (Kurihara et alia at KDDI and others at Toshiba) and academics in China (Chunli et alia) have published papers showing how to use random numbers with simple XOR operations to accomplish the same level of information theoretic security and minimal storage, with performance hundreds of times better than Shamir Secret Sharing.  Some of the algorithms offer arbitrary "(k, n)", aka "(threshold, sharecount)" flexibility, as Shamir also does.

Is there any reason to continue using Shamir versus the new XOR based threshold secret sharing algorithms?

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)?

The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent.

As for the speed benefits being marginal, well, normally we use secret sharing as a part of an overall algorithm achieving something else, and the time taken by the secret sharing algorithm is dominated by something else, and so the time taken doesn't really matter.

As for the speed benefits being marginal, well, that's because Shamir's method really is quite efficient; the generation of a share (once you've generated the randomess) is $k-1$ field multiplications and $k-1$ field adds; if you use the field $GF(256)$, this can be done with $2k-1$ table lookups, $k-1$ adds and $k-1$ xors.  The recombination step (once you've converted the id's into coefficients) is $k$ field multiplications and $k-1$ field adds; similarly cheap.

Now, you ask, why does the paper claim to do so much better than Shamir?  Well, that's because they were testing it against a Secret Sharing implementation that was never designed for performance.  If you look into the implementation of SSSS, you'll see that it uses the GMP bignum library to perform the operations.  Since the internal operations it uses are cheap (exclusive-or and shift left by one), the vast bulk of the time is spent in memory management (allocating and freeing memory).  Furthermore, the field multiply implementation it uses is a generic one; if one is greatly concerned with speed, one could do better by optimizing for a specific field size (as I mentioned, a moderate sized field such as $GF(256)$ can be done quite fast using log and antilog tables).

Now, to be clear, I'm not saying that the SSSS implementation is bad; what I am saying that performance wasn't very high on the developers list.  However, if speed is considered important, one can do quite a lot better.

As for your overall question, 'given that there are alternatives to Shamir, why do people generally stick with it?', well, I suspect that it's a combination of Shamir is good enough (a good implementation should run in a time that's competitive to Kulihara, and in any case, an I mentioned, we generally don't care), and that Shamir was the first (and people tend to stick with what's first - remember, people are still using RSA, even though we have better alternatives available).


How does IBM's 53-bit quantum computer compare to classical ones for cryptanalytic tasks? IBM just announced "a new 53-qubit quantum computer".

How does it compare to classical computers, performance-wise, for cryptanalytic tasks? E.g. finding a 48- or 64-bit value whose SHA-256 has a certain value (edit: or factoring the product of two distinct primes, or computing some discrete logarithm).

How does it compare to classical computers, performance-wise, for cryptanalytic tasks?

Not at all - IBM's quantum computer cannot perform any nontrivial cryptanalytic task.

For one, 53 physical qubits far too few to do anything interesting; for example, implementing SHA-256 would take thousands of logical qubits.

For another, the qubits are not even close to be reliable enough.  The IBM quantum computer cannot do any quantum error correction - this means that, as it performs operations on the qubits, the errors pile up.  Any interesting cryptanalytic task requires us to perform millions (or more) of quantum operations; even a slight amount of error accumulation would overwhelm any result.


Restricting output of key derivation function Are there any suitable key derivation functions that allow the output to have certain constraints applied to them?`

I know you can choose a length in some functions (HKDF for example), but what about restricting the output to conform to a subset of the printable ASCII set, such as [a-Z][A-Z][0-9].

Thanks

Modern cryptography operates mostly on binary values or big numbers. And generally cryptography that operates on numbers encodes / decodes those numbers to binary as well (RSA PKCS#1 specifies binary representations for the public key, private key and of course the ciphertext and signatures). If an API specifies text input / output it is generally provided as a convenience to the programmer rather than that it is part of the implemented algorithm specification.

To have printable ASCII it is easiest to convert the binary value generated by your KDF to base64 or base64url. In that case each character encodes 6 bits. It should be easy to calculate the output size of the KDF to give the precise amount of base 64 characters. Otherwise you could still cut of the left over base 64 characters, but remember that base 64 implementations may require you to input 4 characters at a time (including padding characters) making it impossible to decode your pruned base 64 encoding directly. It would make sense to use a multiple of 3 for the output of the KDF / multiple of 4 characters after encoding using base 64.

To have base 62 (as specified in your question) is much harder, as 62 is not a power of two. That means that you either need to perform base conversion using big integer calculations (divide-and-remainder) or you'll have to convert to base64 and escape out three characters (the +, the / and the escape character itself). Escaping will result in a variable length encoding though, maxing out on doubling the base64 string in size.

Notes:

Hexadecimals is even easier to work with: it takes 2 characters per byte, and that's it. It will expand the output some more, but that may be worth it for the convenience it offers;
Encoding keying material in a textual string is generally frowned upon. Strings are easy to find in application code and are generally hard to destroy (e.g. Java has immutable strings that may not be garbage collected either).


What is the limit of plaintext required to break the Vigenère encryption? A theoretical question about the Vigenère cipher:

Without any knowledge about the key (not even it's length) can we tell how much known or chosen plaintext is needed for the adversary to completely recover the key?
What about if we know the key length? (I assume that we'll need plaintext with the same length of the key).

For chosen plaintext and a classic Vigenère cipher, you need only as many characters of plaintext as the length of the key to completely recover the key. It's a trivial reversal. (If the cipher uses 26 scrambled alphabets, it will take more.) if you don't know the length of the key, you will spot the repeating sequence after the second repeat.

For an unknown ciphertext, that's when it gets interesting. You need enough repeats of the keylength to measure the index of coincidence. The Friedman test provides a way to estimate the amount of ciphertext.


Can I use MAC as CTR mode nonce, if my messages are non-repeating? I design encryption for a network protocol with restrictively low MTU. I'm aiming at 128 bit strength; AES-128-CCM would add 128 nonce bits and 128 MAC bits to each packet. Such MTU reduction by 32 bytes is not acceptable and I must come up with a solution which adds smaller overhead.

The protocol messages do not repeat between re-keying, because they contain large enough sequence number (I can specify how often to re-key).

Question: Can I use the packet MAC as the nonce for the CTR mode encryption?

AFAIK the only requirement for the "counter" value is that it does not repeat for the same key, and that is guaranteed by message uniqueness (assuming MACs would not collide). Such "reuse" would save me 16 nonce bytes in each packet.

Yes, but to use a known algorithm that specifies precisely that, take a look at the SIV mode of operation . "SIV" stands for Synthetic IV. IV is the initialization vector, which is the nonce (or the nonce and initial counter value, depending on the definitions).

Unsurprisingly it relies on CTR mode for confidentiality and CMAC for the authentication tag that doubles as IV - much like CCM.

The problem with CCM is that you would have a chicken/egg problem as the MAC is calculated at the end of the protocol. Although you could implement the protocol differently, I'd recommend to use a tried and tested mode instead.

Besides that, CCM mode is - at least in my opinion - a horrible mode to implement.

SIV does have the problem that it is a full two pass protocol; you will have to go over each packet twice to encrypt: one pass for creating the SIV and on pass to encrypt. Decryption is easier as you already have the IV ready, so you can at least combine the two passes.


What is different between G1×G1→GT and G1×G2→GT in the bilinear pairing? It is an implementation of the bls12-381 algorithm known as pairing-friendly, at GitHub.
Looking at this, the pairing parameters are $G_1$ and $G_2$,
$G_1$ is the point of $F_q$, $G_2$ is the point of $F_{q^2}$.
However, some papers describe it as follows.

Bilinear Map Let G1, G2 be two cyclic groups of prime modulo p. Let g
be a primitive root (i.e. generator) of G1. A bilinear map [10] or
bilinear pairing „e‟ is an effectively calculable task e : G1 × G1 →
G2 such that it satisfies the below two conditions,

Non degeneracy: e(g, g) ≠ 1.
Bilinearity: e(gx, gy) = e(g, g)xy for all x, y ∈ Z.

Setup: Let E(Fq) be an elliptic curve above the fixed field Fq where q
is large prime number (at least 160 bits) and G be a point on elliptic
curve E of order n. Let G1, G2 be two multiplicative cyclic groups of
prime modulo n. Let e : G1 × G1 → G2 be a bilinear map, z = e(G1, G1)
∈ G2.

$$z = e(G_1, G_1)$$
Here, both parameters take the point of $F_q$. How are they different?

The most general form of a bilinear map is $e : G_1 \times G_2 \to G_T$. We can categorize a scheme's usage of the bilinear map into 3 standard categories:

Type 1: in addition to the bilinear pairing, the scheme requires efficiently computable homomorphisms $\phi_{12} : G_1 \to G_2$ and $\phi_{21} : G_2 \to G_1$. In other words, the scheme sometimes needs to "convert/cast" a $G_1$-element to a $G_2$-element and vice-versa. This is the same thing as requiring that $G_1 = G_2$.

Type 2: the scheme requires an efficient homomorphism $\phi_{12} : G_1 \to G_2$. In other words, the scheme sometimes needs to "convert/cast" a $G_1$-element into a $G_2$-element (but not vice-versa).

Type 3: the scheme never needs to "convert/cast" between groups.

See Pairings for Cryptographers by Galbraith, Paterson, and Smart for more discussion about these types (especially section 2).
Type 3 is the most desirable since it places the fewest restrictions on the bilinear map. Type 1 demands a lot of structure from the bilinear map, and I think type-1-compatible groups/pairings are less efficient.


nonce generation on AES CCM* I want to encrypt with AES CCM* and i dont understand the nonce generation.
the toolkit i'm using has a function to generate the nonce for CCM but it needs the following params:

param src_addr      The MAC address in EUI-64 format.
param frame_counter The MAC frame counter.
param size_of_t     AES-CCM* MAC (tag) byte size. Valid values = [0,4,8,16].

i know the MAC size but how do i get the other parameters BEFORE even running init?

i know the MAC size but how do i get the other parameters BEFORE even running init?

This is one of the cases where you have to deal with two different expansions of the acronym "MAC": Medium Access Control and Message Authentication Tag. The first two points, ie the MAC address and the MAC frame counter refer to the Media Accesss Control expansion, ie the (link-layer) address of the peer you want to communicate with and the (link-layer) sequence counter of the current message packet. The MAC tag size refers to the actual Message Authentication Code tag of CCM*.

  so in testing it should be random?

This depends on the tests you want to do. In some cases it makes sense to randomize these values, eg if you just test whether encrypt and decryption works. In other cases, eg when you want to test against test vectors, the randomness will not be helpful / will make verification of operationality of the system harder.


How can an interactive ZKP become non-interactive? From my understanding, random oracles (hash functions) are used in the Fiat-Shamir heuristic to generate non-interactive ZKPs. I think I have a good grasp of how interactive ZKPs in this scheme work, but I am still struggling to understand how proofs can become non-interactive, from a high-level perspective.

In the Alibaba Cave example, I understand how interactivity can be used to prove that one party has a secret S. I have seen examples where the prover generates a hash of the solution to predetermined challenges of statistical significance, but how could the verifier recreate the hash of that challenge?

Warning: Oversimplified.

Most, if not all interactive Zero-Knowledge proofs rely on the randomness of the verifier. Taking the Ali Baba cave example, since Alice cannot predict what path Bob wants her to come out of, it is statistically improbable that she will be able to fake the proof, especially when this "experiment" is done multiple times.

In case you don't know, a hash funtion is a pseudo-random function. This means that, given the same input, it will always generate the same output. A cryptographic hash function is a one-way function, one where it is infeasible to create a preimage attack, or simply put, finding X in H(X)=Y, given only Y.

The Fiat-Shamir heuristic simply replaces the verifier's randomness (and therefore the interaction) with a random oracle, or in concrete terms, a cryptographic hash function. Since the prover cannot predict the output of a cryptographic hash function, this provides the randomness necessary for the scheme to work.

In that case, Alice wants to prove that she can unlock the door in a cave C. She goes inside the cave, generates a hash H(C), and depending on the output, goes in either path A or B and comes out the other path. Bob, without ever telling Alice anything, simply checks that Alice went through the correct path (if H(C)=A or H(C)=B) and that she exited through the other path.

You could adapt this to make it harder to fake, by computing H(C||n) instead of H(C), where n is a number starting from 0 that increases by 1 every time the experiment is conducted, and running the experiment multiple times.

This Wikipedia article is a really good one and gives a more concrete example.


Derive a public EC key from two public EC keys Alice has two EC key pairs: $a_1$, $a_2$ are private keys (integers), $A_1$, $A_2$ are the corresponding public keys (points). Alice and Bob want to create a new public key $C$. Alice must prove that this key $C$ was created from exactly $A_1$ and $A_2$, i.e. Alice did not use other key pairs for $C$. The new public key $C$ would be used for ECDSA. The private key $c$ is created from $a_1$ and $a_2$ and is usable for ECDSA with $C$. The private key $c$ must not be able to be created from only $a_1$ or only $a_2$.

The algorithm will be generalized to $n$ key pairs. My thoughts for case of 2 keys are below.

Which algorithm can be used for that? I have two ideas:

Addition of $A_1$ and $A_2$: $C = A_1 + A_2$. Bob can verify this, since he knows $A_1$ and $A_2$. The private key would be $c = a_1 + a_2$. This works because $(a_1+a_2) \cdot G = a_1 \cdot G + a_2 \cdot G = A_1 + A_2$. Clear. But how secure is it? Can an ECDSA signature of the public key $C$ be created without both $a_1$ and $a_2$? Maybe $a_1$ or $a_2$ only is enough for this? I don't know.
Multiplication. $C = a_1 \cdot a_2 \cdot G$. Verification is complicated if it is even possible. If Bob knows $A_1$, $A_2$ and $C$, how can he verify that $C$ was composed exactly from private keys corresponding to $A_1$ and $A_2$ (maybe with Alice's help, but without possessing ability to sign with $C$)?

Example of vulnerable verification (for proposal 2): Bob generates a random number $r$ (not available to Alice), computes $r \cdot A_1$ and asks Alice to multiply this by $a_2$. Alice sends $a_2 \cdot (r \cdot A_1)$ to Bob. $a_2 \cdot r \cdot A_1 = r \cdot a_1 \cdot a_2 \cdot G = r \cdot C$. Bob compares $a_2 \cdot (r \cdot A_1)$ sent by Alice with $C$. Then he does the same with $A_2$.

This is vulnerable: Alice computes $C = a_1' \cdot a_2' \cdot G$. Bob generates $r \cdot A_1$ and asks Alice to multiply it with $a_2$, Alice multiplies it with $a_2' \cdot (a_1'/a_1)$. So the result of the multiplication is $a_2' \cdot (a_1' / a_1) \cdot (r \cdot A_1) = a_2' \cdot (a_1' / a_1) \cdot (r \cdot a_1 \cdot G) = r \cdot a_2' \cdot a_1' \cdot G = r \cdot C$. So Bob mistakenly believes that $C$ is derived from $A_1$ and $A_2$. Division by $a_1$ is multiplication by $a_1^{-1}$, which can be calculated from $a_1$ using a multiplicative inverse.

Please, prove that algorithm proposed in item 1 (addition) is correct or provide correct verification for algorithm 2 (multiplication) or provide your own or existing algorithm which is appropriate for the task.

As long as there is a probability that the adversary has the access to a valid signature on the message $m$ using one of the private keys, none of the schemes would be secure, and also any other scheme which is using a linear combination of the keys as the resulting private key.

Because, if an adversary has two valid ECDSA signatures on message $m$ which one is made by private key $a_1$ and the other is made by private key $a_2$, she can produce any signature on message $m$ using the private key $c=b_1a_1+b_2a_2+b_3$ where $b_1$,$b_2$ and $b_3$ are known to the adversary. This is due to the homomorphic properties of Elgemal signature.

So other than the algorithm #2 the algorithm #1 (Addition) seems to be unsecure. Whereas, If an adversary has a valid ECDSA signature on message $m$ using private key $a_1$ and she knows $a_2$ then it can produce a valid signature on message $m$ using private key $c=a_1+a_2$ quit efficiently. In other words for breaking the scheme it suffices to have just one of the private keys, say $a_2$, and a valid signature produced using the other private key, say $a_1$.

For making the answer more concise, I'm using the notations in Wikipedia article ~ "Elliptic Curve DSA".

assume the signature on message $m$ made using private key $a_1$ is $(r,s)$ and the forged signature made for private key $c=a_1+a_2$ is $(r',s)$.

$(r,y_1)=kG=zs^{-1}G+rs^{-1}a_1G$

$(r',y_1')=(r,y_1)+rs^{-1}a_2G$


Cryptography of numbers Is there any algorithm capable of encrypt securely (symmetric) N numeric digits in a numeric message of M digits (N < M)? I am especially interested in a specific case in which N = 10 and M = N + 3. I tried the most famous algorithms, like DES and AES, but they did not get success. Does anyone know a way to encrypt messages with limitations like this?

One way of doing this is using a Format Preserving Encryption method.

This is a symmetric encryption method that is designed to convert (potentially) small messages into encrypted messages of exactly the same size.  For example, it may take strings of 13 decimal digits, and encrypt them into strings of 13 decimal digits.

One such method would be the FF3 method from NIST SP 800-38G; if you set radix=10, then it can encrypt a string of 13 digits, giving you a string of 13 digits (which is exactly what you want).

Here is how you would use it in your example: you would take your $N=10$ digit number, and extend it to $M=13$ digits by appending 3 0's.  Then, you'd hand your string of 13 digits (and the key) to the FPE algorithm to encrypt, and it'll give you another string of 13 digits; that's your ciphertext.  Decryption is the the opposite; FPE decryption of the 13 digits, and then strip off the last three 0's (and, if they're not 0, then the ciphertext was invalid)

There are existing techniques for encrypting messages that can't be expressed in an even number of radix digits; however since your messages can, there's no reason to involve those.

All three methods in 800-38G can handle radix=10; I suggest FF3 because the pseudocode listed for FF1 in the NIST draft is wrong (their decryption code isn't an exact inverse of their encryption code; yes, NIST knows this), and FF2 has known (academic) weaknesses.


Is it bad to tell someone what encryption algorithm your system uses? We have a customer asking about what methods we use to secure our system. Specifically they want to know what encryption algorithm we use for how we manage passwords. My philosophy is the harder it is for the bad people the better, so my mind set is keep as much secret as possible no matter how miniscule or how easily inferred the details can be. So I'm very hesitant to say anything.
We of course don't want to lose any business over this, so I guess my question is, is it ok to say we use "********" encryption algorithm? In other words, if you told someone what algorithm you use how much of a security breach could that be considered? Thanks in advance!

No, it's not bad to tell this info. In fact, it's suspicious when someone doesn't reveal the design of the system. Kerckhoffs's principle states that a system must remain secure so long as an attacker knows everything except a designated secret "key".
For symmetric encryption, "key" means secret keys. For asymmetric cryptography (signatures and key exchange) that means private keys. For password storage, that means the passwords themselves (and possibly a "pepper" value, if used).
I'd personally assume that anyone who isn't familiar with this is hiding a backdoor in their system. If the cryptography isn't auditable, it's safer to assume it's insecure and use an auditable (open-source or at least source-available) implementation whenever possible.


IV = Filename XOR CipherKey? i want to encrypt transparently using Rijndael. So this is, what I thought of and I would like to have an opinion from "Experts" whether this will harm encryption strenght.
I am using chunks of 1MB and give them a GUID as filename.
edit: The 1MB chunks are just out of performance reasons. Imagine a file of 500MB to decrypt, deflate change some bytes, compress again and encrypt again. Is it really that bad a security vulnerability?
These chunks are then first compresses using DEFLATE to minimize attacks based on known Content.
These chunks are then encrypted using Rijndael and a given Cipherkey. The IV will be created as an XOR of my Filename (the guid) and the Key behind the scenes.
edit: The IV is never stored, but always created anew from the GUID and the Key. As far as I understand, this is the IV only for the first cipher block in CBC. (GUID XOR Key) XOR Plaintext -> ciphering -> new IV for next block.
Is it possible to deduce the IV from ciphered data, without knowing the key? If so, this IS a bad idea. Otherwise I dont see the the disadvantage.
Would this be viewed more secure? Cipher the GUID with the key and an IV of Zeros and use this as the IV for my ciphering.
All chunks are then collected in an XML File, which is saved the same way but named as the original file name.
Will the creation of the IV harm the security in any way?
Am I doing something else terribly wrong?
Are there are other obvious weak spots that I am missing?

Thanks a lot!
Andreas

I am using chunks of 1MB and give them a GUID as filename

That is fine although unnecessary, the entire input file can be encrypted.

  These chunks are then first compresses using DEFLATE to minimize attacks based on known Content

VERY BAD idea, since you are breaking the input file into pieces, you are now exposing the entropy of specific file sections to an attacker. Either compress the file before you break it up, or do not break it up at all (or do not compress it)

  These chunks are then encrypted using Rijndael and a given Cipherkey. The IV will be created as an XOR of my Filename and the Key.

VERY BAD idea, now the attacker has the key. Use a random IV for CBC mode or a sequential IV for CTR mode. You have not specified your mode of operation.

  All chunks are then collected in an XML File, which is saved the same way but named as the original file name

I would keep the actual file name in the XML file in an encrypted format so you do not expose the potential file type or content. You can also keep hashes of the encrypted data, and integrity information in the XML file.

  Are there are other obvious weak spots that I am missing

Probably; your proposed IV generation scheme means you do not know enough about cryptography to be developing an encryption program, do more research and get more education on the subject before continuing. Cryptography Engineering would be a good starting point.


How you find the unpadded short plaintext using RSA? I am currently trying to understand how you find the unpadded short plaintext when you are using RSA. Please help with explaining the process and so I can understand this topic more.

As kelalaka hinted, the issue with particularly short plaintext in unpadded RSA is that it is subject to brute force via chosen plaintext attack.

For each plaintext $m$ in the short space you suspect the enciphered plaintext to originate from calculate $c = m^e \text{ mod } n$ where $e$ is the public encryption exponent and $n$ is the public modulus. Then compare $c$ to the ciphertext for which you are trying to find the plaintext. If identical, the message $m$ is the same as the padded short plaintext in question. Because RSA is deterministic, identical plaintexts produce identical ciphertexts.


How to decrypt Pohlig-Hellman cipher if e and (n-1) aren't relatively prime I couldn't find any articles that addressed to how to decrypt c after it was encrypted using the Pohlig-Hellman cipher if $e$ and $n-1$ aren't relatively.
Can someone please tell me how to do it?
I couldn't find an questions about this on StackExchange.

It is essentially the same as the answer I gave in How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?, with the same restrictions ($e$ assumed prime, $e^2$ assumed not to be a divisor of $p-1$), with the sole change being that $\lambda = p - 1$.
It's easy enough to cover the composite $e$ case (factor $e$ into primes $e = r_1 r_2 … r_n$, and then find solutions for $c = m^{r_1 r_2 … r_n}$ by inverting each $r_i$ individually.
The other case $e^2$ is a divisor of $p-1$ is a lot tougher, and probably needs a different approach...


What is cryptographic sealing? While revising my CAdES library I encountered some "sealing issue" in digital signatures.

The Win SDK signtool.exe has a /seal parameter which produces 1 authenticated attribute in the signature "Intent to Seal" and one unauthenticated attribute "Sealing Signature" in the signed file.

I 've also seen that in PDF files. Couldn't find more online on it.

My questions are:

What is the purpose of "sealing" vs simply signing a message?
What are the OIDs associated with them? What are the relative RFCs?
Is it simply a matter of adding 2 attributes in the PKCS#7 or is there another issue I must take into account?
Is there a difference when timestamping a "sealed" message?

Cryptographic sealing is the application of asymmetric cryptography to encrypt a session key so that it cannot be used-- until it is decided to remove the seal and use the key.  It is a protection mechanism. See this description from Oracle:

  Sealing the symmetric key involves creating a sealed object that uses
  an asymmetric cipher to seal (encrypt) the session key. The RSA
  asymmetric algorithm cannot be used because it has the size
  restrictions described in the next section, and the sealing process
  makes the session key too large to use with the RSA algorithm.

The idea of cryptographic sealing has been around for a long time. A paper from 1981, Cryptographic Sealing for Information Secrecy and Authentication., by David K. Gifford, goes into interesting detail about it:

  A new protection mechanism is described that provides general
  primitives for protection and authentication. The mechanism is based
  on the idea of sealing an object with a key. Sealed objects are
  self-authenticating, and in the absence of an appropriate set of keys,
  only provide information about the size of their contents. New keys
  can be freely created at any time, and keys can also be derived from
  existing keys with operators that include Key-And and Key-Or. This
  flexibility allows the protection mechanism to implement common
  protection mechanisms such as capabilities, access control lists, and
  information flow control. The mechanism is enforced with a synthesis
  of conventional cryptography, public-key cryptography, and a threshold
  scheme.

So, the purpose of sealing is very different from that of signing.  Sealing prevents use of a session key. I have been unable to find any RFCs that deal with sealing.  Nor have I found any applicable OIDs. The timestamping involved in sealing, as far as the encryption process goes, will be the same as normal, as far as I can see. RFC 5652 (Cryptographic Message Syntax) does not specifically mention cryptographic sealing.