RFID Protocol Cryptanalysis Assume we have the following scheme for RFID:
TAG & READER both have initially k keys.
Every session the TAG computes $k_i$=F($k_{i-1})$ where F is a function which computes XOR of previous key with randomly generated number, e.g. $k_i^R$=F($k_{i-1}^L$) $\oplus$ $r_i$ , $k_i^L$=F($k_{i-1}^R$) $\oplus$ $r_i$ where $r_i$ is a random number for session i. The READER receives ($k_i$, $r_i$) and performs same computation to verify $k_i$. If its correct replies with True either False. If READER replied True - they both add $r_i$ to the key set.
If reader replied FALSE or message didn't arrive - key set are not updated.
(if the message didn't arrive, READER does not respond at all).

I've read that one of the possible ways for analyzing this protocol is by creating a table of all possible keys which can be generated after obtaining $k_i$ and then looking for repeating rows.

What are other possible ways to analyze this scheme in order to find  vulnerabilities ?

Thank you

Edit: I've clarified more the question for what I asked, are techniques for analyzing the protocol disregarding technical problems like lost messages.

As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync.  (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey".  But the current protocol, as described, does not have this feature.  Also, note that this would have its own security implications, which would need to be analyzed.)

This protocol also has the inconvenient feature that each tag can only work for one reader, at least unless the readers communicate with each other to synchronize their state, or unless the tag actually holds multiple keysets, and uses some kind of a handshake with the reader to decide which key to send.  (Again, neither of these features are part of the protocol as decribed, and so their security implications cannot be analyzed reliably.)

The fact that the protocol requires the tag to generate random numbers also worries me a bit.  I'm not really familiar with the state of the art in RFID, but generally, securely generating unpredictable random numbers is not a trivial task.  The protocol appears to be designed for tags that have very minimal computing capabilities, so I wouldn't fell comfortable automatically assuming that such a tag has a cryptographically secure RNG.

Also, obviously, 4-bit keys are trivially vulnerable to brute force attacks, but that's easy enough to fix.  In the rest of this answer, I'll assume that the actual key length is at least 128 bits or so.

Even if all the issues mentioned above are addressed, though, the protocol as described has (at least) two obvious and serious security flaws:

An eavesdropper can impersonate the tag after observing four consecutive successful authentications.  The random numbers generated by the tag are transmitted in the clear, and the keys depend only on the last four random numbers, so knowledge of those four numbers automatically lets an attacker compute the key.

When using the key thus obtained, a clever attacker could also perform four consecutive authentications, and recycle the random numbers so that the reader ends up in the same state it was in before.  That way, the holder of the valid tag need not notice anything unusual, as their tag will still be in perfect sync with the reader.

(In fact, since the XORed key is also sent in plain, it's enough to observe the latest transaction and the fourth one before it.  This is not enough to fully determine the state of the tag, but it does suffice for one fake authentication.)
The attacker doesn't even need to get near the reader to carry out this attacks, since it's trivial to impersonate the reader.  The fake reader can just reply "true" to anything the tag sends it.  This allows a number of attacks:

An attacker can impersonate the reader, and (possibly after some delay) relay the tag's key and random number to the real reader.  This will allow the attacker to authenticate as if they had the tag, and any logs will show the tag being used normally.
Alternatively, an attacker with a fake reader can query the tag four times, replaying "true" every time, and thus steal the full state of the tag.  At that point, the real tag will no longer work (until and unless the attacker deliberately sends the same sequence of four random numbers to the real reader to re-sync its state), but the attacker can now authenticate with the reader as many times as they like.

There are ways to address all of these issues, but honestly, by the time you've fixed them all, the result will no longer bear more than a passing resemblance to your original protocol.  So, no, this is not a secure authentication protocol.


Is it possible to decrypt an ECDSA private key if the same nonce is used across different private keys? If the same nonce is used across different messages under the same private key, the private key can be easily revealed.

However, let's consider another scenario.

Two private keys, x1 and x2, are used with the same pair of nonces, k1 and k2. Thus, for each pair of signature (r,s) and hash message h, we get:

$$ s_1=k_1^{-1}(h_1+r_1x_1) \pmod p $$

$$ s_2=k_1^{-1}(h_2+r_1x_2) \pmod p $$

$$ s_3=k_2^{-1}(h_3+r_2x_1) \pmod p $$

$$ s_4=k_2^{-1}(h_4+r_2x_2) \pmod p $$

Therefore, no nonce is used twice by the same private key, but nonces have been reused across different private keys.

Is it possible to retrieve x1 and x2 in this scenario? From what I can observe, the four equations are linearly independent withe each other and consist of four variables. Therefore, there are unique solutions for x1 and x2, right?

Or did I miss something?

SOURCE: This idea was first suggested in this paper: https://link.springer.com/chapter/10.1007/978-3-030-00470-5_29

Is it possible to retrieve $x_1$ and $x_2$ in this scenario?

Yes. We multiply each equation by it's corresponding $k_i$ and reformat, giving
$$\begin{array}{rrrrrrr}
s_1\,k_1&&-r_1\,x_1&&\equiv&h_1&\pmod p\\
s_2\,k_1&&&-r_1\,x_2&\equiv&h_2&\pmod p\\
&s_3\,k_2&-r_2\,x_1&&\equiv&h_3&\pmod p\\
&s_4\,k_2&&-r_2\,x_2&\equiv&h_4&\pmod p
\end{array}$$
and that's a linear system of 4 equations in field $\Bbb Z_p$ with 4 unknowns $k_1$, $k_2$, $x_1$, $x_2$ for one knowing the 4 signatures and (the hash of) their respective messages. It has unique solutions except if $s_1\,s_4\equiv s_2\,s_3\pmod p$, which has no reason to hold, since the $s_i$ are non-zero and randomized at least by their respective $h_i$.

If I got the details right,
$$x_1=\frac{h_1\,r_2\,s_2\,s_3-h_2\,r_2\,s_1\,s_3-h_3\,r_1\,s_1\,s_4+h_4\,r_1\,s_1\,s_3}{r_1\,r_2\,(s_1\,s_4-s_2\,s_3)}\bmod p\\
x_2=\frac{h_1\,r_2\,s_2\,s_4-h_2\,r_2\,s_1\,s_4-h_3\,r_1\,s_2\,s_4+h_4\,r_1\,s_2\,s_3}{r_1\,r_2\,(s_2\,s_3-s_1\,s_4)}\bmod p$$
where operations including division are in the multiplicative group $\Bbb Z_p^*$.

Michael Brengel and Christian Rossow's Identifying Key Leakage of Bitcoin Users (in proceedings of RAID 2018) is an interesting attack against bitcoin implementations. It gives a good illustration that nonce must be generated with great care in ECDSA (and other DLog-based signature schemes).

A robust and perfectly interoperable option is to deterministically use $k=\text{HMAC}(x,h)\bmod p$ where HMAC uses a hash and output size much wider than $p$ (e.g. SHA-512 and full size output for up to ≈400-bit $p$), $x$ is the private key, and $h$ is the hash of the message as used in the signature production.

If for some reason we want a randomized signature, we can first generate a tentatively true random $d$ then compute $k=\text{HMAC}(x,(h\mathbin\|d))\bmod p$ or $k=(\text{HMAC}(x,h)\oplus d)\bmod p$. This insure that a failure of the true RNG will not reveal the private key.

These three methods to generate $k$ could theoretically give $k=0$ and that should be tested against, but if we encounter this, $r=0$, or $s=0$ in ECDSA signature, the practical line of action should be to declare attack and burninate every data manipulated that won't be an unbearable loss (including the copy of the private key if there is a backup).


Cryptographic hash that supports efficient update after random-access plaintext modification Is there a cryptographic hash algorithm that, given the hash of a plaintext, supports supports efficient recomputation of the hash after modifying a single byte of the plaintext?

Specifically, is there a hash function H() such that, given plaintext P and Q of the same length that differ only in the byte at position K, there exists another function R() such that R(P, Q, K, H(P)) = H(Q) and R is O(1)? If so, what are H and R?

Such a function would be interesting because it would allow creating a filesystem that efficiently tracks a cryptographic hash for each of its files. Such a filesystem could be useful for implementing highly efficient file transfer (like rsync) or version control (like git) systems.

I don't have a proof, but I don't think an $O(1)$ R is possible. That would make it very easy to calculate the hash of a changed input, and while this wouldn't contradict any defining property of a hash, it would make the hash weak for constructs like key derivation. So it would have to be a pretty unusual hash.

The standard solution is hash trees, also known as Merkle trees. It's an old technique, older than all modern hash functions, but still very much relevant for filesystems with integrity checks. Hash trees give you an R function with $O(n)$ extra storage and $O(\log n)$ calculation time and data transfer to make an update. The idea is to divide the data into blocks and to maintain a tree whose leaves are the data blocks and whose inner nodes contain hashes of their children. Whenever a block is updated, you only need to update the path from that block to the root of the tree.


Should new applications still use RSA? Is it worth going down the ECDH route for protocols? I am currently designing an application for communication between two and more users. At the moment I am trying to figure out what methods to use for the asymmetric cryptology.

With the recent "breakthroughs" that everybody has been talking about concerning RSA I am a bit unsure whether to use it or not for future projects.

I looked at ECC and RSA alternatives such as ElGamal, but it seems like one could study that subject for the next 35 years and would still not come up with a decision.

In particular I looked at key exchange between two or more users via a server. After reading for a day or two and striking out OTR for a protocol, I got interested in Elliptic Curve Diffie–Hellman — and as it says on the Wikipedia article: "to derive another key which can then be used to encrypt subsequent communications using a symmetric key cipher."

However, it seems that ECDH is not advanced enough to satisfy my requirements of CIA & deniable encryption with regards towards MITM attacks.

Its suggested to use FHMQV for more advanced security. Sadly, as soon as I read the introduction I blacked out because I didn't understand anything.

I have about 1 year of deeper experience and understanding of cryptology, but I am by far no expert on this subject.
Still, I need to make a decision and would like to know from you whether to be concerned about RSA or not and if I should go down the DH route.

Accordingly to a previous thread Why is elliptic curve cryptography not widely used, compared to RSA?, RSA is still widely used compared to ECC because:

RSA is well established
Its public key operations (e.g. signature verification, as opposed to signature generation) are faster than ECC
(most importantly) The RSA patents have expired, while a small company called Certicom holds a number of EC-related patents.

However, according to the NSA website, Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques (RSA and Diffie-Hellman) now in use. Thus, they decided to move to elliptic curve based public key cryptography for protecting both classified and unclassified National Security information.


Authentication using AES I need to implement an authentication mechanism in an embedded environment which does not support floating point operations but has an AES accelerator module which allows for encyption/decryption operations.

Currently, I'm thinking of using the following approach:

Compute the ciphertext of the message using a secret key k1.
In parallel compute the ciphertext of the same message using secret key k2(k1 $\neq$ k2). Upon the encryption of each block the current block is XOR-ed with the previous so that the length of the authentication code is always equal to the size of a block (i.e. 128 bits).
The message to be sent is obtained by concatenating the ciphertext with the authentication code.

Is this approach secure?

TL;DR
No, the approach is not secure. Use a standard like CMAC instead. Or even better, check your AES accelerator module to see if it supports any AEAD modes of encryption like GCM, CCM, EAX.

Long Version

In order for a message authentication code (MAC) to be secure, an adversary with oracle access to the MAC (basically this means the adversary can send arbitrary messages to a black-box that will compute the MAC tag), should not be able to forge a MAC (i.e., construct a valid MAC for something that the black box never computed a MAC for).

I am going to ignore step 1 for now since that is the confidentiality part and has no impact on the authentication part. Also, I'm assuming you are using AES-CBC with a 128-bit key based on your comment.

So the proposal is to encrypt the plaintext with a key $k_2$, then XOR all the blocks together to get a MAC tag. Let's assume that a static IV of all 0's is used for the MAC.

For a two block message, say $m_1,m_2$, the MAC would be $MAC_1 = E_{k_2}(m_1)\oplus E_{k_2}(E_{k_2}(m_1)\oplus m_2)$. I could also ask the oracle for the MAC of $m_1$ by itself, which would be $MAC_2 = E_{k_2}(m_1)$.

Notice now that $MAC_1\oplus MAC_2$ is a valid MAC for the message $E_{k_2}(m_1)\oplus m_2$, but I never asked the black box for that MAC. So that would be a break.

How useful is this? Well, since the attacker controls $m_1$ and $m_2$, and can get $E_{k_2}(m_1)$ before choosing $m_2$, the attacker can make $E_{k_2}(m_1)\oplus m_2$ anything she wants by setting $m_2$ appropriately. Therefore, the attacker can ask for two MACs on non-malicious looking messages (likely they will look random), but get a MAC on a chosen message.

So, no, your approach is not secure.


Meet in the Middle Attack on x=2^n + x' I encountered today the following equation:

$x = 2^n + x'$, where $0 \le x' < 2^k < 2^n$, $2|k$ and $n, k$ is known.

There seems to be a meet in the middle attack for this, with runtime $O(2^{\frac{k}{2}})$ but I don't see it.

$x$ is known and we want to recover $x'$.

Could anyone give me a hint?

Thanks.

Well, if you absolutely had to do a MITM attack, I suppose one could look like:

Rewrite the equation as:

$$x  - x'_{low} = 2^h + 2^{k/2}x'_{high}$$

where $x' = 2^{k/2}x'_{high} + x'_{low}$ and $0 \le x'_{low}, x'_{high} < 2^{k/2}$

For each $x'_{low}$ value in the range, compute $x - x'_{low}$ and place it in a list.
For each $x'_{high}$ value in the range, compute $2^h + 2^{k/2}x'_{high}$ and place it in a list.
Flip the order of the first list (normally, you're supposed to sort them; these are already in sorted order), and then scan through the two lists, and look for a value in common.

Yes, this is a silly way to do it; however it is a Man-in-the-Middle attack of the specified complexity; this might be the answer they're looking for...


PKCS11: CKA_VALUE_LEN attribute and Unwrap key In PKCS11 specification v2.40, we see some confusion with CKA_VALUE_LEN attribute and UnwrapKey behavior.
From PKCS11 spec 2.40 section 2.8.2,

2 -> MUST not be specified when object is created with C_CreateObject.
3 -> MUST be specified when object is generated with C_GenerateKey or C_GenerateKeyPair.
6 -> MUST not be specified when object is unwrapped with C_UnwrapKey.
In the AES-ECB and AES-CBC, spec tells to pass CKA_VALUE_LEN (section 2.8.4),

So what is expected from application? Do the applications need to pass CKA_VALUE_LEN during unwrap?
NOTE: Even PKCS11 spec 3.0 is also saying the same thing.

Yes, I think that's sufficiently unclear to ask for clarification of the authors of the document, and it probably needs fixing.
However, what I do know is that the key size is definitely clear from the wrapped key itself. So there is definitely no need to specify CKA_VALUE_LEN during the call to C_UnwrapKey. There is no need to check it either; I'd be more worried about the value of the key then the size of the key if the key can be altered somehow.
What is possibly meant is that the key size of the wrapped key is determined using CKA_VALUE_LEN during key generation. Because in that case the type by itself doesn't specify the output length, i.e. the size of the key being unwrapped.


Using different hashing function with ECDSA I came across an IC device configuration & security flow and the details are illustrated in image below.
I'm wondering must the ECDSA pair with the SHA Hashing function?
Alternatively, what if using the AES-GCM to generate both CIPHER & TAG? The GF generated TAG later go through the ECDSA to be encrypted with the private key.
So from the decryption side, it exactly work the same like the image except replacing the SHA engines with the AES-GCM engine. I'm wondering why this is uncommon in all the industry practice?
Or will anything go wrong with the scheme I describe above?

I will first address the issues of the diagram;
Encryption part
Although the encryption is mentioned as optional

there is no mention of how the AES key is generated. The common method is the Diffie-Hellman Key Exchange and the Elliptic Curve version of it is preferred ECDH.

there is no mention of the mode of operation. CBC, CTR, GCM,... etc.

There is no mention of the nonce/IV generation. The nonce generation is crucial;

In the CBC it must be unpredictable
In the CTR and GCM the (IV,key) pair should be never use more than once.

ECDSA part;

The naming is completely wrong. We use signature and verification and those processes are completely different than encryption and decryption, even in the RSA. In short RSA decryption is not signature.

The verification part is wrong. Only the signature part is sent, the signature and message must both exist during the ECDSA verification.  They tend to make it symmetric but it is wrong.

Questions

I'm wondering must the ECDSA pair with the SHA Hashing function?

They didn't show which curve is used there. If a curve like P521 or Goldilocks is used the one may need XOFs like SHAKE128-512 series, or use SHA256 as CTR mode to generate more than one block to support all of the curve needs.

Alternatively, what if using the AES-GCM to generate both CIPHER & TAG? The GF generated TAG later go through the ECDSA to be encrypted with the private key.

The AES-GCM doesn't produce a digital signature, they can provide confidentiality, integrity, and authentication only if correctly used. AES-GCM can not provide non-repudiation. For digital signatures, you need a digital signature algorithm.

Or will anything go wrong with the scheme I describe above?

If there is no need for a digital signature, then it can be fine. The AES-GCM has a better alternative; AES-GCM-SIV is a nonce misuse resistant scheme. This can only leak the same message is sent again if the same message is sent again with the same (key,IV) pair is.


Secure use-cases of block cipher with 64-bit block size In what cases can we use a weak block cipher like DES ?

More precisely, Are there specific situation in which a weaken block cipher can still be used, for instance for certain types of plaintext ?

We can still safely use 64-bit-block ciphers when used in an otherwise sound protocol, and all of the following three conditions are met:

The effective key size is made big enough; that disqualifies DES (55-bit), but not Blowfish (up to 448 bits), TEA (128 bits), 3DES (167 bits), and to some degree 2-keys-3DES (111 bits). Note: I computed the effective key size of DES and variants accounting for unused low-order bits of keys, and the complementation property. Theoretical attacks allowing better-than-brute-force key search for 2-key-3DES are not a practical concern for the time being (except from demonstration of security and certification standpoints).
The number $n$ of blocks that could be used with the same key (legitimately or by an attacker abusing a legitimate device) is low enough to guard against a birthday attack. If we want the maximum odds of the adversary to succeed in this way to be bounded by $2^{-k}$ for some $k>0$, we are safe if we limit $n$ to about $2^{(65-k)/2}$. E.g. if we accept only a one in a million chance than an adversary succeeds by birthday attack, $k\approx 20$, thus we should limit to $2^{22.5}$ blocks; that's only about 45MiB in an encryption application.
The implementations are suitably protected from various side-channel attacks. When the adversary has physical access to the device implementing the block cipher, this often requires further lowering the number of uses of a given key. 3DES is well analyzed in this regard, Blowfish much less so.

A common example of safe use of 3DES is as session keys (for integrity or confidentiality protection) in Smart Card applications, with the amount of data in the session limited, as in this European Regulation (search CSM_021 thru CSM_031 for a description, CSP_301 and CSM_013 for the limitation of the number of blocks).

Update: A small block size worsen some insecure encryption protocols/modes, such as ECB, especially when used with low entropy in the plaintext. Solution is: use secure encryption protocols/modes; there's then no worry about entropy in the plaintext.


Do garbled circuits run in constant time? It seems like garbled circuits should not be input dependent, and hence should always run in constant time. Just wanted to clarify if this is true.

No, this is not needed in general, for Garbled circuits are not meant to be reused (notice that while most are not, there is some research looking into reusable GC, but not much).

Furthermore, if you are using shuffled garbled truth tables, as you should, then timing discrepancies do not leak any useful information, as long as you do not reuse the circuit.


How long will my encryption remain private? This is a basic question in cryptography but I have not found a good, comprehensive answer.

It is explained that our keys should expire and we should get new, stronger ones with time, reflecting more powerful decryption computing. Does that mean that emails encrypted today will become easier (even trivial) to decrypt in future, so emails encrypted today will eventually lose today's privacy?

If so, what is the general opinion on how this affects notions of privacy by encryption?

The main good reasons to change keys periodically are:

to mitigate the risk of a key compromise; at least some ways keys get compromised are a one-time event, e.g. eavesdropping of the keyboard protecting the passphrase; changing the key thus restores security until the next leak, and only messages enciphered with the leaked key are compromised (and only those actively intercepted after the leak if the scheme provides forward secrecy)
so that humans remember the procedure;
addition per comment: in order to reduce the risk coming from using the same key of a block cipher for too many blocks; e.g. for 3DES in CBC mode: if the adversary has 32 GiB of known plaintext (e.g. all-zeroes of an idle link), chances that she can decipher 8 meaningful bytes from another 32 GiB worth of data are >63%.

The main reason to increase key size (which is, or at least should be exceptional compared to key change) is to induce retirement of the obsolete tools used to process the keys; not only is it business to security vendors, it often is the best way to increase security; for examples, if 1024-bit keys are deemed no longer usable, chances are that the Smart Card holding them will be replaced by newer ones, designed with better side-channel leakage protection. In my experience, resistance against brute force is rarely the real weak point in a commercial application (except if that was engineered-in, e.g. to meet some legal requirement).


How does gpg know what cipher algorithm is needed for decryption? I am using gpg to make encrypt a tar.gz.

My first try uses --verbose --symmetric and then the decryption is done with --verbose --decrypt. The --verbose shows that encryption was done with CAST5 and then the decryption uses CAST5.

I check all the file contents as a sanity check

My second try uses --verbose --cipher-algo AES256 --symmetric. But I don't change the decrypt command... but somehow it knows to use AES256.

I check all the file contents as a sanity check

how does gpg know which cipher is needed (in this case AES256 instead of the default CAST5?

p.s. Does gpg embed what cipher algorithm was used, yes/no? wouldn't it be "better" to not tell anyone what encryption type was used?

how does gpg know which cipher is needed (in this case AES256 instead of the default CAST5?

The OpenPGP Symmetric-Key Encrypted Session Key Packet (RFC 4880, §5.3) says which algorithm.

  wouldn't it be "better" to not tell anyone what encryption type was used?

Not really.  This is a basic premise of essentially all serious cryptography for more than a century starting with Auguste Kerckhoffs in the 1880s: a cryptosystem should remain secure as long as the key is secret, even if everything about the method is known to the adversary.

The standard security goal for an unauthenticated cipher is IND-CPA, short for ciphertext indistinguishability under chosen-plaintext attack, meaning essentially that an adversary can't tell the ciphertexts of two distinct messages apart—even if they can choose the two messages, and even after studying the ciphertexts of any other messages of their choice.

Consequently, e.g., an adversary can't learn anything about the content of an email you've exchanged.  But they can still look at the email header, which tends to have a lot more information about your conversation (including who you were corresponding with, which can be extremely juicy information!) anyway than which algorithm GnuPG chose to encrypt it with.

If you wanted to conceal whether there is a message at all in some other stream, as in steganography, then you might want to avoid identifying information like this.  But that's not the setting that OpenPGP was designed for, and that's much costlier to implement.


Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit? In reading through the original GCM specification (McGrew & Viega '05), the composition of the 128 bit Initialization Vector as a concatenation of a 96b nonce and a 32b unsigned wrapping counter seems arbitrary and forces the scrambling pattern to repeat every 232 16-byte block.

Is the algorithm expected to be secure for significantly longer stream lengths if for example the IV were a 128b nonce XORed with a 64b or 128b counter, or are there known cryptanalysis issues that begin to arise?

In the same document the authors in section 2.1 specifies the plaintext size to be between $0$ and $2^{39}-256$ bits = $2^{36}-32$ bytes = $2^{32}-2$ blocks of 16 bytes.

That's the rationale behind the choice of the counter size. Given that requirement it will never overlap/wrap, which means you will never end up having repeating the "scrambling pattern" for the same message.

This constrains the maximum message size to $2^{36}-32 = 68.719.476.704 B$ approximately 64GB which didn't seem a problem to the authors.

Now, this choice of the counter constrains also the number of messages that can be protected under the same key at $2^{(128-32)=96}$ since the nonce is made by 96 bits.

If you look at section 3.1 of this paper by the GCM's original authors they gave the rationale above for their choices commenting that "any mode built upon a counter mode will have a similar tradeoff" {between maximum message size and number of messages under the same key}.

Now, you can easily modify GCM, by increasing the counter to 64 bits and decreasing the nonce to 64 bits and still have a secure authenticated encryption mode.
AES-CCM, for example, by specification support messages up to $2^{64}-1$ bytes.


Block Cipher vs Stream Cipher in Web Application I'm doing research about "Cryptographic attack methods in Web Application" so I have some questions to ask you guys:

Block Cipher vs Stream Cipher, which is more common used in Web Application?
How and Where is Stream Cipher implemented in Web Application?

Hope to get your response soon :)

Very few cryptosystems actually use a block cipher directly (i.e. in "ECB mode") to encrypt data — and those that do usually only do so because whoever designed them didn't really understand how a block cipher should be used.

Rather, the main use of block ciphers in cryptography is as versatile building blocks for other cryptographic components, such as stream ciphers, message authentication codes, hash functions, KDFs etc.  In particular, the usual way to use a block cipher to encrypt free-form data is by using a mode of operation such as CBC, CFB, OFB or CTR (or an authenticated mode like EAX, GCM, OCB or SIV) which actually uses the block cipher to construct a kind of stream cipher.

Thus, the actual distinction, insofar as there is one, is not between block ciphers and stream ciphers as such, but between stream ciphers based on block ciphers (like AES-CTR or AES-CBC) and "primitive" stream ciphers not based on block ciphers (of which the most common is probably RC4).

I don't really have any reliable statistics on how much those are respectively used in web applications, but my gut feeling would be that the majority (say, 95%) of (symmetric) encryption schemes used in such systems are probably based on block ciphers (mostly AES, some 3DES, occasionally rarer types like Serpent, Blowfish or old single DES).  Their main competitor is RC4, with a small but non-negligible share (say, 5%), while all other "primitive" stream ciphers (like the eSTREAM ciphers) are probably marginal (< 1%), mostly because few crypto libraries support them.

(The share of RC4 probably goes up a bit if its use in SSL / TLS is included in the total, particularly since many websites switched to it after the BEAST attack exposed weaknesses in the TLS 1.0 implementation of AES-CBC.)


Is Indistinguishability Obfuscation Real? I've recently stumbled upon an interesting Quanta Magazine article. It states that indistinguishability obfuscation (iO) 's theoretical feasibility has been proven, referencing a relatively recent paper by Jain, Lin, and Sahai. However, the Wikipedia article for iO states that the work presented in this article relies on the "dubious" assumption that there exists a PRNG in $NC^0$. The authors of the paper explicitly list this assumption, but what makes me stumble here is the Wikipedia article's wording. I've taken a look at the paper referenced in the Wikipedia article. I've got some base knowledge in cryptography and some more refined knowledge in complexity theory, but not enough to fully understand any of both publications. However, I've taken from glimpsing at the Applebaum paper that the question about the existence of said PRNG indirectly touches on the $P−NP$
question, making it seem to me like an unlikely-to-be-soon-settled question.
So I'm now very confused about the reliability of that Quanta Magazine article. As you've probably gathered by now, I'm not from the field of cryptography. But I took from the article that this technology (if truly feasible) could potentially revolutionize the way we think about cryptographic protocols, which makes me wonder why it didn't make bigger waves.
My question is this: Is that proof of IO reliable (i.e., can one by now safely say that IO is theoretically possible, ignoring all of the troubles of practical implementation and application), or does it stand on some for-now-unverifiable assumption?

First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ with super-linear stretch (i.e., stretching from $n$ to $n^{1+\tau}$ for any $\tau>0$). This is indeed not known, as far as I could ascertain from a brief search, but if you are really interested I suggest that you contact Benny Applebaum and ask him what the current status is on this question. Note that the other assumptions in the paper are also pretty strong but are just much more reasonable than everything we had until now. So, can we say that we have iO unless a lot of what we believe in crypto breaks? Probably not yet. But we are much closer to that now.
Note that the fact that the existence of something relates to P/NP and other questions does not mean anything. Almost all of crypto relies on assumptions (e.g., there is no public-key cryptography if $P=NP$). The question is only whether or not these assumptions are what we call "standard" or not.


Hash functions in XEdDSA and VXEdDSA Signature Schemes Can someone please explain the below paragraph from section 2.5 in The XEdDSA and VXEdDSA Signature Schemes? Specifically I want to understand how we are defining the family of hash functions and how is it used further?

  XEdDSA and VXEdDSA require a cryptographic hash function. The default hash function is SHA-512.

  We define $hash$ as a function that applies the cryptographic hash to an input byte sequence, and returns an integer which is the output from the cryptographic hash parsed in little-endian form. Given $hash$ and the curve constants $p$ and $b$, we define a family of hash functions indexed by nonnegative integers $i$ such that $2^{|p|} - 1 - i > p$.

  ${hash}_i(X):\\
\;\;\text{ return }{hash}(2^b - 1 - i \;||\; X)$

  So $hash_0$ hashes $b/8$ bytes of $0xFF$ prior to the input byte sequence $X$, $hash_1$ changes the first byte to $0xFE$, $hash_2$ changes the first byte to $0xFD$, and so on.

  Different $hash_i$ will be used for different purposes, to provide cryptographic domain separation. Note that $hash_i$ will never call $hash$ with the first $b$ bits encoding a valid scalar or elliptic curve point, since the first $|p|$ bits encode an integer greater than $p$. Note also that $hash_0$ is reserved for use by other specifications, and is not used in this document.

The hash functions are indexed to achieve domain separation. See, for example, Section 2.2.

The big idea is that if you have a secure underlying function (namely, the $hash$ function), for little cost, you can create a family of secure functions (the $hash_i$) with different outputs for a particular input $X$.

As an example of use of these indexed functions, if my input is DEAFBEAD,

hash_0(0xDEAFBEAD) == sha512(0xFF || 0xDEAFBEAD) == 9758ed9f853fabb2e963dc81ba617ea7dadbd802a82acdced8dc7813e908d1dfdd571b02f690487b1e1b5c7ac1938501cb0ccd00fac086a803758b5d92d811c9
hash_1(0xDEAFBEAD) == sha512(0xFE || 0xDEAFBEAD) == e8897c024462b42136308fbc975cebec5dcc83ae748047dd6cfa8d5a0806cb40fc1967932d605b6bb577cc1679e37fb94cba0af47ce32f5d6b56153e09f34a24
etc.

So throughout the document, you see $hash_1$ getting used in xeddsa_sign, $hash_2$ getting used in hash_to_point, and so on.

Each of the $hash_i$ now "does its own thing". For example, $hash_5$ may get used for signing only and $hash_6$ may get used for verification only.

The $hash_i$ are all equivalent to $hash$ in terms of security, so to my knowledge it doesn't matter which of the $hash_i$ you use for which purpose (except for $hash_0$, which is not to be used here). But this way, you get several independent secure functions derived from a single secure function.


Does the ability to influence the key of a MAC effects its security? If a PPT adversary can influence the key of a MAC function, is it still secure?

For example, if we define $f$ as follow:

$f(r,x) = HMAC_{(k\oplus r)}$(x)

If the adversary has oracle access to $f$, how likely he can predict the key $k$?

For respecting the persons who have answered the above question, I do not change it. The actual scenario is as follows:

I have a module that gets $(m,r)$ and generates $(m,x,HMAC_{k \oplus r}(m \parallel x))$ where the $k$ is the secret of the module and $x$ is the message added by the module. So:

$f(m,r)=(m,x,HMAC_{k \oplus r}(m \parallel x))$

Can I claim that every tuple $(m,x,t)$ s.t. $t=HMAC_{k \oplus r}(m \parallel x))$ is generated by the module?

P.S. I am still curious about the above claim. But, I just noticed that if I change $f$ as follows:

$f(m,r)=(m,x,HMAC_k(m \parallel x \parallel r))$

then, I can claim every tuple $(m,x,t)$ s.t. $t=HMAC_k(m \parallel x \parallel r))$ is generated by the according to the definition of MAC.

If a PPT adversary can influence the key of a MAC function, is it still secure?

In general probably no if you make no restrictions on the ways the key can be influenced. In particular the answer is "no" when you rely on your MAC actually being a PRF for your security proof (like HMAC does). This means that if your MAC relies on this then you need some additional argument for related-key security, as PRFs cannot be secure against all classes of related-keys. For a proof and more background on this see Proposition 8.4 of the original paper that introduced this (PDF).

  If the adversary has oracle access to $f$, how likely he can predict the key $k$?

Cryptography isn't about "can you predict the key" because you can usually build schemes that don't use their key-input and are thereby trivially secure if all you want is the key.

A more interesting question would be, if an attacker has access to (this concrete) $f$, how easy is it to forge tags? This has in fact been studied for HMAC and keys related by a constant leading to an attack that runs in time $2^{n/2}$ with $n$ being the HMAC's output length.


How do I decide what mode to use? I'll be using AES from OpenSSL.  I understand why I don't want to use ECB from reading pages like this Wikipedia article, which has a great example of what happens when you attempt to encrypt with electronic codebook.

But what I'm missing, is some sort of comparison table with all the other modes so I understand the positives and negatives of the various modes.  Where can I find this information so I can make an informed decision on what mode to use?

Update 1:

Looks like OpenSSL's EVP api (which I believe is the recommended API when using OpenSSL?) only supports 2 modes [OpenSSL][1] – GCM and CCM – which drastically reduces my choices.

1: https://www.openssl.org/docs/crypto/EVP_EncryptInit.html

Update 2:

Unsurprisingly, that OpenSSL page is somewhat misleading or incomplete.  Looking at /usr/include/openssl/evp.h I see there are 30+ variations on AES to choose from, including:

EVP_aes_*_ecb()
EVP_aes_*_cbc()
EVP_aes_*_cfb1()
EVP_aes_*_ofb()
EVP_aes_*_ctr()
EVP_aes_*_xts()
...and many more!

So I'm back to reading about all the different modes so I can make a semi-intelligent choice as to which I should be using.

Encryption modes have lots of differences. Putting all of them in a table would be tricky. I would recommend you to do some work and read through the NIST documentation on Block cipher modes.
If you are unsure and you don't have particular requirements, you could check if GCM mode is available. It is an authenticated mode that also provides the integrity/authenticity of the ciphertext. You can also add any other non-confidential data such as configuration data in the Additional Authenticated Data (AAD) - this is separate input to the cipher. Beware that GCM mode fails catastrophically to IV nonce / reuse (GCM-SIV mode could correct that).
In the end, all modes described by NIST - except of course ECB mode, note the NIST hint - are secure for providing confidentiality when used correctly. So in that sense there is little point in comparing them without going into the specific use case.
[EDIT] I've removed the requirement that the IV needed to be put in the AAD data. I don't know what I was thinking when I wrote that and I didn't get corrected...


Behavior of Iterated 3-DES When reading ''Algebraic Cryptanalysis'' by Gregory V. Bard, Springer Editions, I got confused by this sentence:

  Suppose there were three naïve Cryptography students, who choose to use 3-DES iterated roughly one million times, because they are told that this will slow down a brute force attacker by a factor of one million.

I just wanted to make sure I understood this sentence fully. Does this mean that, for a given message m, we just compute 3DES(3DES(...(3DES(m))...)) one million times? (Assuming we keep the same keys)

Yes, It is what you understood. You use the same key for each encryption.

If you think that they used different keys for each TDES (3DES) they need to store one million keys. This is not practical for the attacker but also for them.

It can also be written as $c = \operatorname{TDES}^{(1000000)}_k(m)$

The point in the section distinguishing these iterated from a random permutation and possible attacks that can be faster than brute-force.


Requirements for RSA key parameters Recently I'm working with a chinese vendor for POS devices and their devices use 2048bit RSA keys for signing binaries. I had to generate a public/private pair (so I can sign my own binaries) and I did some research about this.

During the research I came across a recomendation from vendor's documentation: please, check if the very first byte of the Modulus (N) of the private key is greater than 0x80. If not, please, generate another key and do the same check.

Well, if you think about it, if it is less than 0x80 the key won't actually have 2048 bits but less than that. After all, RSA keys parameters are essentially big integers and zeros to the left in integers doesn't play any role into calculations. I even found that OpenSSL has code to test this condition (I guess at least).

Now, question: shouldn't the other parameters have exactly the same requirements? I mean, they are all integers and will be used in calculations like so. Why doesn't e.g. the private exponent is subject to the same checking?

Shouldn't the other parameters have exactly the same requirements?

Certainly not all other parameters. The vendor could set requirements for $e$, but they would be different. For the other key parameters, extra requirements would be unusual, and there could be a valid technical reason for them only if you are using gear (software or hardware) that the vendor supplied or prescribed for use when signing binaries or preparing a Certificate Signing Request.

The key parameters given to the vendor or which will get into the POS are those in the public part of the RSA key: $(N,e)$. There are legitimate interoperability requirements for these. However, the requirement "very first byte of the Modulus ($N$) of the private key is greater than 0x80" is not standard: it should be "..is not lower than 0x80", or it is there to work around some nasty bug, or it is a non-standard flag for something (e.g. allowing loading unsigned code when the first byte of $N$ is 0x80). The standard (FIPS 186-4 appendix B.3) requirement on $N$ for 2048-bit RSA key is $2^{2047}\le N<2^{2048}$ (and $N$ odd), not $2^{2047}+2^{2040}\le N<2^{2048}$, and I would not let that deviation unexplained.

The standard for $e$ is $2^{16}<e<2^{256}$ (and $e$ odd), with the upper limit often lower, but there's nothing common or reasonable that would require the first byte to be over a limit close to 0x80. $e=2^{16}+1$ is sometime required. $e=3$ was formerly popular in POS applications, for it speeds up card authentication and is perfectly fine when used with proper signature padding.

A private key should remain known by its legitimate holder only, and (for RSA and secure keys) there is no way to assess the value of its parameters from what should get known to the vendor or manipulated by the POS devices. Even the fact that $N$ has two rather than three prime factors is not testable by the vendor or POS. Thus a requirement on the private key is technically justifiable only for gear that uses the private key (in the application: to sign software or CSR). Starting with the more commonly enforced (list not limitative):

The private key is expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ per RSAPrivateKey in PKCS#1 v2.2 without the optional otherPrimeInfos, and thus $N$ has exactly two prime factors, rather than more.
$N$ has exactly $k$ bits with $k$ in a discrete set (typically: multiples of some power of two in some range).
$d<(p-1)(q-1)/\gcd(p-1,q-1)$ (limit in FIPS 186-4). That's often relaxed to $d<N$ (limit in PKCS#1v2.2), $d<2^k$, or other.
$p$ and $q$ are odd and in range $(2^\frac{k-1}2,2^\frac k2)$. When enforced, the lower limit may vary, e.g. be relaxed to $\mathtt{B5_h}\,2^{\frac k2-8}$ or $2^{\frac k2-1}$. But even if such limits are standard, many hardware devices and most software are perfectly happy with $p$ and $q$ not of the same bit size.
$q<p$ or vice versa (a requirement indicative of lousy practice).


Small Encryption Exponent I am trying to crack an unpadded RSA set up for a homework.

I have public key (R,e) and encrypted message E.

R:=1189873858375600120035497781492406260116261348762168101523668479976252918878873543993974091515716923413521166189;
e:=7;
E:=935688997292570230577548538417371291686892187342525833188430568797480485753147343888751799688783739259397891334;

Obviously, the attack that I'm supposed to use has something to do with the size of the public encryption exponent but I'm struggling to see exactly how to use it.

I understand the relationship between e, d and φ(n) and understand that there is an integer k < min{e, d} such that φ(n) = (e ∗ d − 1)/k but I don't understand how I can use that fact to brute force discover φ(n).

It appears that the solution comes from doing some kind of search from 1..k but since d is still unknown, I don't really see how to take advantage of that.

Can someone enlighten me, please?

The question is from Problem 2 in Assignment 6 given here. It looks much like a straight instance of the RSA problem: we want to find $x\in\mathbb N$ such that $x^e=E\bmod R$ and $x<R$, given $R$, $E$, $e=7$, with $E$ expected to be the product of two unknown primes $p,q$ such that $e$ is coprime with $(p-1)\cdot(q-1)$.

It is correct that knowing none of $d$, $\varphi(R)$ or $\lambda(R)$, nor the factorization of $R$, we can't solve the problem by massaging $e\cdot d\equiv1\pmod{\varphi(R)}$ or $e\cdot d\equiv1\pmod{\lambda(R)}$ with $e$ small.

The fact that $e$ is small would help if it turned out that $E$ (or $i\cdot R+E$ for some small $i$) was an exact power of $e$; for this would allow to find $x$ by extracting an $e$-th root. For random parameters, this happens with odds about ${R^{1/e-1}}$, thus decreasing with $e$. But $R$ is so big that theses odds are vanishingly low for $e\ge2$. In fact, any small odd $e>2$ is believed a safe choice in RSA when $x$ is random or properly padded.

The most classic avenue to solve an RSA problem is to factor the public modulus $R$. This is how Part 1 of Assignment 2 was done, for $R$ of 276 bits. In the present problem, $R$ is 367-bit, therefore brute force factorization is feasible (it was feasible in 1995 by means available to academics; see this answer). However it would require a significant effort, and I do not know that Maple's built-in factorization primitive would factor a properly chosen 367-bit RSA modulus in reasonable time.

We should not rule out factorization though: in this course, Alice (which, we are told, has $R,e$ as public key) has in Assignment 4 made unconventional and rather poor choice of key; so there is a chance that $R$ was not properly chosen and can be factored with little effort, using some of the factorization methods likely alluded to in the course.

Hint 1: The problem can be solved with practically any big-number calculator offering modular exponentiation, without even writing an iterative program.

Hint 2: (Hover mouse to see it)

   Alice may have put too much emphasis on being ultra-resistant to trial division for a given magnitude of $R$.


Is multi-byte mapping to one byte a viable encryption technique? The idea is to randomly map byte values eg

\begin{equation}
  Sub(x)=\left\{
  \begin{array}{@{}ll@{}}
    (a, b), & \text{if}\ r=1 \\
    (c, d), & \text{r=0}
  \end{array}\right.
\end{equation}

Where $r$ is the random value that determines the output, $x$ is the input byte, and $a, b$ or $c, d$ is the output bytes.

A concrete example might be:

\begin{equation}
  Sub(97)=\left\{
  \begin{array}{@{}ll@{}}
    (12, 57), & \text{if}\ r=1 \\
    (34, 54), & \text{r=0}
  \end{array}\right.
\end{equation}

Each byte has a unique byte reference.

To encrypt choose random map and set

encrypt[97] = 12,57
encrypt[97] = 34,54

To decrypt find matching values

decrypt[12,57] = 97
decrypt[34,54] = 97

Is this kind of multi-byte mapping to one byte a viable encryption technique?

You seem to be describing a homophonic substitution cipher, except on bytes instead of letters.  Such a cipher is slightly better (i.e. harder to break) than a simple substitution cipher, but not by much.

To analyze the security of your cipher in more detail, one would need to know how the encryption map is chosen (e.g. is it derived from a key somehow), how many possible encryptions each plaintext byte has and how the encryption of each plaintext byte is chosen.  Still, even without knowing the details, most ciphers of this type tend to be vulnerable to some pretty simple attacks if the attacker can collect enough ciphertext (and possibly corresponding plaintext) to analyze.

For example, if the encryption of each plaintext byte is chosen randomly from among the possible alternatives, this implies that each of the encryptions of a given plaintext byte occurs with the same average frequency.  If the attacker can collect enough ciphertext, they can determine which pairs of bytes occur with approximately the same frequency in the ciphertext, and guess that those are probably alternative encryptions of the same plaintext byte.  (How much is enough depends strongly on what the plaintext is, but a megabyte or two should be plenty for most kinds of data.)  Having done that, they can then attack the cipher using basic frequency analysis, just like one would attack a simple non-homophonic substitution cipher.

Also, if the attacker has access to some ciphertext and to the corresponding plaintext, they can simply compile a partial decryption table by comparing them.  With this method, even a few dozen kilobytes or less may be enough to get a reasonably good coverage of the possible encryptions of most common plaintext bytes.  Armed with such a partial encryption table, the attacker may then be able to partially decrypt other ciphertexts and to use those partial decryptions to guess the plaintext bytes corresponding to other ciphertext byte pairs and thereby extend their table further.

Basically, a cipher like this could be quite a challenging puzzle for an amateur cryptanalyst to break.  You shouldn't rely on it for any real security, though, especially not if you want to encrypt more than very small amounts of data.


Can I compute “SHA256(secret||data)” when having “SHA256(secret)” and “data”? I need to find the SHA256 hash of s string like this: part1-part2. I know the SHA256(part1), length of part1 and I know part2, but I don't know what is the contents of part1.

Is there any chance I can compute the hash of the whole string using only these three parts of information?

As @yyyyyy already commented: if you are able to successfully apply a length extension attack, you would be able to compute

$$\operatorname{SHA256}(\mathit{secret}\Vert\mathit{padding}\Vert\mathit{data})$$

But computing $\operatorname{SHA256}(\mathit{secret}\Vert\mathit{data})$ for freely chosen $\mathit{data}$ without the $\mathit{padding}$ in between is assumed to be “hard”; meaning that you’ll end up having to brute-force your way towards a result.

Also see “understanding a length extension attack” for a more indeep understanding of things.


How hard to solve the given mod problem Let c = a.b mod p

where p is n bit prime number (e.g. 128 or 160 bit prime number);
a - random number between 1 and (p-1);
b - random number between 1 and (p-1);

Given c, a and p, how hard to compute b?

Very easy, you just use the Extended Euclidean Algorithm to compute $a^{-1} \pmod p$. Then you have $b \equiv ca^{-1} \pmod p$.

Note that, because the EEA has polynomial complexity, this remains easy even if $p$ is very large (e.g., tens of thousands of bits).


Using KDF output for password validation I am currently revising an AES data format. I would like to determine whether a provided password/key is incorrect. Previously this was done by validating the HMAC, but this makes it impossible to distinguish between data corruption and a bad password. It also requires reading the entire stream before validating the password, which is problematic.

My new design is as follows (the HMAC step is HKDF):

prk = PBKDF2(SHA512, password, salt, rounds, 512 bits)
(validator[16], iv[16]) = HMAC(SHA512, prk, "rncryptor.validator+iv" || 0x01, 256 bits)

The validator is 16 bytes that are written to the header. During decryption, I recompute the validator to check the password before proceeding.

I believe this scheme is secure. Common best-practice for password validation is a salted and stretched hash. I believe HKDF is providing the same. My one slight concern is NIST SP 800-56a, Section 5.8:

  An Approved key derivation function (KDF) shall be used to derive secret keying material from a shared secret. The output from a KDF shall only be used for secret keying material, such as a symmetric key used for data encryption or message integrity, a secret initialization vector, or a master key that will be used to generate other keys (possibly using a different process). Non- secret keying material (such as a non-secret initialization vector) shall not be generated using the shared secret.

The validator is not "keying material" at all, so I don't believe this is relevant, but I don't understand the restriction even for "a non-secret initialization vector." Why would it be dangerous to use a proper, salted KDF to generate a non-secret IV? Does this impact my use as a key/password validator?

It's best practice to use the KBKDF to generate separate key material for validation as well as for generating the key used for encryption using a different input or counter of each key.

If you do apply a KBKDF for each key / IV (using different ID's/counters for each) then you should not have any concern leaking any information. These KBKDF's are plenty fast (especially in comparison with PBKDF2 of course) so speed should not be a concern.

I would suggest to use a counter mode KDF in NIST SP800-108 if you want to stay within NIST boundaries. You can still use your favourite HMAC as PRF.

Note that there is some discussions regarding the security of KDF's. NIST approved KDF's may not always be the most safe. For instance, consider scrypt over PBKDF2 and HKDF-Expand (your currently selected KBKDF) over NIST SP800-108 if you don't require NIST approved algorithms.

Note that all the KBKDF's of NIST as well as HKDF have been added to Bouncy Castle 1.50 lightweight API for Java (I did the implementation / testing against NIST CAVP vectors), in case you require an implementation.


Prevent communication with a node assuming full transparency I have an IoT device that I have set up to communicate with AES-256-GCM encryption. The working version has the encryption key stored in plaintext in a file on the device (this is going to be improved). Every time it is communicated with, a new key is included inside the encrypted message and the device updates its key to match it ready for the next message.
I would like to prevent someone from being able to communicate with a device, even if they have accessed everything on it.
Plan
I am thinking of setting up a (what, salt? hash?) which is sent to the device with each encrypted communication, which it adds/multiplies/hashes with something it has stored to create the password it can use to decrypt the communication. What should I look into to do this properly?
Good or bad idea?
I know it's highly discouraged to 'roll your own' when it comes to crypto, so I want to know whether taking this step would be considered well- or ill-advised.
Thank you.

This sounds like a job for…public-key signature!

Store a public key on the node, and reject any incoming message if it does not have a valid signature under that public key.

If you're concerned about performance, verification under RSA with $e = 3$, or Rabin–Williams, is very fast.


Secret sharing - Size of the share I'm having some hard time understanding why the size of the share must be at least as large as the secret itself, why is this restriction imposed? What would happen if the share is smaller?

In Shamir's secret-sharing scheme, the secret and the shares of the secret all are elements of a finite field, and so necessarily have the same size. In the Reed-Solomon code based variant of Shamir's secret-sharing scheme proposed by the late Bob McEliece and myself (R.J. McEliece and D.V. Sarwate, "On sharing secrets and Reed-Solomon codes", Communications of the ACM, v. 24, Issue 9, Sep 1981), the $n$ shares are $\frac 1k$-th the size of the secret, but these schemes don't have the perfect information-theoretic security of Shamir's scheme. See this answer.


Understand LWE(Learning With Error) negligible error probability According to Regev's paper, p15

  Correctness. Note that if not for the error in the LWE samples, $b-⟨a, s⟩$ would be either 0 or ⌊ q ⌋ depending on the encrypted bit, and decryption would always be correct. Hence we see that a decryption error occurs only if the sum of the error terms over all S is greater than q/4. Since
  we are summing at most m normal error terms, each with standard deviation αq, the standard deviation of the sum is at most $\sqrt{m}\alpha q < q \log{n}$; a standard calculation shows that the probability that such a normal variable is greater than q/4 is negligible.

I did a little experiment with mathematica and the resulting probability of decryption error is around 0.28. Can you point out where I was wrong?

Firstly I build the the following variables as in the paper:

In[1]:= n=10
        q=RandomPrime[{n^2,2n^2}]
        m=1.1*n*Log[q]
        α=1/(Sqrt[n]*Log[n]^2)
        σ=α * q
        Floor[q/2]
        q/4
Out[1]= 10
Out[2]= 131
Out[3]= 53.6272
Out[4]= 1/(Sqrt[10]*Log[10]^2)
Out[5]= 131/(Sqrt[10]*Log[10]^2)
Out[6]= 65
Out[7]= 131/4

Then I calculate the maximum probability that the error terms sum is greater than q/4 by calculating the value of the Cumulative Probability function when x is -q/4:

In[323]:= (*Probability that sum is greater than q/4*)
          CDF[NormalDistribution[0,Sqrt[m]*α*q],-q/4]
Out[323]= 0.279785

As you can see, it's too large for "negligible" so I think there's something wrong with my calculation.

Here are the PDF for a single error $e$ and the sum of errors:

Single error

Sum of errors

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.


Impact of a non-uniform distribution in a secret sharing scheme When it comes to the secret sharing schemes, it seems that the random numbers need to be drawn uniformly. Is there any difference between the random numbers from uniform distribution and the non-uniform distribution? Do different distributions affect the security of the scheme?

Just to add to the other answers, you may also want to take a look at leakage resistance secret sharing, for example this work.
The idea is to study the following question:

  What is leaked about the underlying secret when the adversary gets some leakage from the shares?

This turns out to be a very interesting question, and in some sense, changing the distribution can be seen as "leaking" information since some shares may become more likely than others.

Interestingly, in some cases, even a 1-bit leakage can completely break security.
For example, if you use Shamir's secret sharing over $GF(2^n)$, then leaking the first bit of a large enough amount of shares will leak the first bit of the secret! So if you have a distribution that generates shares for which it is more likely that the first bit is, say, $1$, then you will know something about the secret.


modfied man in the middle attack diffie hellman I have been given a problem in preparation for my cryptography final that I'm not sure how to solve. It asks me to suppose a scenario where instead of where an attacker would intercept some message from Alice ($g^a$) mod p and ($g^b$) mod p from bob, and then replacing each of these with $g^e$, the attacker would replace it with $g^q$ where $p=mq+1$, $p$ is the large prime upon which Alice and bob have agreed, $m$ is a small even number, and $q$ is another prime.

Why are there exactly $m$ values for $k$?
Why is this attack any better than the attacker simply raising $g$ to their own value ($e$)?

Why are there exactly $m$ values for $k$?

Well, assuming $k$ is the value of the shared secret that either Alice and Bob derive, well, that's not true; there are at most $m$ possible values, however it may be fewer.  There will be exactly $m$ values if $g$ is a primitive root modulo $p$; however when we use Diffie-Hellman in practice, we generally avoid using a primitive root.

To understand why there are at most $m$ possible values, we need to look at Fermat's Little Theorem; one way of expressing it is:

$g^x \equiv g^{x \ \bmod\ p-1} (\bmod\ p)$

(This isn't the standard way of writing it; this formulation works out fairly well for this purpose).

The other thing to look at the Diffie-Hellman operation with the modified messages, where Alice computes:

$k = g^{aq} (\bmod\ p)$

And we ask ourselves "how many distinct values can $aq \bmod\ p-1$ take on?"  (Hint: consider the Chinese Remainder Theorem).

You're supposed to be learning, hence I'm not giving you the full answer; I hope these hints are enough for you to fill in the missing pieces.

  Why is this attack any better than the attacker simply raising $g$ to their own value $e$?

Well, in practice, it won't be any better; any secure protocol that uses Diffie-Hellman must have a story why an attacker who modifies the messages cannot gain an advantage; such protection will foil both attacks.

However, I believe the answer they're looking for starts with "if the attacker replaces both values with his own value $g^e$, then both sides will always derive different shared secrets (and hence different session keys); to continue the attack, the attacker must decrypt each sides messages, and reencrypt them with the keys shared with the other side.  However, if the attacker replaces both values with $g^q$, then with probability $\ge 1/m$, [fill in details here]


How can I know when a file was signed? I have been thinking about digitally signed documents (Word files and PDF files) and can not get over the fact about - how can I securely know when the file was signed?

Scenario:
If the date of the signature is saved in the file that I am signing. The voucher for the date is me. However, if someone steals my private key, and I revoke my Certificate, the thief can easily create a PDF file with a false date and sign that with my revoked key. The document will appear as being signed at the time, when my Certificate hasn't been revoked yet.

The only way I can think of to implement the signature date safely is by sending my signature to a "trusted" time server, which timestamps my signature and signs it. So in fact - I need a digitally signed document which vouches about the time of my signature.

Does Adobe just take Computer time, or does it get time from the Adobe server, or does it receive an Adobe-signed vouch for time?

Is there another - simpler way?

You can prove that a document was signed after a certain date by including data that was not known to anyone before that date, such as stock market data.

You cannot prove that a document was signed before a certain date by purely cryptographic means. Information doesn't go stale, so when you show a signature, it could have been signed at any time.

You can prove that a document was signed before a certain date by non-cryptographic means. Showing the signed document to someone (a trusted third party) is an easy way to do that: if you trust that entity to vouch for having seen the signature at a certain date, then the signature has to be older. The third party doesn't need to see the document, only its signature (containing a hash of the document); if you need to prove that the document was signed, you can reveal the document later.

None of this is what you need, though. You would like to prove that a document was not signed before a certain date — the date when your private key was stolen. The thief could create a signature and pretend that the signature had been made a long time ago (but they will of course not be able to prove it: it would be your word against his).

One way to accomplish what you want is to require that any valid signature be “notarized”: the recipient must be instructed never to trust your signature alone as genuine, only your signature validated by a trusted third party (the notary), which would demonstrate the existence of the signature at the date it was seed by the notary.


Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible? In the paper Pairings for Cryptographers we read about what the authors call a type 2 pairing in which we have a "pairing friendly curve $E$ over $\mathbb{F}_q$ with embedding degree $k>1$ and define $G_1$ to be the subgroup of $E(\mathbb{F}_q)$ of order $l$". We also define $G_2=\langle Q\rangle$ where $Q\in E(\mathbb{F}_{q^k})[l]$. In this type of pairing we have a group homomorphism from $G_2$ to $G_1$.

The authors go on to say

  The advantage of the Type 2 setting is that we can use any curve and still get a homomorphism from $G_2$ to $G_1$. The disadvantage is that the group $G_2$ has no special structure. It seems to be impossible to sample randomly from $G_2$ except by computing multiples of the generator $Q$, hence we cannot securely hash to $G_2$.

Why is computing multiples of the generator $Q$ not a secure way to hash into $G_2$? For instance, say the order of $G_2$ is larger than $2^{256}$. Why couldn't I use a 256 bit hash function $h$ to help hash into $G_2$? Specifically my hash $H:M\to G_2$ where $M$ is the plaintext space would be something like $H(m)=h(m)Q$.

What the authors of the paper cited by you certainly mean by secure is "treat the hash function to $G_2$ as a random oracle". The problem is that hashing to $G_2$ can only be realized by taking some point in the group and multiplying it with a scalar (which is for instance the output of a full domain hash mapping to integers in $Z_{ord(G_2)}^*$). See for instance here for fast methods, which, however, also do not yield "secure" hashing to $G_2$.

It is best explained by an example why such simple hash functions (multiply scalar with some fixed point) can yield to insecure cryptographic protocols. In the example below, I use a type 1 setting for illustration purposes (BLS signatures in type 2 pairings are still secure under a slighly different assumption - co-CDHP instead of CDHP - since one can use a secure hash function $H$ to $G_1$).

The security of BLS essentially relies on treating the hash function $H$ as random oracle, i.e, the output of $H$ cannot be determined unless by querying $H$.

Let us take a look at the BLS setting, where we have $G, G_T$ to be prime order $p$ groups and let $P$ be a generator of $G$ and $e:G\times G\rightarrow G_T$.

Then the private key $x$ is a random element of $Z_p$ and the public key is $X=xP$.

Signing a message $m$ amounts to computing $S=H(m)$, where $H:\{0,1\}^*\rightarrow G$ is modelled as a random oracle that maps from strings to elements of $G$, and setting the signature as $\sigma=xS$.
Signature verification when given $m$ and $\sigma$ is to check if $e(H(m),X)=e(\sigma,P)$.

Note that if we would make an extremely bad choice and choose an "insecure" $H$ as $H(m):=H'(m)P$ where $H':\{0,1\}^*\rightarrow Z_p^*$ is a secure hash function, then anybody can forge signatures by computing $\sigma=H'(m)X$ for arbitrary messages (this is essentially the strategy of simulating the random oracle used in the security proof).

So, the signature scheme (and other pairing based protocols that require $H$ to be modeled as a random oracle) live from the fact that the output of $H$ is unpredictable and in particular the discrete log with respect to the generator is not known.

A type of pairings that allow to securely hash into $G_2$ and where there is also an efficiently computable homomorphism from $G_2$ to $G_1$ are so called type 4 pairings.


Can an AES-GCM be cracked if the key is known but the nonce isn't? I'm kind of new in this field and I've been trying to learn it.

I'm now facing an issue where I have a couple of packages encrypted with AES-128 GCM and I have the key that was used to encrypt these packages. However, I dont know the nonce or the H.

Is there any way for these packages to be decrypted? or is the nonce not being known keeping them safe in a case like this?

Would appreciate all help. Thanks a lot!

You'll have to guess the plaintext of at least one block (128 bits) that is on a 128 bit boundary from the start of the GCM ciphertext. Then you can XOR it to retrieve 128 bits of the key stream.

Now the key stream you can decrypt since you have the key. This will get you a counter value. The counter in GCM mode starts with a 12 byte nonce and the counter as four bytes: 00000002 in hexadecimals. Once you have that nonce you can generate all the other required nonce + counter values.

So yes, it is possible, but only if you can guess at least one block of the plaintext.


How would quantum computers affect password based encryption? At first glance: Assuming that the output of the password hashing function is large enough,
quantum computers should have no effect on password encryption as on symmetric cryptography in general.
Is that correct?

More precisely: Grover's search invokes an oracle instead of searching a dataset. Does this mean that
dictionary attacks cannot be performed efficiently with quantum computers?
Is there any other way in which quantum computers could be used for password cracking?

Currently we use slow key derivation functions. If a hypothetical quantom computer could run these as fast as a classical computer (Which is a huge If) grover's algorithm would allow searching over the equivalent of the squared root of the password space.
However even a sizeable quantom computer won't be able to do that. We will be seeing Shor's algorithm being used to attack RSA and DH before we see Grover's used to attack old 128 bit encryption. And that before it will be used against a password based key derivation function.
And I expect none of this soon.


Deciding on an AES cipher mode for chunked data I'm trying to decide on which ciphermode to use for a programming excercise. I have a file that I need to encrypt without saving unencrypted data to storage and without storing the entire file in memory.

I've opted for streaming the file, in a fixed size into a buffer, encrypting said buffer, write said buffer to storage and clear the buffer before doing it all again with the next slice of data.

Once the encrypted chunks had been written to storage, they could be consolidated into a single file, which would have to be split into chunks again for decryption.

The above seems like a standard way of doing it, from what I could gather, but I'm not entirely sure as to which ciphermode to use.

I was wondering which of AES-GCM and AES-CBC would be best to use?

Ideally I'd like to choose a solution that is "encrypt-then-mac", but I'm unsure which of those fit the bill here?

The programming language I'm doing this in is Golang, if that matters to anyone.

I was wondering which of AES-GCM and AES-CBC would be best to use?

If these two are your option, then it is essentially a no-brainer. Always use AES-GCM unless you really know what you are doing.

  Ideally I'd like to choose a solution that is "encrypt-then-mac", but
  I'm unsure which of those fit the bill here?

That's what AES-GCM does internally. It encrypts the data with AES-CTR and then uses a fast, specialized MAC to authenticate the ciphertext.

  Once the encrypted chunks had been written to storage, they could be
  consolidated into a single file, which would have to be split into
  chunks again for decryption.

One thing to look out for when doing streamed decryption is that the resulting plaintext must not be used until the decryption has finished. The reason being that until you have processed everything (including the authentication tag at the end), you can't be sure that the data hasn't been tampered with. There are workarounds to this, that allow you to chunk the data and authenticate it individually using incrementing nonces to prevent re-ordering attacks, but even then there may still be problems with substitution attacks (ie where old versions of chunks are used to substitute current chunks).


How does one construct a 27x27 tabula recta for 2-of-3 secret sharing? In the answer to this post at security.stackexchange, someone describes how, using pencil and paper, one can do 2-of-3 secret sharing with a tabula recta.  But I don't understand how he created his table, and although I can see some sort of pattern I wouldn't be able to reconstruct it in a pinch.

Another question I have is, is this sharing scheme information-theoretically secure?  Does any individual share, taken alone, provide any information about the secret?

We start by coding a secret $k\in\{0,1,2\}$ as three shares $x$, $y$, $z$ by

choosing share $x$ uniformly at random in $\in\{0,1,2\}$
choosing share $y$ as $(x-k)\bmod 3$
choosing share $z$ as $(y-k)\bmod 3$

One share gives no clue about $k$, but we can recover $k$ from any two shares:

from $x$ and $y$ as: $k=(x-y)\bmod 3$
from $y$ and $z$ as: $k=(y-z)\bmod 3$
from $z$ and $x$ as: $k=(z-x)\bmod 3$

Note: per standard notation of modular arithmetic, for $n>0$, the quantity $i\bmod n$ is defined as the $j$ with $0\le j<n$ such that $i-j$ is a multiple of $n$.

The table we need to carry this has $k=(x-y)\bmod 3$ at column $x$ and lines $y$, that is:

    |  0  1  2
----+----------
- 0 |  0  1  2
- 1 |  2  0  1
- 2 |  1  2  0

Now, if the secret consists of two digits each in $\{0,1,2\}$, we can express it as three shares of two  digits each in $\{0,1,2\}$, by using the above method for each digit of the secret, yielding the corresponding digit for each of the three shares.

We can simplify doing that by building the following table, where each digit of the result is obtained by applying the previous table to the corresponding digit of each input:

     |  00  01  02  10  11  12  20  21  22
-----+-------------------------------------
- 00 |  00  01  02  10  11  12  20  21  22
- 01 |  02  00  01  12  10  11  22  20  21
- 02 |  01  02  00  11  12  10  21  22  20
- 10 |  20  21  22  00  01  02  10  11  12
- 11 |  22  20  21  02  00  01  12  10  11
- 12 |  21  22  20  01  02  00  11  12  10
- 20 |  10  11  12  20  21  22  00  01  02
- 21 |  12  10  11  22  20  21  02  00  01
- 22 |  11  12  10  21  22  20  01  02  00

We can then replace two-digit pairs by $3^2=9$ letters A..I (in row and column indexes, and the table itself), and we get:

     |  A   B   C   D   E   F   G   H   I
-----+-------------------------------------
- A  |  A   B   C   D   E   F   G   H   I
- B  |  C   A   B   F   D   E   I   G   H
- C  |  B   C   A   E   F   D   H   I   G
- D  |  G   H   I   A   B   C   D   E   F
- E  |  I   G   H   C   A   B   F   D   E
- F  |  H   I   G   B   C   A   E   F   D
- G  |  D   E   F   G   H   I   A   B   C
- H  |  F   D   E   I   G   H   C   A   B
- I  |  E   F   D   H   I   G   B   C   A

We can do the same thing for secrets consisting of three digits, then replace three-digit triples by $3^3=27$ signs: letters A..Z and . . That's how the table in my answer was constructed.

The mapping of $3^3=27$ three-digit triples to letters is arbitrary. We would obtain a table that works just as well for any mapping. We can additionally reorder lines and columns in a convenient order, e.g. alphabetical. That allows to generate different easy-to-use tables that work just as well.

We can also extend to $3^4=81$ symbols, allowing uppercase and lowercase, digits, and 19 typographical symbols (but if the symbols are ultimately printed, the font must allow recognizing between O and 0, l and 1 ).


In which disciplinary category can cryptography be put? Is it a multi-disciplinary, inter-disciplinary, cross-disciplinary, or maybe even trans-disciplinary? What are the basis to describe each kind? I mean, how can we infer by which disciplinary field we can describe the cryptography?

I got an answer saying that it is multi-disciplinary because it contains multiple subjects like information theory, mathematics… what about the other fields?

It is multidisciplinary because it's a branch of mathematics and freely borrows from other branches such as statistics or algorithms.

I'm not so sure if it's cross-disciplinary. Although companies that make secure products (ie. products that use crypto facilities) employ cryptographers, cryptography in itself is a purely theoretical discipline that doesn't concern itself with implementation details that much (but Crypto.SE often does).

You could say it's interdisciplinary because it is a parent of quantum cryptography but I can't think of a justification for calling it cross-disciplinary.


How would an attacker perform an exhaustive key search on a block cipher using ECB mode? Do you always assume from Kerchoff's principle, that the attacker has access to everything but the decryption key?

That is, am I to assume that to perform an exhaustive key search, the attacker has a plaintext block and ciphertext block pair.

So an attacker would systematically try every possible key by decrypting the ciphertext? Then he would be able to identify when he has found the correct key if it matches the plaintext?

If he only has the ciphertext is an exhaustive key search still possible?

Should I be looking at what information a block cipher running in ECB mode provides?

Please help!

I think the attack models establish constraints on the cipher parameters that allow you to confirm guesses in a brute force or probabilistic search.

A simple way to look at it is that they let your write equations involving the cipher parameters. For example, in $c = enc(p,k)$, you can fix two of the parameters and solve for the third. Clearly $c$ (ciphertext) must be obtainable from $\lbrace p,k \rbrace$ (encryption of plaintext $p$ under key $k$), and $p$ obtainable from $\lbrace c,k \rbrace$ (decryption), but $k$ should not be obtainable from $\lbrace c,p \rbrace$ (secure against known-plaintext attacks).

If all you have is ciphertext samples, then you have no means to verify a guess for the key. From an algebraic perspective, you cannot set up an equation using $c$ alone that will allow you to derive anything about $p$ or $k$. However, if you are running in ECB mode, then solving $k$ for one block under known-plaintext gives you $k$ for every other block, including blocks where only $c$ is known.

Sure, you can set up the equations corresponding to a particular attack model, but ciphers are designed so that the equations are not solvable by any means other than exaustive brute force search.


Should Diffie-Hellman on Curve25519 be validated? I have some issues understanding the original protocol proposed by Daniel J. Bernstein for Diffie-Hellman on Curve25519. On his web page he states to not validate remote public key, but at the same time enumerates a list of bad points for "some protocols". It does not state anything about zero check after scalar multiplication.

In another question I got linked to this article about validation, but I can not see a definitive conclusion explicitly telling to not validate inputs nor outputs.

Should Diffie-Hellman on Curve25519 be validated? By validation I mean to check that input public key is not a "bad point" and check for zero on scalar multiplication result.

From DJB's page:

Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys.
There are some unusual non-Diffie-Hellman elliptic-curve protocols that need to ensure "contributory" behavior.

So for (EC)DH using Curve25519 you don't need to validate public keys.
If you are using Curve25519 for some other elliptic curve protocol you may need to perform validation by making sure the public key isn't in some small subset of possible public keys.


What encryption mode should I use to protect CAN bus communication? I have a CAN bus project and I should encrypt the communication between nodes using the AES algorithm. Which encryption mode should I use?

Theory aside, there's basically no way to have security on the CAN bus.
The Controller Area Network, or CAN bus, is a differential bus that is robust enough for critical communications but simple enough to be used with micro-controllers. CAN bus employs a message-based protocol over four wires, power, ground, CAN-, and CAN+, where the message from a device with the lowest ID becomes dominant on the bus.  In the language of the CAN specification, the “dominate” bit is “0” and “recessive” bit is “1” based on the fact the signal lines are drive to their high and low states by transistors in the dominate state and that resistors passively pull the signal lines to each other in a passive fashion in the recessive state. Relating to physical security of this bus, if you "short" two lines, it will cease to function.
CAN data frame starts with an arbitration field that contains the ID of the node. If two nodes have a message at the same time, both nodes will start transmission concurrently, and the node with the higher ID number in binary will stop transmitting when it sets the bus to be recessive, which is a “1”, but detects that the bus is in a dominate state, which is a “0”. At this point, a collision has happened and the node has lost arbitration. This is also the physical reason that it is impossible to physically protect the CAN bus from a malicious device on the bus, because setting the bus to “0” that forces the bus into the dominate state is an attack on availability, such as a DoS attack. The best that the system can do in this case is to detect the fault and shut down.

Security for CAN bus through authentication protocols for CAN bus proves difficult because authentication codes are not tied to message IDs, which makes them impossible to trace, and do not generally seem appropriate for implementations on simple microcontrollers. Although authentication is required and is an important problem, you will have to focus only on encryption of the data in the CAN frame because of its importance from the hardware implementation perspective.
You cannot use a counter because you cannot guarantee delivery of a packet.  You are pretty much stuck with ECB mode for encryption.


AESManaged Trade Compliance Issue in United States I am currently using AESManaged encryption for my silverlight application. Does AESManaged encryption have a severe trade compliance issue in Bureau of Industry and Security in terms of shipping the application internationally?

I am tempted to say that AESManaged is a class provided by the framework, i.e. you do not ship it: it is already shipped. Then whatever compliance issue may exist is to be handled (and has been handled) by Microsoft, not you.

(I am not entitled in any way to give legal advice, so do not take my word for it.)


If a single bit was known through all states in AES, which would cause the most information to leak? This question is motivated by some bad Verilog.  Due to someone being sloppy with port assignments and a output statement, I have an AES core that has a single-bit from a S-Box in the key schedule tied to a pin.  This was caught in my audit of the HDL; however, it's sort of a neat error.  Due to the nature of the hardware, I can get 10-bits of information about the key out of it as it's configured for AES-128 and it's a very parallel implementation (it's actually the LSB of the squaring module in the S-Box on the lowest byte of the key).  This got me thinking:

If you are an attacker and could watch one bit of AES-128 for 10 rounds, which bit would you choose to recover the most useful information?  I feel it would be a bit in the key schedule.

If you are an attacker and could watch one bit of AES-128 for 10 rounds, which bit would you choose to recover the most useful information? I feel it would be a bit in the key schedule.

Actually, I'd expect a leak of one of the internal state bits would give the attacker more information.

The key schedule is static, and so if you leak 10 bits, well, you still have (at best) 118 bits of uncertainty in the key; no where close to small enough to be useful for an attacker.

However, if you leak the internal state, you can look at (say) one of the internal state bits after each round.  The advantage there is that we can look at the bits for a number of known plaintexts/ciphertexts; this yields considerably more information.  After 1 round, an internal bit is a function of the plaintext and 33 key bits; by looking at a number of plaintexts, we can get enough information to deduce those 33 key bits.


Relation between short and «regular» Schnorr signature I'm failing to fully understand the reasoning in 19.2.3 of Boneh and Shoup's A Graduate Course in Applied Cryptography. That constructs short («optimized»/original) Schnorr signature from «regular» (modern) Schnorr signature.
I get the construction, and that it's described by

The transformation $(u_t,\alpha_z)\mapsto(H(m,u_t),\alpha_z)$ maps a regular Schnorr signature on $m$ to an optimized Schnorr signature, while the transformation $(H(m,u_t),\alpha_z)\mapsto(u_t,\alpha_z)$ maps an
optimized Schnorr signature to a regular Schnorr signature.

Thanks to helpful comments, I now fully understand the mappings, and can now answer my original question: why

It follows that forging an optimized Schnorr signature is equivalent to forging a regular Schnorr signature.

Update: But I lack understanding of why

It will be sufficient to work with 128-bit challenges.

My thinking is that the proof of the regular Schnorr signature models the hash as a random oracle, but we can't model something with a 128-bit output as a random oracle and claim 128-bit security. Also, I'm worried the reduction to the Discrete Logarithm Problem could become one to a different DLP with some 128-bit limitation. And that could be an issue: for example, the problem of finding $x$ given $(g,y)$ with $y=g^x$ becomes tractable¹ when we limit $x$ to 128-bit, or to $x=a\,x'+b$ with 128-bit $x'$ and given $(a,b)$.
Update 2: Pondering that comment, the crux seems to be that a verifier in Schnorr's identification/Σ-protocol needs only a $t$-bit challenge for error probability $2^{-t}$. But that's still foggy for me.

¹ by Baby-Step/Giant-Step in principle, or Pollard's Rho in practice

@Maher's comments guided me to understanding.
To prove security of short Schnorr signature from security of «regular» Schnorr signature with the same hash $H$, we hypothesizes a PPT algorithm $\mathcal A$ that breaks short Schnorr signature, and use it to build algorithm $\mathcal A'$ that breaks regular Schnorr signature, as follows.
$\mathcal A'$ does as $\mathcal A$, except:

Whenever $\mathcal A$ requests a signature: $\mathcal A'$ requests a signature for the same message $m$ from the regular Schnorr signature oracle, gets a regular signature $(u_t,\alpha_z)$, turns it into a short signature $(H(m,u_t),\alpha_z)$ by applying $u_t\mapsto H(u_t,m)$ to the first component of the signature, and uses that for whatever $\mathcal A$ does.
When and if $\mathcal A$ outputs a forgery: $\mathcal A'$ turns that short signature forgery into a regular signature forgery by applying $c\mapsto g^{\alpha_z}\,u^{-c}$ to the first component of the forgery, using only knowledge of public key $u$ and the group parameters.

Algorithm $\mathcal A'$ remains PPT, and breaks regular Schnorr signature with the same probability as $\mathcal A$; only extra cost are more queries to the random oracle performing the hash, and the final computation for the forgery.

What Boneh and Shoup's 19.2.3 leaves unclear to me is how it's justified

It will be sufficient to work with 128-bit challenges.

that is why $H$ with output much narrower that the group order will do in regular Schnorr signature.


Why can't the commitment schemes have both information theoretic hiding and binding properties? The commitment schemes like Pedersen's or Hash based, either have information theoretic hiding and computational binding or computational hiding and information theoretic binding. So can we ever get both information theoretic hiding and binding? Is it ever possible to do, or it is proven to be impossible?

It's impossible. In order to be perfectly hiding, it must be the case that two different messages can produce the same commitment string. But then that commitment can be opened in two ways (by an unbounded committer), so the scheme is not perfectly binding.


How is EC key encoded in PKCS#8? I just started working with certificates and signatures. For an application I write I need a key pair for ECDSA signatures, using the elliptic curve secp384r1 (aka NIST P-384).

I produced such a key pair with the Bouncy Castle lib in Java. Just for testing purposes I then used the JcaPEMWriter to write the two keys to files.

I got the following results:

  -----BEGIN EC PRIVATE KEY-----
  MDUCAQEEMB4Tr3coGQbhIax2Aqs3IJW3D2QmsG1efvhrCeY+6F0K9fTAFT1+mTyL
  ENJ2lUdD/Q==
  -----END EC PRIVATE KEY-----

and

  -----BEGIN PUBLIC KEY-----
  MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEhUvTJddWZidioBHCnPk23SH2C1lITFEK
  UGH63OqRcbE3cfGkykx0XUdHh8ZIKMUhikKr8+ln59sh7Tz1D6TqjtNPsuEMO07t
  ykzbQM+xZT0DMwnVNx+B0UT1Rr9JrNVX
  -----END PUBLIC KEY-----

My questions are:

1) Why is the format of the two key representations different? The private key is in PKCS#8, the public key in X.509 format (at least that is what Java's "getFormat" method tells me). I think there must be some good reason why the developers decided for these different representations, but for me it is just confusing ;-). Is this due to some standard?

2) Next I went to https://lapo.it/asn1js to decode the keys. For the public key I got some information about the algorithm used, and then a 776 bit string. These are 97 bytes. If I understand it correctly, those are made up of one byte telling me that the elliptic curve point is in uncompressed encoding, 48 bytes (=384 bit) for the x-coordinate and 48 bytes for the y-coordinate.

But when I try to decode the private key in the same manner, I get only 48 bytes for the actual key. What exactly do these bytes represent? Is this the curve point in it's compressed form? But in this case, shouldn't there be a flag at the beginning telling me that this is compressed form?

Maybe you can help me get a better understanding of what's going on here. Thank you in advance!

But when I try to decode the private key in the same manner, I get only 48 bytes for the actual key. What exactly do these bytes represent? Is this the curve point in it's compressed form? But in this case, shouldn't there be a flag at the beginning telling me that this is compressed form?

When we generate an EC public/private key pair, we pick a number $x$ and compute the elliptic curve point $xG$, which is $G$ (the well-known "generator point") added to itself $x$ times.

The public key is the point $xG$; because it is a point, we need to state whether we're expressing that point in compressed or uncompressed format.

In contrast, the private key is just the value $x$; this is just an integer, and so doesn't need to be 'compressed'.

As for why your $x$ is 48 bytes (or about 384 bits), we try to select the integer randomly between 1 and the size of the group (which is, in your case, circa $2^{384}$); selecting from a smaller range would reduce the security we get, and selecting from a larger range wouldn't help.


Reversing DJB2 Hashes I have some spare time, and a few hundred DJB2-hashed values sitting around. I thought I'd try to do something "useful" and invert DJB2, such that I could calculate the plaintext of the hashes (which has long since been lost, a fact that is often bemoaned).

For those who don't know, DJB2 is implemented like this: (C#)

public int Djb2(string text)
{
    int r = 5381;
    foreach (char c in text)
    {
         r = (r * 33) + (int)c;
    }

    return r;
}

Text is a string of ASCII characters, so DJB2 has a lot of collisions, a fact that I knew full well going in to this. Fortunately, the plaintext I have has characteristics that will allow me to use heuristical filtering, so false positives shouldn't be much of an issue :)

My algorithm is essentially this, plus some recursion-control (pesudocode):

reverse(hash):
    y = hash mod 33
    for c in [65, 120]:
        if c mod 33 == y:
             print reverse((hash - c) / 33), c

In other words, find the remainder of the hash / 33. Then, for all the ASCII values from 65 to 120, check to see if the value / 33 has the same remainder. If it does, subtract it from the hash, divide the hash by 33, and continue the algorithm. In this way, we only investigate promising paths, because we know that the subtraction of C must leave a number that is evenly divisible by 33.

For example, here is the algorithm working to decode a simple hash:

$h = 177676$
$y = h\mod{33} = 4$
Values of $c$ where $4\equiv c\mod{33}$: $70$ and $103$
I can now pursue only those two values of $c$. (In this case, $103$, or 'g', was correct)

Thus, I know my algorithm works to reverse the hashing process. Unfortunately, I ran into a nasty problem. Djb2 will rapidly overflow the bounds of an int, often with plaintext as small as four characters. This overflow essentially results in r being implicitly modded by $2^{32}$.

Normal division won't work. I asked a question on programming SE about division in this case, and was informed about the multiplicative inverse of 33. Unfortunately, I don't need a division operation (yet), I need a remainder operation! This is proving to be much trickier, and I'm not sure it's even possible.

Here's an illustrative example:

$h = 2090289493$ <-- h is actually $6385256691\pmod2^{32}$ because of the overflow
$y = h\mod{33} = 28$ <-- Incorrect! Should be 32

Here is an example of the algorithm using the operation $\Omega$ and an $h$ that has overflowed. This is what I'd like to do, but I don't know what operation $\Omega$ represents.

$h = 2090289493$
$y = h\ \Omega\ {33} = 32$
Values of $c$ where $32\equiv c\mod{33}$: $65$ and $98$
I can now pursue only those two values of $c$.

Am I on the right track with reversing DJB2 (can it be reversed?)? Is there some way of finding the remainder of a large number that has been modded by $2^{32}$?

Am I on the right track with reversing DJB2 (can it be reversed?)? Is there some way of finding the remainder of a large number that has been modded by 232?

You were on a right track to explain why it can't be easily inverted.

Given an arbitrary $h_i$, every letter of the alphabet will give you another potential $h_{i-1}$ that the value was before that letter was concatenated. Subtract the letter's value, then invert the multiply. That's a possible hash of some string.

Just six or seven letters will allow you to construct most numbers modulo $2^{32}$ as hash values. For strings longer than that it is impossible to tell what the last letter could have been just from looking at the possible hash values before that letter.

Unless you know the strings are very short, trying to invert the function is unlikely to give you much better performance than an exhaustive search such as you'd need to run for a cryptographically strong hash function. I.e. guess strings that match your expected pattern and see if they give the same hash value.


I cannot understand the concept of a divisor for an elliptic curve I am trying to understand ABE for a project of mine. I've grasped the concept of elliptic curves, but could not understand the meaning of divisors for functions on them.

Could anyone help me with this? I mean, why would we want to define functions on an elliptic?  What is the benefit?

As @user94293 mentioned, divisors are a way to keep track of the zeroes and poles of a function. (Poles are related to projective coordinates).

Think of a function like $f(x) = x^2 - x + 6$. It has two zeroes: $-2$ and $3$. If I only gave you these two zeroes, you would be able to recreate the original function, up to a constant factor.

The reason divisors are used in pairing-based cryptography (and thus in ABE) is because the pairing function itself is defined as the function which has a particular divisor. This is enough since, as mentioned, if you have the divisor (and thus the zeroes), you can reconstruct the function.

In particular, the Tate pairing is defined as the function $\tau_r(P, Q) =  f_\tau(Q)^{(q^k-1)/r}$ where $f_\tau$ is a rational function (a function which is the ration of two functions) with divisor $r\langle P \rangle - r\langle \infty \rangle$, which means it has $r$ zeroes in point $P$ and $r$ poles in the point at infinity. This function is computed with Miller's algorithm.

In short, divisors are used to specify the pairing function used in pairing-based cryptography.