Comparing n-multiple amount of merkle trees? I would like to know what best steps are there in finding differences between a high order amount of merkle tree's or if a better associative structure should be used.

I ask this questions because while i have found on comparing two trees for differences i have not found any specifics on comparing n amount at the same time (100-200 for ex).

While i would imagine a sequential validation process from one tree to the next, my question would be if there are any general way to do so.

While I originally looked into what would require the use of some Tree Topology or use of Bloom Filters, I asked a friend on this problem.
He gave me a more practical solution:

Sort each Tree by Leaves Seperately
Then you put each result in heaps - sort of like a merge step of the quick sort algorithm.
You then take the First Heap from the first tree and compare it with the first heaps from the other trees.

If all heaps match, pop all the heaps and you have a leaf present in all of the trees
If the first heap is larger than any given heap, pop it - it doesn't match all the trees. Continue popping from that heap until you find a matching heap, or...
If the first heap is smaller than any given heap, pop all of the previously checked heaps - all of them contain a leaf that is not present in all of the trees
Repeat until one of the heaps is empty

This solution has a linear complexity - you will compare each leaf about 1 time.


AES-256 CTR with ESSIV, is this correct? I am having some problems encrypting disk using AES-256 in CTR mode, with ESSIV iv generation (I am aware of couple of flaws, although this mode is enough for now). What I have here is:

S = SHA256(K), result 32 bytes
K = original key, 32 bytes
SN = sector number, 16 bytes
E = AES-256 CTR
IV2 = generated iv, 16 bytes

What I am doing with it:

IV2 = E(data=SN, key=S, iv=SN)
decrypted_data = E(data=encrypted_data, key=K, iv=IV2)

In couple of sources (e.g. here: https://is.muni.cz/th/vesfr/final.pdf) I got that for ESSIV generation I should use the exact same block cipher as for main de/encryption. However, I am getting wrong results. Is this the correct approach?

Thanks.

It seems in my case IV was supposed to be generated using AES-256 in ECB mode.

ESSIV_IV = E(data=SN, key=HMAC(KEY))

where E is AES-256 ECB, SN is sector number of disk data, extended to 16B (padded with zeros) and KEY is 32B long encryption key (HMAC = SHA-256).


Is there a preferred way/standard on how to transmit an initialization vector for AES encryption Is there a preferred way on how to transmit the initiliazation vector with witch AES encryption was made? I could imagine that, if the encrypted data is stored to a file, the IV is preppended at the file's beginning before the actual encrypted data (or somehting similar).

Is there such a convention?

The most common way to transmit an initialization vector is, indeed, to prepend it immediately before the ciphertext.

When you look at the original ciphermodes the first used IVs (CBC, CFB, OFB), the IV actually does function as a 'previous ciphertext block' for the very first actual ciphertext block; placing it immediately in front of the very first ciphertext block makes more sense than any other alternative.

Now, for newer modes (such a CTR), the IV is used in other ways internally.  However, the convention stuck.


Is Common Name encoded in the certificate? When I make a certificate like so

cd /etc/openvpn/easy-rsa/2.0/
source ./vars
. /etc/openvpn/easy-rsa/2.0/build-key client1

Then commonName is set to client1.

When I ask the OpenVPN server what the commonName is of the user who is connected, can I then trust, that the user haven't altered his commonName in the certificate?

Update

I have tried to change all the clear text in the crt file on both the client and server, but the certificate still works and the OpenVPN server still replies with the proper commonName and Subject.

This certificate still works, where I have altered all plain text. I have removed the actual certificate for security reasons.

If commonName and Subject isn't extracted from the plain text. Where does OpenVPN then gets them from?

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 5 (0x5)
        Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=X, ST=X, L=X, O=X, OU=X, CN=X CA/name=X/emailAddress=X@X.X
        Validity
            Not Before: Jan 12 12:53:47 2012 GMT
            Not After : Apr 11 12:53:47 2012 GMT
        Subject: C=X, ST=X, L=X, O=X, OU=X, CN=X/emailAddress=X@X.X
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:a5:40:a0:e4:44:3e:27:4c:13:69:03:a7:c3:38:
                    4f:dc:43:dc:fb:f5:43:c8:5b:50:8b:7f:0d:f4:d8:
                    30:00:e0:e3:f7:75:1c:3b:e2:08:95:8e:31:cf:a7:
                    6f:e2:94:f4:4d:7c:c4:11:a9:a5:84:1b:95:2b:9a:
                    93:da:ad:34:ae:df:5d:9d:0a:18:b3:df:86:c1:f6:
                    fb:fe:d8:16:64:a9:bf:91:51:8a:54:ba:26:5a:b4:
                    6a:88:c3:52:a7:fa:86:39:08:20:c1:53:3d:f3:12:
                    e1:50:37:11:16:db:99:53:02:82:6f:a0:05:9f:23:
                    ff:bf:79:93:1c:ef:1e:4e:31
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Basic Constraints:
                CA:FALSE
            Netscape Comment:
                Easy-RSA Generated Certificate
            X509v3 Subject Key Identifier:
                89:E7:7A:9B:1F:72:15:91:BD:D0:F4:67:A8:A1:C3:E0:0D:B1:3A:B3
            X509v3 Authority Key Identifier:
                keyid:75:A6:F1:68:88:53:F5:9B:14:4A:67:00:0B:58:7C:38:1C:A0:A1:F8
                DirName:/C=X/ST=X/L=X/O=X/OU=X/CN=X CA/name=X/emailAddress=X@X.X
                serial:80:D1:56:33:4C:5D:6D:57

            X509v3 Extended Key Usage:
                TLS Web Client Authentication
            X509v3 Key Usage:
                Digital Signature
    Signature Algorithm: sha1WithRSAEncryption
        9c:a5:2b:a8:cf:86:60:90:f3:45:80:78:30:89:6a:56:cc:09:
        e8:a4:75:25:af:04:52:8f:15:7b:cd:87:94:f3:c4:2f:99:3f:
        b5:51:f7:e1:de:96:92:ae:0a:77:9e:1f:fb:8a:c3:de:84:3c:
        bb:4f:7f:f1:67:af:0c:1e:b0:90:2c:de:63:f8:47:89:f5:7b:
        57:fe:e4:8d:1d:1e:62:19:27:99:83:99:9f:4d:08:ef:b6:b4:
        7d:56:5d:ca:39:fd:1c:f3:15:6a:da:bc:51:ca:ad:59:7c:af:
        77:72:3c:ca:e7:dc:74:bc:c0:de:2e:f7:b2:27:1b:a7:ae:02:
        0f:9c
-----BEGIN CERTIFICATE-----

-----END CERTIFICATE-----

The "Common Name" is part of a X.500 name; here, the one called "SubjectDN", which designates the owner of the public key which is contained in the certificate. That name is part of the certificate, in the part which is covered by the signature; as such, it is exactly as trustworthy as any other element in the certificate.


Is a simple stream cipher "partially homomorphic" if no integrity check is applied? My understanding is that, simply put, a stream cipher is just a CSPRNG such that $R(i,k)$ will produce a deterministic but statistically random sequence, where $i$ is an IV, and $k$ is the session key. The resultant key-stream $K$ is then combined with plaintext (i.e. $C = K \oplus M$).

Now, if we take two messages $m_1$ and $m_2$, and assume $\mathcal{E}(x)$ and $\mathcal{D}(x)$ are functions that encrypt and decrypt a message as described above, surely the following is a partially homomorphic cryptosystem?

$$\mathcal{D}(\mathcal{E}(m_1) \oplus m_2) = m_1 \oplus m_2$$

This seems a really simple and fundamental way to perform unauthenticated homomorphic cryptography, yet the Wikipedia article doesn't mention it at all.

Am I incorrect in saying that this process demonstrates homomorphism?

To answer your question: no this is not homomorphic encryption because one of the plaintexts is used unencrypted. There may be times when it is a useful property, but the only uses I know of it are to demonstrate the malleability of xor ciphers.

To be a homomorphic encryption function, it should be possible to calculate the encryption of some function of the plaintexts from their respective ciphertexts without using the key. That is, given $c_1=e_k(m_1)$, $c_2=e_k(m_2)$ one should be able to calculate $c_3=e_k(f(m_1,m_2))$ by evaluating some $g(c_1,c_2)$.

More generally, a homomorphism is a mathematical function that preserves some operation. For example, if an encryption scheme $e$ would be xor-homomorphic if
$$
  e(m_1)\oplus e(m_2) = e(m_1\oplus m_2)
$$

More complex schemes might commute with other operations. For example the Pallier scheme uses the fact that
$$
   a^x \cdot a^y = a^{x+y}
$$

To construct a scheme that uses multiplication of ciphertexts to calculate the sum of plaintexts.


Are Koblitz curves paring friendly? I want to implement an identity based encryption scheme using Koblitz curves as scalar multiplication is faster due to Frobrenius endomorphism.

How can I tell if a curve over $\operatorname{GF}(2^m)$ is pairing friendly or not?

I have found this paper called "Elliptic Curves Suitable for Pairing Based Cryptography" but I think it talks about curves over $\operatorname{GF}(p)$.

Let $q$ be the base field cardinal; in your case, $q = 2^m$ for some integer $m$. We need $m$ to be prime for a Koblitz curve, otherwise the curve would also be defined on non-trivial sub-fields, allowing for faster discrete logarithm. For a "pairing-friendly curve", we need the curve order to be a multiple of a prime $r$, and the pairing produces outputs in $\mathbb{F}_{q^k}$ for some integer $k$ which is the embedding degree.

That degree $k$ is the smallest $k\gt 1$ such that $r$ divides $q^k-1$. For a random curve, that degree is very high, on the same order of magnitude as $q$ itself, so computing the pairing would entail using values that cannot fit on an existing computer (or in the whole universe, for that matter). This is the case for all "standard" Koblitz curves (K-163, K-233, and so on).

Moreover, since a pairing transforms discrete logarithm on a curve into discrete logarithm in a finite field, you would need that finite field to be large enough for discrete logarithm to be hard. It has been recently shown that discrete logarithm in fields with small characteristic, in particular binary fields, is much easier than the discrete logarithm modulo a big prime; current records include fields of more than 9000 bits in size. Therefore, if you want to use binary fields for pairings, and still retain some decent security, then you need to use a destination field so large that computations will be very slow, thereby voiding any computational advantage from the curve being binary (Koblitz or not).


How secret key is sent in cipher-texts? Secret key is included in cipher text. so how can we say that if hacker grab the cipher text he will not be able crack the code? if he cannot do with cipher-text then how receiver can crack the message from same cipher-text? what is difference?

Most of the time - the key is not included in the cipher-text. The key needs to be "pre-shared" between the sender and recipient. This is true for symmetric encryption.

Or - the key can be encrypted using the asymmetric encryption. That the sender could encrypt with the recipient's public key (not secret) and only the recipient could decrypt with its private (secret) key.

This is base of the asymmetric encryption. It is very expensive (in performance), so a one-time symetric key is generated and encrypted using the asymmetric encryption. The key is used for symmetric encryption of the payload (of any size). The recipient receives the encrypted symmetric key (what could be retrieved using the private asymmetric key) and then the rest of the payload can be decrypted.


what is the state of the art algorithm to encrypt credit card data We have a business requirement to keep credit card data. What is today's (Nov 2013) state of the art algorithm to encrypt credit card data that will be saved on disk? Additionally, I'd appreciate pointers to Java libraries that implement these algorithms

Note that we are PCI compliant and we already store credit card data. I am doing a review to make sure that our encryption method remains state-of-the-art

In practical cryptography, you do not use state-of-the-art, the newest and shiniest algorithms, but instead something required or recommended by the appropriate standards.

In PCI, AES, Triple-DES, SHA-1, RSA etc. are fairly common. PCI is bit slow to adopt  new cryptographic standards. This is for part that payment industry uses devices (like cards) with relatively underpowered processing units.

If you want something that is state-of-the-art, and practical, you may enjoy e.g. cr.yp.to, but those algorithms are likely not accepted by some of the PCI standards.

For encrypting credit card data stored on disc, one modern fancy combination would be  AES-256 with FPE.


Are there any successful preimage attacks? Are there any successful preimage attacks on any serious cryptographic hash algorithm or at least on serious-looking non-cryptographic hashes (like MurmurHash)?

MD4 is Not One-Way. The attack described in the 2008 paper is a theoretical attack with complexity $2^{102}$, which is better than the brute force complexity of $2^{128}$. In later theoretical results reported here the complexity dropped to $2^{94.98}$ and here it dropped even further to $2^{69.4}$ for secondary pre-image attacks.

Similarly, The MD2 Hash Function is not One-Way as reported in a 2004 paper, where the complexity of finding pre-images was reported to be $2^{104}$, compared to the brute force complexity of $2^{128}$. The attack was improved in 2008 to a complexity of $2^{73}$.

Other examples include draft algorithms that are broken during the initial design phase or peer-review phase, such as the SHA-3 submission Maraca.

Non-cryptographic hashes, such as MurmurHash, are usually not designed to be one-way. In order for something to qualify as a proper "attack", it has to do better than anticipated given the security claims. If there are no security claims, there can't really be any attacks either. And of course, if there are no security claims, the algorithm should obviously not be used for cryptographic purposes.

A helpful hint might be to only use algorithms that are published, have security claims, and always search for papers that mention the algorithm name here https://eprint.iacr.org/search.html before using it for production purposes. Practical attacks are almost always preceded by theoretical attacks, and theoretical attacks are often (almost always?) published somewhere. This doesn't, however, apply to every proprietary algorithm on the Internet, and also not to algorithms that are not designed for cryptographic purposes to begin with.


What does the cipher-text overhead means? I have two questions here.

What does the cipher-text overhead means?
Why we were suggested not to encrypts the plain-text itself instead just encrypts only the key (i.e random number)

Cipher Text overhead is the positive difference in length between the encrypted text and the plain text.

In stream ciphers, the encrypted length is typically equal to the clear text so there is no overhead. However, when Initialization Vectors are used - this will add to the size.
In block ciphers, there is usually padding involved such that the size of the plain text increases to being a multiple of the blocksize. So the encrypted size is the size of the plain text + padding. Chaining mode and Initialization Vector also adds extra length.

I think your questions refers to stream ciphers where the key is used to generate the stream and then stream is XOR'ed with the plain text to get the encrypted text. i.e. the key itself is not used directly to encrypt the plain text. The key + some state is used to generate the stream. And then stream & plain text are combined (typically by XOR) to create the encrypted text.

OTOH, if you are referring to Hybrid Encryption as suggested in the comments, then this is the explanation - The advantage of PKI is that it does not require the 2 parties to share a common secretHowever, PKI is much more inefficient and slower than symmetric cryptosystems. A hybrid cryptosystem combines the convenience of a PKI with the efficiency of a symmetric encryption.

In hybrid encryption, the symmetric key to be used for the encryption is agreed upon using PKI, but the rest of the communication is encrypted by the symmetric key.

For very long messages, the bulk of the work in encryption/decryption is done by the more efficient symmetric-key scheme, while the inefficient public-key scheme is used only to encrypt/decrypt a short key value.


Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm The question stems from the fact that foundations of crypto states:
suppose breaking an encryption scheme is NP-complete, then P != NP implies that this encryption is hard to break in the worst case, but does not rule out the possibility that it can be broken almost always.
How can this be true, if the encryption is NP-complete breaking should take super-polynomial time no?

The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this.  It was designed to rely on the difficulty of the subset sum problem, which is NP-complete.  However, while NP-complete means, under the P ≠ NP hypothesis, that there is no polynomial-time algorithm to guarantee a solution for every input, that doesn't mean the legitimate user can efficiently generate keys or ciphertexts for which all polynomial-time algorithms to decrypt ciphertexts or recover keys will fail with nonnegligible probability.  And it turns out that the knapsack cryptosystem is easily breakable.

Now, it is not always the case that cryptosystems with relations to NP-complete or NP-hard problems are practically breakable.  For example, the McEliece cryptosystem (Wikipedia article), whose decryption is related to the NP-hard problem of decoding general linear codes, has withstood scrutiny of decades, and modern parametrizations are not known to be breakable even with a quantum computer.

For more about P = NP and crypto, see also an earlier post I wrote on the usefulness of asymptotic cost analyses versus concrete cost analyses.  The brief summary is that even if P = NP, that fact may nevertheless have no practical consequences for cryptography.


What advantage is there for using a nonce and a timestamp? I know both nonces and timestamps are used to prevent replay attacks, and nonces may offer increased security in the situation a message could be replayed with the timestamp in the allowable window. However, if a nonce can provide all the protection a timestamp does, why would they ever be used together?

However, if a nonce can provide all the protection a timestamp does, why would they ever be used together?

If you use a timestamp in combination with a nonce, it can help mitigate the risk of nonce reuse.  Guaranteeing that nonces are never duplicated within the relevant scope can often make a system more complicated, because it needs to maintain state reliably while that scope is "alive."

Imagine, for example, that a system that sends packets encrypted with a counter nonce loses power momentarily, comes back up, and resumes transmission with the key/nonce pair that was saved before the power failed.  How do you guarantee that it won't reuse a nonce that it used just before the power loss?

These sorts of problems fall under the rubric of stateful cryptography—cryptographic schemes that require you to keep and update some state between invocations in a correct fashion.  Keeping such state incorrectly or unreliably is a common source of failures.  Timestamps don't always solve state problems, but they sure can help.

In addition they can be helpful for all sorts of non-cryptographic reasons.  For example, timestamps on their own can't generally provide a total order over events because two events may be measured to have happened at the same time.  Adding a counter gives you a way of consistently ordering such simultaneous events—even an arbitrary order (that does not reflect reality in any sense) is often useful if all parties agree on it.

If we're talking about replay in particular, if you authenticate the timestamps as associated data and reject data that's tagged too far in the past, you often cut many of the attacker's options, which is generally a plus.  But that however doesn't require you to use the timestamp as a nonce for an encryption algorithm, but rather as associated data for authentication.


How can SSL secure a two-way communication with only one key-pair? As I understand it, SSL involved the use of a public-private key pair.  How does this enable two-way communication?

Suppose I have some server with which I wish to communicate securely.  I connect to it, and it supplies me a certificate, which contains its public key (assume the certificate is valid).  I then take my request, and encrypt it with this public key, and transmit the resultant ciphertext to the server.   This communication is secure from eavesdropping.  But how does the server return to me my results securely?  I lack a public/private key pair, and have no certificates.

That's not quite correct.  In SSL, two things happen:

First, a session key is negotiated using something like the Diffie-Hellman method.  That generates a shared session key but never transmits the key between parties.
Second, that session key is used in a normal symmetric encryption for the duration of the connection.

SSL does use public/private in one way, because an X509 certificate is used to identify at least one end of the connection.  Those certs are signed using an asymmetric key pair.


Encrypting multiple small messages with a single reused symmetric key What is a good way of doing this? Practical and Secure.

This is for a browser environment.

For example, let's say there are a few 100 independent messages of about 100 characters each that you want to send to the server independently and in an arbitrary order and you want to encrypt them with the same key before they are sent to the server because you don't want the server to have the contents of the messages. The next day the server may return some of those messages and the user should be able to decrypt them in the browser with the same key.

How would you do this?

What encryption scheme and what block cypher? Why? What library is recommended?

NOTES:

This is in addition to HTTPS not instead of it.
The user does trust the server to send a trustworthy encryption function and use it.

You can use any authenticated, secure cipher. AES-GCM is currently used a lot. You need a nonce per message to use AES-GCM or you can use one of the SIV variants, which calculate a nonce (Synthetic IV) assuming that the messages are all distinct.

The question is more how to store the symmetric key than anything else, but that's not really a cryptography question - it's more about browser security and offline storage and such. Deriving a key from a passphrase might be a good idea, but note that you need a good key derivation mechanism in addition to a strong passphrase.

Often it makes sense to use asymmetric cryptography so that you don't need the private key during encryption. Keeping the key secure is the main issue with cryptography after all. In that case the passphrase could be used to wrap / unwrap (encrypt / decrypt) a private key value. Unfortunately you'd need local storage to store the wrapped private key - and this might be an issue in itself.


"Fine grain Cross-VM Attacks on Xen and VMware are possible" and OpenSSL 0.9.7 Here's a paper that just made its way into Cryptology ePrint Archive: Fine grain Cross-VM Attacks on Xen and VMware are possible!.

Its a good survey of past attacks and presents a couple of new techniques for AES against OpenSSL, PolarSSL and Libgcrypt.

Why did the authors use OpenSSL 0.9.7? That's from 2007, and I don't believe its even supported any longer.

Actually the authors used both OpenSSL 0.9.7 and 1.0.1; they detail the differences between the versions, what changed in the implementations, and what they can do from other VM.

They refer to 0.9.7 because that was the version used by Bernstein in 2003 when he worked on cache-timing attacks on AES. This allows to highlight how much (or how little) the cross-VM boundary complicates things for the attacker. They also did tests on 1.0.1, since that's the current, modern version.


Why doesn't Wang's attack work on SHA-1? Wang's (et al) differential attack works on MD5, MD4, RIPEMD and HAVAL.

Why doesn't it work on SHA-1?

The message expansion step in SHA-1. The compression functions for MD4,MD5, RIPEMD and I think HAVAL only re-arrange and re-use words in the message block.

SHA-1 will expand the message from 16 words to 80 words using a rotation and XOR operation. The additional 64 words are a function of every word of the message block.

Because of this additional dependence on previous words in the block, Wang's attack will not work.


Is it necessary, that the public key is a prime number in the RSA algorithm? I read some  books talk about RSA cryptography but I did not understand something when choosing a public key $e$ Sometimes the condition is

$1<e<$$\phi(n)$

Where $\phi(n) = p-1 * q-1$

also sometimes is

$e \in [{1,2,...,\phi(n)-1}]$

also sometimes is

$e$ should be prime number

Examble

Choose $p = 3\ and\ q = 11  $

Compute $n = p * q = 3 * 11 = 33 $
Compute $\phi(n) = (p - 1) * (q - 1) = 2 * 10 = 20$
Choose $e$ .here can choose e = 7 where 7 is prime number or I can choose $e=9$ where 9 is relatively prime to 20.

My question

Are both states right when choose 7 and 9. or not right .If no why???

There is no specific reason why $e$ is required to be a prime number.  It must be relatively prime to $\phi(n)$ (otherwise we can't decrypt uniquely); however that is the only hard requirement.  Assuming that 9 is relatively prime to $\phi(n)$, there is no reason why 9 can't be used as a public exponent.

However, selecting a prime value for $e$ does have this practical advantage; for prime $e$, then the requirement that it is relatively prime to $\phi(n)$ is equivalent to the statements that $p \ne 1 \pmod{e}$ and $q \ne 1 \pmod{e}$ (where $p$ and $q$ are the prime factors of $n$). If we use the common logic of selecting $e$ first, and then $p$ and $q$, this turns into a relatively simple additional criteria when doing prime selection.


What are the relative merits of padding algorithms pkcs7, iso7816, and x923? I am assuming none of these padding algorithms are "the best"... But what are the advantages and disadvantages of using them? PKCS7 is certainly the most commonly used one, but I am interested in seeing what the others offer.

ANSI x.923 padding and the padding used within PKCS#7 are functionally equivalent. The last byte of the padding stream is the length of the padding stream. The difference is the value of the other bytes, which are all 0x00 in ANSI, and all the identical to the last byte in PKCS#7.

f4 93 d6.00 00 00 00 00 00 00 00 00 00 00 00 0d    ANSI X.923
f4 93 d6.0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d    RSA PKCS#7

Neither has a large advantage over the other, except that a zero padded message can be "fixed" to ANSI padding by simply changing the last byte in many cases.

I do not believe that either one requires official verification of the padding bytes preceding the last byte to verify that they are correct per the standard, meaning the same algorithm can decode either scheme by simply looking at the last byte. The same algorithm will also decode ISO 10126 padding.
If used in an unauthenticated scheme, the bytes should be checked for correctness, since some attacker advantage could be achieved through their manipulation. Verification is done with bitwise OR against those bytes, which then must either equal 0x00 for ANSI or the length byte for PKCS#7 padding.
Both only support up to 255 bytes of padding.
PKCS is by RSA for RSA products and algorithms, and ANSI is a generic common standard by committee with the goal of interoperability.

ISO/IEC 7816-4 is a different story. It is more flexible and can technically support an unlimited length of padding bytes, however removal of the padding can be more computationally intensive. ISO/IEC 7816-4 padding places a single 0x80 byte after the message, then pads the rest with 0x00.
The padding scheme is also known as bit padding, as it simply places a single 1 bit after the plaintext, followed by 0 valued bits up to the block size; it therefore works for bit oriented protocols as well.

f4 93 d6.80 00 00 00 00 00 00 00 00 00 00 00 00    ISO/IEC 7816-4

By specification you must start at the end and work backwards, checking every byte until you hit 0x80. If you hit something other than 0x80 or 0x00 the message is assumed to be incorrectly decoded. With a small block size this is quite fast.
ISO/IEC 7816 contain the ISO/IEC standards for electronic ID cards like smart cards. Systems that use the standard have mandatory padding for encrypted data.

I have also seen what I called "rainbow" padding, which looked to be a hybrid of ANSI and PKCS7. The last byte was the amount of padding bytes, and the preceding bytes were that value decrementing until the message boundary:

f4 93 d6.01 02 03 04 05 06 07 08 09 0a 0b 0c 0d    ???

I have never seen it described by a specific name, but it may be removable by an ANSI/PKCS remover if the remover only takes the last byte into account.

As you mentioned, none of these padding schemes are perfect. Only IEC 7816 can support block sizes of 256-bits and larger, and ANSI and PKCS7 can be unpadded by a common algorithm.


Seed a PRNG with random data and a password I'd like to combine a random key file with a password to generate a secure seed for a CSPRNG. The key file is assumed to have very high entropy, but the password will be whatever the user provides. What's the best way to combine the two in order to seed the PRNG? The goal of course is that the output of the PRNG will be difficult to predict unless you have both the key file and the password.

My first thought it to simply use PBKDF-2 to stretch the password so it's the same size as the key file, then XOR them together. I won't be transmitting this seed or anything, so I don't think it matters that this in itself is poor encryption. But are there any other considerations I should make?

I will most likely be using AES in counter mode for the PRNG, but an answer covering a more generic case would be appreciated. Also, I'm assuming that the key file is the same size as the seed that the PRNG will take.

If your password has a low entropy (or "could have a low entropy") and the "key file" is assumed to be known to an attacker, you really need some key stretching like PBKDF-2, bcrypt or scrypt with a suitable work factor to detain possible attackers.

As these functions also have a salt input, and you actually have another entropy source (the key file), I would use the key file as the salt input and the password as the key input to these schemes, and produce an output of suitable size for your CSPRNG seed.

I suppose the same scheme is also secure when only the password is known (and not the keyfile used as salt), though this is not a direct design goal of these password hashing schemes.


Attack against $\operatorname{DESA}_{k,k_1} (x) \underset{\text{def}}= \operatorname{DES}_k(x)⊕k_1$ Problem 5.16 in this pdf, from the book: Christof Paar, Jan Pelzl, Understanding Cryptography

5.16. This is your chance to break a cryptosystem. As we know by now, cryptography is a tricky business. The following problem illustrates how easy it is to turn a strong scheme into a weak one with minor modifications. We saw in this chapter that key whitening is a good technique for strengthening block ciphers against brute-force attacks. We now look at the following variant of key whitening against DES, which we’ll call DESA:
$$\operatorname{DESA}_{k,k_1} (x) \underset{\text{def}}= \operatorname{DES}_k(x)⊕k_1$$
Even though the method looks similar to key whitening, it hardly adds to the security. Your task is to show that breaking the scheme is roughly as difficult as a
brute-force attack against single DES. Assume you have a few pairs of plaintext–
ciphertext.

Normal DES
Let's say you have a normal DES plaintext-ciphertext pair encrypted with 56 bits key $k$ where $C_1=DES_k(P_1)$.
In the worst case, one needs to try the $2^{56}$ possible keys to find the encryption key. And later on, one can decrypt all Ciphertext encrypted with the key $k$
DESA
Let's say one has 2 pairs of plaintext-ciphertext pairs ecnrypted with
$k$ (the usual 56 bits key size) and $k_1$ (64 bits since the block size)  where $C_2=DESA_{k,k_1}(P_2)$ and $C_3=DESA_{k,k_1}(P_3)$
So one can x-or given two ciphertext and:
$C_2\oplus C_3 = DESA_{k,k_1}(P_2)\oplus DESA_{k,k_1}(P_3)= DES_k(P_2)\oplus k_1\oplus DES_k(P_3)\oplus k_1=DES_k(P_2)\oplus DES_k(P_3)$
So, $k_1$ is gone. In the worst case, one tries $2^{56}$ times and get $k$ with two plaintext-ciphertext pair.
Then, for any ciphertext with the help of previous equation one can calculate the $k_1$
$$C_1 = DES_k(P_1)\oplus k_1$$
knowing the key $k$ one can calculate $k_1$.
So in total $2^{57}+1$ DES encryption is called, instead of $2^{56+64}$ key size.


SPA resistant RSA trace I am trying to perform simple power analysis on RSA. In particular focusing the
modular exponentiation module and for this I have implemented left-to-right variant of binary exponentiation.

pseudo code of the implemented algorithm is as follows:

Result = a^b mod N
k = length(b);

Result = 1;
for i = k-1 to 0 do
  Result = (Result X Result) mod N;   // SQUARING

  if b[i] == 1
    Result = (Result X a) mod N;     // MULTIPLICATION
  end if

end for

From the acquired power trace, I cannot differentiate between square and multiplication samples just by looking at the trace.

I also tried by performing a correlation test between the first operation(i.e. square) and all the other operations but i get the same level of correlation peaks for all the operations.

So from these observations can I conclude that my implementation is SPA resistant at least with respect to the regularity between the patterns of both operations.

My second question is, if it is SPA resistant then why in some of the cases which I read on internet have different pattern for both operations. Even though in practice they also use same multiplication algorithm for both squaring and multiplication as I did.

Clearly, your code is not SPA safe.
The if condition over a sensitive bit will certainly leak in timing. The time taken by a square is slower that a multiplication due to this if condition.
Exemple: bit 000 will induce a Square Square Square in term of cpu instruction will have less than a bit 100 where you will perform Square Multiply Square ...
Try to compare couple of operations instead of individual.

Regarding, the difference between a square and a multiply it depends on the chip you are working on, does modular operation are provided by a crypto processor? In this case, some countermeasures might have been implemented to avoid differences between a multiplication and a square.

You can share your traces if you like.

edit

Here is two SPA safe algorithm

Atomic The most elegant SPA safe algorithm, imo http://bcm.crypto.free.fr/pdf/CCJ04.pdf Fig2

The Montgomery Powering Ladder  Less efficient as it is a square and multiply always (trash multiply for square) https://www.iacr.org/workshops/ches/ches2002/presentations/Joye.pdf


Number of Substitution boxes How many possible 16 bit S-boxes exist? (AES uses 8 bit substitution boxes)
I first taught of calculating 128(keysize in bits)/8(bits) =16, but I believe it's wrong.

An s-box is a bijective function $f: \{0,1\}^b\rightarrow\{0,1\}^b$. This reduces the question to "how many of those $f$ exist".

To see this easily, imagine domain and image of this function as two boxes with $2^b$ elements. How many different sets of arrows can you imagine between those two sets?

For the first arrow, you have $2^b$ choices. For the second arrow, you have $2^b -1$ choices. For the third, $2^b-2$, and so forth to the last arrow, where there's one choice left.

Multiplying those together, you would get $2^b(2^b-1)(2^b-2)\dots 1=2^b!$ possible s-boxes, so in your 16-bit case that makes $2^{16}!$ possibilities.

To put this more mathematically, an s-box is a permutation of $2^b$ elements, and there are $2^b!$ such permutations.


ChaCha20-Poly1305 test vectors I was trying to use OpenSSL 1.1 (via Ruby) to validate the ChaCha20-Poly1305 test vector from this IETF draft: https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7

The relevant test vector is quoted here:

The following block contains a test vector for the
AEAD_CHACHA20_POLY1305 algorithm.  The first four lines consist of
the standard inputs to an AEAD algorithm and the last line contains
the encrypted and authenticated result.

KEY:    4290bcb154173531f314af57f3be3b5006da371ece272afa1b5dbdd110
        0a1007
INPUT:  86d09974840bded2a5ca
NONCE:  cd7cf67be39c794a
AD:     87e229d4500845a079c0
OUTPUT: e3e446f7ede9a19b62a4677dabf4e3d24b876bb284753896e1d6

This gives me an 8-byte nonce. But when I try to run this test, I quickly run into a problem:

cipher = OpenSSL::Cipher.new("chacha20-poly1305")
cipher.encrypt
cipher.key = ["4290bcb154173531f314af57f3be3b5006da371ece272afa1b5dbdd1100a1007"].pack("H*")
cipher.iv = ["cd7cf67be39c794a"].pack("H*")

ArgumentError: iv must be 12 bytes
        from (irb):81:in `iv='
        from (irb):81
        from ~/.rvm/rubies/ruby-2.4.0/bin/irb:11:in `<main>'

How come OpenSSL is insisting on a 12-byte nonce, but the draft spec is giving me an 8-byte nonce? I'm still learning about ChaCha20 and Poly1305, so I'm sure I'm missing something basic.

For the complete picture, as was pointed out, you should use the final RFC, not drafts. There are two relevant RFC here:

RFC 7539 describes the stream cipher ChaCha20, the MAC algorithm Poly1305, and an Authenticated Encryption with Associated Data mode that combines ChaCha20 and Poly1305 in a safe way (in particular, it uses ChaCha20 to provide the secret values needed by Poly1305).
RFC 7905 describes TLS cipher suites that rely on the AEAD construction described in RFC 7539; that RFC explains how the associated data and nonce are built in the context of TLS.

In RFC 7539, section 2.6, there are some explanations about the nonce. The nonce must have length exactly 96 bits (12 bytes); however, the following text appears:

The protocol will specify a 96-bit or 64-bit nonce.  This MUST be
unique per invocation with the same key, so it MUST NOT be
randomly generated.  A counter is a good way to implement this,
but other methods, such as a Linear Feedback Shift Register (LFSR)
are also acceptable.  ChaCha20 as specified here requires a 96-bit
nonce.  So if the provided nonce is only 64-bit, then the first 32
bits of the nonce will be set to a constant number.  This will
usually be zero, but for protocols with multiple senders it may be
different for each sender, but should be the same for all
invocations of the function with the same key by a particular
sender.

This is why the test vector in RFC 7539, section 2.8.2, shows this:

IV:
000  40 41 42 43 44 45 46 47                          @ABCDEFG

32-bit fixed-common part:
000  07 00 00 00

These are a 64-bit IV and a 32-bit "fixed-common part", which are meant to be assembled (concatenated) into the 96-bit value that the algorithm requires.

However, if you look at RFC 7905, you will see that what happens in TLS is something a bit different:

AEAD_CHACHA20_POLY1305 requires a 96-bit nonce, which is formed as
follows:

1.  The 64-bit record sequence number is serialized as an 8-byte,
    big-endian value and padded on the left with four 0x00 bytes.

2.  The padded sequence number is XORed with the client_write_IV
    (when the client is sending) or server_write_IV (when the server
    is sending).

In other words, a full 96-bit (12 bytes) value is generated from the handshake, and the record sequence number is XORed into the last 8 bytes. An alternative design, more in line with the method explained in RFC 7539, would have been to concatenate a 32-bit (4 bytes) value generated during the handshake with the 64-bit (8 bytes) record counter. However, the RFC 7905 designers found it fit to use the XOR method, which can be argued to make nonce reuse between distinct TLS connections even less probable (not that it would matter much, since distinct TLS connections also use distinct encryption keys).


Secure multiparty computation... where one entity owns all parties Here's a corner case for you.

A user produces a small amount of confidential data and would like to delegate a third-party to perform some computation on it and return the results. Data and results are to be kept secret from the third-party, you can assume a "curious but honest" threat model.

My first naive intuition was that this would be an obvious application of FHE, but now I wonder... is there any way to tackle this use case using sMPC instead?

In other words: split the input data into a number of "workers" which are all controlled by the same third-party. Is there any sMPC scheme that is robust to such a scenario?

Thanks.

No.

If you split the data between the parties, say using additive secret sharing, anyone controlling all parties can recover the full data. That is part of the very definition of secret sharing. If you want to ensure that the data will remain hidden even when the adversary controls all parties, then you cannot simply run a secure MPC protocol on shares of the input, you need something that will hide your input even when the state of all parties is known. Homomorphic encryption is indeed the most natural solution that comes to mind.


How to select salt an IKM for HKDF I have an application where I need to combine a Diffie-Hellman shared secret, with a user's password and derive a key. I'm investigating the possibility of using HKDF to as follows

Initial Keying Material(IKM)= DHE-shared-secret and
salt                        = password-utf-8-bytes

I choose this because the DHE-secret is larger and, has more entropy than the password bytes. Is this correct or should it be the other way around?

I'd say that if you'd use HKDF as it is supposed to, then you should concatenate the two the concatenated result as Input Keying Material (IKM). HKDF has an extract first which will compress the IKM so you can input as much keying material as required.

You should of course make sure that it is impossible to have collisions for concatenated secret and password pairs. This is easily accomplished by making sure that the DH secret is constant sized (which is best practice anyway).

It is always possible to later add an actual salt; a password is not unique across invocations and therefore it is unsuitable to be a salt. You may want to add a salt later to reach a higher security level and leave it empty for now.

You may want to first perform a password hash over the password and include the result in the HKDF calculation. The reason for that is that currently the other party of the key agreement must know the password in advance. It is better to store a password hash in case the other other party gets compromised.

With that in mind you may also be interested in SRP and other augmented PAKE protocols.


Why is SubtleCrypto API generating different signature for same data? I am trying to generate key pairs using SubtleCrypto API in javascript and then using the same to sign some data using ECDSA algorithm. Documentation for the same can be found at this link.
https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/sign
An implementation of the same API can be found at this link.
https://github.com/diafygi/webcrypto-examples/

Now the problem I am facing is the signature produced by the API is different for the same private key and data, which should never be the case.

    var gprivateKeyobject = null;
var gpublicKeyobject = null;
var gsignature =null;

window.crypto.subtle.generateKey(
    {
        name: "ECDSA",
        namedCurve: "P-256",
    },
    true, //whether the key is extractable (i.e. can be used in exportKey)
    ["sign", "verify"] //can be any combination of "sign" and "verify"
)
.then(function(key){
    //returns a keypair object
    gprivateKeyobject = key.privateKey;
    gpublicKeyobject = key.publicKey;
    console.log('keys generated');
})
.catch(function(err){
    console.error(err);
});

var str = "hello test 1233";
var buf = new ArrayBuffer(str.length*2); // 2 bytes for each char
  var bufView = new Uint16Array(buf);
  for (var i=0, strLen=str.length; i < strLen; i++)
  {
    bufView[i] = str.charCodeAt(i);
  }
   console.log(bufView);

function sign()
{

window.crypto.subtle.sign(
    {
        name: "ECDSA",
        hash: {name: "SHA-256"}, //can be "SHA-1", "SHA-256", "SHA-384", or "SHA-512"
    },
    gprivateKeyobject, //from generateKey or importKey above
    bufView //ArrayBuffer of data you want to sign
)
.then(function(signature){
    //returns an ArrayBuffer containing the signature
    //console.log(bufView);
    console.log(signature);
    console.log(String.fromCharCode.apply(null, new Uint8Array(signature)));

})
.catch(function(err){
    console.error(err);
});

}

my console showing different signatures produced at consecutive calls to the function sign(which implies that private key and data to be signed must not have changed)

Now the problem I am facing is the signature produced by the API is
  different for the same private key and data, which should never be the
  case.

Actually in cryptography we don't require our signature schemes to be deterministic. It can even be harmful if you consider things like fault attacks (example attack PDF). Additionally you are using ECDSA which has only "recently" seen a deterministic variant in RFC 6979 and for which most standards (still?) mandate the non-deterministic variant (eg FIPS 186).

Additionally more often than not if you want to do something with deterministic signatures you are looking for a different primitive and probably should describe the problem and not the problem of "the" fix.

If you really don't want a deterministic signature scheme supported by the API you linked to, you can use RSASSA-PKCS1-v1_5 which is an older, still secure deterministic RSA-based signature scheme.


Is this attack for RSA possible? $N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively.

I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, m_x^d$.
Is it possible for me to factor $N$ or derive $d$ from the above knowledge?

My tentative answer is "no" because this problem seems to be similar to the problem mentioned in RSA Without Padding?. Therefore, my problem is also similar to the open problem 1 mentioned in Twenty Years of Attacks on the RSA Cryptosystem.

Therefore, I think it's practically impossible to recover $d$ or factor $N$, but I cannot come up with the solid proof. Can anyone help?

The original question states that we are given $e,m_1,{m_1}^e,{m_1}^d,\dots,{m_x}^e,{m_x}^d$, but not $N$; and asks for $d$ or a factorization of $N$.

I suspect some gremlin crept in this statement, because if any of the ${m_j}$ is such that ${m_j}>1$, it is trivial to obtain $d$ from ${m_j}$ and ${m_j}^d$, as $d=\log({m_j}^d)/\log(m_j)$.

So I guess we are given $e, m_1, {m_1}^e\bmod N,{m_1}^d\bmod N,\dots,{m_x},{m_x}^e\bmod N,{m_x}^d\bmod N$. If we are not given $N$, and for non-trivial choice of messages, we can find $N$ with overwhelming probability as $N=\gcd_{j=1}^x(({m_j}^e)-({m_j}^e\bmod N))$. With $N$ known, the givens ${m_1}^e\bmod N$ can be eliminated, for we can recompute them.

Thus the problems likely boils down to: given $N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N$, can we find $d$ or a factorization of $N$?

If the givens (beside $N$) allowed to efficiently factor $N$, that would solve Open Problem 1 in Dan Boneh's survey given as the question's second reference, which is nearly that problem (in addition, there is freedom to choose the $m_j$).

Thus no, we do not know how the givens (beside $N$, or the givens that let us find $N$) help in factoring $N$, but we do not know how to prove that they do not help significantly. That's an open problem!

We however can state one provable fact: if the $m_j$ are chosen at random, then knowledge of the ${m_j}^d\bmod N$ can not help. Proof sketch: any efficient algorithm factoring $N$ from $(N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N)$ with the $m_j$ chosen at random could be turned into an efficient algorithm that factors $N$ from $(N,e)$ alone, by choosing some $c_1,\dots,c_x$ at random and computing the $m_j={c_j}^e\bmod N$.

Some triva:

If we knew $d$, or any working private exponent $d'$, then we could factor $N$ using an efficient probabilistic algorithm.

If we knew the factorization of $N$, we could find the smallest working private exponent $d_0=e^{-1}\bmod\lambda(N)$, such that $d\equiv d_0\pmod{\lambda(n)}$. And if we further knew that $d=e^{-1}\bmod\phi(N)$ (rather than just some working private exponent), we could find $d$.


Is frequency analysis a viable attack on non-text data encoded by substitution? Is frequency analysis a viable attack on non-text data encoded by substitution (eg image and audio formats encoded with a substitution cipher)?

If one can prove that a large amount of image and audio data doesn't exhibit a frequency patter, only then can we consider frequency analysis as a non-viable attack.

For a modified simple example, let us say each guitar chord is encoded as a byte of audio data. If you analyse about 70+ songs, you will see that 4 chords are the most frequently used (as suggested by Axis of Awesome). Hence, a frequency analysis attack on each byte can be done for such musical data.

On an ending note, we humans are not good at generating data with uniformly distributed frequencies. So intuitively I feel that frequency analysis would be a possible attack for any data set somehow generated by humans (say playing a musical instrument). Is it computationally efficient? That is another question. But a formal prove and analysis of large data is needed either against or for this intuition to answer your question in a precise manner.


Historic Authentication Schemes Before Computers The Bulletin of the Atomic Scientists recently ran an article about an alleged near miss with rockets in 1962, which raises some
interesting cryptographic questions:

  After the usual time-check and weather update came the usual string of
  code.  Normally the first portion of the string did not match the
  numbers the crew had.  But on this occasion, the alphanumeric code
  matched, signaling that a special instruction was to follow.

  Bordne’s crew was instantly alarmed and, indeed, the second part,
  for the first time ever, also matched.

  At this point, the launch officer of Bordne's crew, Capt. William
  Bassett, had clearance, to open his pouch.  If the code in the pouch
  matched the third part of the code that had been radioed, the captain
  was instructed to  open an envelope in the pouch that contained
  targeting information and launch keys.

To me it is doubtful that this event ever happened, but it made me wonder how messages were authenticated in pre-computer days during the time of mechanical calculators and long before the advent of public key cryptography.

At this time, the standard was a codebook + superencryption and electromechanical rotor machines. In this case they probably used a code book. Neither scheme provides integrity or authentication.

CBC-MAC as one of the easiest MACs is (barely) feasible to do by hand and doesn't fit the description 'the code in the pouch matched the third part of the message'

Another issue with all of these schemes is that every potential recipient can trivially originate a fraudulent message himself.
There is nothing to keep a rogue crew from opening the secret pouch, constructing a message and sending it out to all other sites.
At that point, all of them will open their pouches, so the seal is useless to find the guilty after the fact.

How were message authentication and integrity handled during the time of codebooks and one time pads? Were there any schemes that provided any non-repudiation capability?

Edit:
I found an article that claims:

  When I served as a Minuteman launch officer in the 1970s, I and
  another crew member could have reverse engineered this entire business
  to create and transmit to the entire U.S. land- and sea-based
  strategic force a fully valid and authentic order that would have been
  carried out by crews whose only validation requirement was to match
  their SAS codes with the order’s SAS codes. (We didn’t use unlock
  codes at the time, even though Defense Secretary McNamara thought
  otherwise). The source of the message was irrelevant; all crews were
  trained to carry out any launch message that validated regardless of
  the source.

But, while somewhat morbidly fascinating, I don't want to dwell solely on the issue of nuclear authentication.
There is a huge body of literature about historical military encryption, but only very little about authentication and integrity. This is strange, because messages were transmitted in error prone Morse code via HF links.
I guess, the famous 'THE WORLD WONDERS' message during the battle of Leyte Gulf shows that at least the Navy did not verify message integrity.

As explained by Cort Ammon, they mostly relied on physical, rather than mathematical processes.

Here is a video on Youtube titled "How to launch a nuclear missile", taken in the Titan Missile Museum mentioned by Cort Ammon.

The message contains a seven character string.
The personnel in the shelter have a set of envelopes with the first two letters on the outside.
If the inside of the envelope matches the message, they launch.

Here is another one from a British sub, starting at 23:00. Decryption is done behind a curtain.

It is all very manual, no computer is visible.
Note the wooden club used to protect the codes (24:17).


Can XEX or XTS modes be used with only one tweak? XEX Mode (with two tweaks) is the following scheme:

$X = E_{k}(I) \otimes \alpha^j \\
C = E_{K}(P \oplus X) \oplus X$

where $I$ and $j$ are both tweaks (sector number and block number respectively).  If I wanted to use only one tweak, $I$, is the following correct and safe?

$X = E_{k}(I) \\
C = E_{K}(P \oplus X) \oplus X$

Essentially $j$ is treated as $0$, which I believe eliminates it from the equation.

To clarify what I mean by "safe"; does the second scheme I show have the same security guarantees that the first scheme has, as outlined in Rogaway's paper?  I skimmed the paper, but remain unclear as to whether the second scheme is included in the XEX family as Rogaway defined it.

No, using XEX mode with $j = 0$ is not entirely safe.  As noted in section 6 of the Rogaway (2004) paper (emphasis mine):

  "Some added care is needed to address the security of XEX. Suppose, to be concrete, that we are looking at $\mathsf{XEX}[E,2^{\mathbf I}]$ and $\mathbf I=[0\mathop{..}2^{n-2}]$. Let the adversary ask a deciphering query with ciphertext $C=0^n$ and tweak $(0^n,0)$. If the adversary has a construction-based deciphering oracle then it will get a response of $M=\tilde D_K^{0^n}\,^0(0^n)=D_K(Δ)⊕Δ=D_K(\mathsf N)⊕\mathsf N=0^n⊕\mathsf N=\mathsf N$, where $\mathsf N = E_K(0^n) = Δ$. This allows the adversary to defeat the CCA-security. For example, enciphering $2M=2\mathsf N$ with a tweak of $(0^n,1)$ and enciphering $4M=4\mathsf N$ with a tweak of $(0^n,2)$ will give
  identical results (if the adversary has the construction-based enciphering oracle). Corresponding to this attack we exclude any tweak $(N,i_1,\dotsc,i_k)$ for which $(i_1,\dotsc,i_k)$ is a representative of $1$—that is, any tweak $(N,i_1,\dotsc,i_k)$ for which $α_1^{i_1} \dotsb α_k^{i_k} = 1$. In particular, this condition excludes any tweak $(N,0,\dotsc,0)$."

However, using $j = 1$ is safe, and, indeed, is explicitly used as an example of a valid tweak by Rogaway e.g. in section 3:

  "Tweaks that are not the increment of a prior tweak will also
  arise, and they will typically look like $(N,1,0\dotsc,0)$. Constructions should be reasonably efficient in dealing with such tweaks."

Also, in their comments on the XTS mode, Liskov and Minematsu confirm that, indeed, $j=0$ is a bad choice for XEX (emphasis original):

  "Note that $j = 0$ must be excluded, as $f(0, v) = v$ for any $v$, which implies $ρ = 1$. Moreover, if $j = 0$ was allowed, a simple attack based on this fact existed, as pointed out by [6] and [3]. Hence if XEX is used, one must be careful to avoid $j$ being $0$."

However (while generally criticizing the choice to use two keys for XTS), they also note that this requirement to avoid $j = 0$ only applies to the single-key XEX mode, and not to XTS, which uses separate keys for the tweak and encryption stages:

  "Note that XTS does not require to avoid $j = 0$, as the offset function of XTS needs not be $(ϵ,γ,ρ)$-uniform, but only be $ϵ$-AXU if it is combined with URP. This difference is significant in security, but has no impact on effectiveness for practical applications."


What is a size of mac_length and mac_key_length for TLS cipher suites HMAC using SHA384 and SHA512? i failed to find explicit definition of hash output size and mac_key_size for hmac based on SHA384 and SHA512.
RFC5246 specifies:

but defines only

Given that MD5 has a size of 128 bit (16 bytes), SHA-1 of 160 bits (20 bytes) and SHA256 of 256 bits (32 bytes) and that these numbers are exactly reflected in the mac_length and mac_key_size I would assume that these sizes reflect the output size of the hash used. This also matches the definition of the HMAC used in TLS where the last step is to apply the hash and use its full output as result. Similar the HMAC definition recommends the output length of the hash as the minimal (and also probably most suitable) key length.

With this in mind the size for SHA-384 will be 384 bits (48 bytes) and for SHA-512 512 bits (64 bytes).


Digital signatures as a building block? I was reading Bruce Schneier's book Applied Cryptography, and he makes a comment about Digital Signatures, that they can be used as a building block for more advanced protocols.

What are examples of things that use digital signatures as a building block?

Key distribution protocols, PKIs, document authentication, general authentication and/or identification protocols, times tamping protocols...


Reduction of decison SIS In Lyu12, Lemma 3.6 is as follows.

Lemma 3.6     For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the  $SIS_{q, n, m, d}$ decsion problem to the $SIS_{q, n, m, (2\alpha+1)d+\alpha}$ decision problem.

Proof. To prove the lemma, we will show a transformation that maps the  $SIS_{q, n, m, d}$ distribution to the $SIS_{q, n, m, (2\alpha+1)d+\alpha}$ distribution, and maps the uniform distribution over $\mathbb{Z}^{n\times m}_{q}\times \mathbb{Z}^{n}_{q}$ to itself. Given $(A, t)$, create a random vector $r \stackrel{\$}{\leftarrow} \{-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, \alpha \}^{m}$ and output $(A, (2\alpha+1)t+Ar)$. First observe that because $2\alpha+1$ is relatively prime to $q$, our transformation maps the uniform distribution to itself. And if $(A, t)$ canme form the  $SIS_{q, n, m, d}$ distribution, then  $(2\alpha+1)t+Ar=A((2\alpha+1)S+r)$, and since $s$ was chosen from the uniformly at random from $\{-d, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, d \}^{m}$, it's not hard to see that $(2\alpha+1)S+r)$ is uniformly random in $\{-(2\alpha+1)d-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, (2\alpha+1)d+\alpha \}^{m}$.

I don't know the role of $gcd(2\alpha+1, q)=1$ in  the proof. Why not create an problem $SIS_{q, n, m, d+\alpha}$ and reduces  $SIS_{q, n, m, d}$ decsion problem to the $SIS_{q, n, m, d+\alpha}$ decision problem?

The assumption about gcd tell you that $2\alpha +1$ cannot belong to an ideal of $\mathbb{Z}/q\mathbb{Z}$. For example,  $2\alpha +1$ could divide $q$ and then $(2\alpha+1)t$ is never going to look like a uniformly random vector in $\mathbb{Z}_q^n$. If you want to fix ideas, assume $3$ divides $q$ and $\alpha =1$: then $(2\alpha+1)t$ always has its entries a multiple of $3$, which is absolutely not what a uniform vector would look like. The added contribution of $Ar$ may not be enough to "blur" the entries to a more uniformly random vector: it is likely that you could observe too many instances where $(2\alpha+1)t+Ar$ has entries a multiple of $3$.

In general, having this assumption make the proof easier (it might even not be possible to have a general proof without it) and relax the care on $\alpha$. It is also not very restrictive.


Secret sharing over reals - Difficulty with Computer implementation I asked a question recently regarding the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz which describes a secret sharing scheme for real numbers in the interval $[0,1]$. I got a fantastic answer as to how to construct a $(k,n)$-scheme.

However, I am struggling to implement the recommended scheme for a general case - I would like to believe there is an algorithm to do this; however, I was unable to do so. Below is a summary of where I am stuck -

For the case $(k,n) = (3,5)$, I used a "2-space diagonal assignment" technique which I have described below:

We have 10 independent $(3,3)$ schemes to construct denoted by
$$r_{j,1}, r_{j,2}, S - r_{j,1} - r_{j,2} \pmod 1 \;\;\forall j \in \{1,\ldots,10\}$$

let $r_{j,3}$ denotes $S - r_{j,1} - r_{j,2} \pmod 1$

My assignments were as follows;

$1 \rightarrow (r_{1,1},r_{2,2},r_{3,3},r_{6,1}, r_{7,2} ,r_{8,3} $)
$2 \rightarrow (r_{2,1},r_{3,2},r_{4,3},r_{7,1}, r_{8,2} ,r_{9,3} $)
$3 \rightarrow (r_{3,1},r_{4,2},r_{5,3},r_{8,1}, r_{9,2} ,r_{10,3}$)
$4 \rightarrow (r_{4,1},r_{5,2},r_{6,3},r_{9,1}, r_{10,2},r_{1,3} $)
$5 \rightarrow (r_{5,1},r_{6,2},r_{7,3},r_{10,1},r_{1,2} ,r_{2,3} $)

I hypothesized that this assignment technique which appears correct is either re-usable for other (k,n) schemes or depends on the difference (n-k).

I tried the both a 2 and 3- space diagonal assignment for a $(3,6)$ scheme..

However, I was unable to work out an assignment technique for the said (and general) case.

Would appreciate any help in finding a general assignment to progress further with my investigation into this scheme. Thanks in advance.

Recall the definition of a $(k,n)$-threshold secret sharing scheme is that any group of at least $k$ players (out of $n$ total players) can recover the secret given their shares.  The naive method for constructing a threshold scheme out of a non-threshold scheme (which was recommended in your previous question's answer) is giving every possible $k$-combination of the $n$ players a fresh $(k,k)$ sharing of the secret.  (I'll note that this is only practical for small values of $n$.)

It seems that you are stuck on the question of how to enumerate all of the possible combinations.  A good reference is this comprehensive answer on Stack Overflow, which mentions several algorithms.

Here is a quick Python script that will calculate all of the combinations for $k=3, n=5$:

import itertools

players = {1, 2, 3, 4, 5}
k = 3
for subset in itertools.combinations(players, k):
    print(subset)

With the resultant subsets:

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

This is of course a general algorithm that will work for any values of $k$ and any set of players.


Questions regarding parallel AES CTR with merkle trees I'm planning to implement a parallelizable variant of AES to end-to-end-encrypt files in a web application.

As a mode of operation I'm most likely gonna use CTR mode with a 64 bit IV and 64 bit counter, since that allows for easy parallelization.

Now it would also be great to be able to verify that the message wasn't manipulated, so I have to hash it somehow. However, most "normal" hash methods don't work in parallel, which is why I want to use a merkle tree.

From my understanding, it should be possible to encrypt, decrypt and verify the data completely in parallel, is that true?

In addition to that, I've seen that a lot of hashing methods (like GCM) verify the length of the ciphertext. Is that necessary with a merkle tree? I'd assume that the way such a tree builds the hash, it would be really hard to manipulate the length.

Also, should I hash the plaintext or ciphertext? and how should I encrypt the hash value?

Note: I'd like to avoid GCM, since it performs quite poorly on some devices I have to support.

Since it's a bad habit to answer questions in comments, I'll take my comments, and put them as an answer.

First off, you appear to be looking at designing your own homebrew method to do parallelizable MACing; don't do it.  There are too many ways to get it wrong, and you don't know what to avoid.

However, since you asked specific questions, I'll try to answer them:

  From my understanding, it should be possible to encrypt, decrypt and verify the data completely in parallel, is that true?

Obviously, yes, for example, with GCM.  You said that GCM doesn't work for you; it still is a proof of concept that parallelization is possible.

  In addition to that, I've seen that a lot of hashing methods (like GCM) verify the length of the ciphertext. Is that necessary with a merkle tree?

Maybe; GCM includes the length so that you cannot come up with two different ciphertexts/AADs that map to the same GHASH polynomial; one way an attacker could do that (if you don't include the length) is just prepend a 0 block to the ciphertext; that doesn't change the polynomial evaluation at all, no matter what the internal $H$ is.

Does your Merkle tree construction require something similar?  Without knowing the details of your construction, it is literally impossible to say.

  Also, should I hash the plaintext or ciphertext? and how should I encrypt the hash value?

Again, without knowing the details of your scheme, I can't really say.

On the other hand, if you're interested in a parallelizable authenticated encryption mode which is not GCM, you might want to consider CWC; it was designed by people who know what they're doing.  It's similar to GCM internally (and actually predates it a bit), however it uses software-friendly operations internally (additions and multiplications modulo $2^{127}-1$), rather than the $GF(2^{128})$ multiplications in GCM.

That may work out better for you.


How can we evaluate a polynomials in a group instead of a field? (verifiable secret sharing on elliptic curves) I am trying to understand how we can have cryptographic schemes that builds on both secret sharing, which is build on top of a finite field, and bilinear maps, which are built on top of elliptic curve groups.

An example of this is section 4 in Public Verifiability from Pairings in Secret Sharing Schemes, where publicly verifiable secret sharing is obtained with bilinear maps as proofs of correctness.
The relevant part of the scheme for the question is:

Setup: $q$ is a prime and $h$ generates a group $G$ of order $q$. Each participant publishes the public key $h_i = h^{d_i}$, where $d_i$ is a random number in $F^*_q$.
Distribution: the dealer chooses a random polynomial of degree $t -1$ with coefficients, $\alpha_j$ in $F_q$: $P(x) = \sum^{t-1}_{j=0} \alpha_j x^j$ and publishes the encrypted shares: $Y_i = h_i^{P(i)}$.

and publishes commitments to the coefficients $C_j = g^{\alpha_j}$.
Verification: A step in the verification process involves calculating $X_i = \prod_{j=0}^{t-1} {C_j^{i}}^j = g^{ \sum^{t-1}_{j=0} \alpha_j i^j}$ and then evaluating whether the bilinear equation $e(X_i,h_i) = e(g,Y_i)$ holds.

The question then is:

How is this possible? The use of bilinear maps implies using elliptic curves groups, while calculating $X_i$ involves both addition, multiplication and exponentiation, i.e. it requires a field. But since we have transitioned to the group of curve points when we calculated $Y_i$ and $C_j$ we will have lost the multiplicative and exponentiation operations, right? What am I missing here?

It is correct to me. Polynomial is not evaluated in the elliptic curve group $G$, but in $F_q$ (where $q$ is the order of $G$), which is a field because $q$ is a prime number.

To be clearer, I add brackets to the equation you gave: $$X_i = \prod_{j=0}^{t-1} (C_j)^{{i}^j} = \prod_{j=0}^{t-1} (g^{\alpha_j})^{ i^j}= (g)^{ \sum^{t-1}_{j=0} \alpha_j i^j}$$ You can see the polynomial is evaluated in the exponent, that why it is in $F_q$.

Maybe it is easier to see if using the Elliptic curve notation (let $P$ be a generator of the EC group $G$, i.e. $g$ in the above equation):

$$X_i = \sum_{j=0}^{t-1} ({i}^j\cdot C_j) = \sum_{j=0}^{t-1} ({i}^j\cdot a_j\cdot P)= (\sum_{j=0}^{t-1} a_j\cdot {i}^j )\cdot P$$


Are PQ/Classical Hybrid Key Exchanges a reflection of how little we trust PQ cryptography primitives? My students have asked me some questions about why there are standards being developed for hybrid public key systems with both a classical and a post-quantum component.

Given that when elliptic curve cryptography was first being deployed no one suggested using elliptic curve cryptography with classical RSA or Diffie-Hellman in a hybrid scheme; when SHA-3 was standardized no one suggested making a hybrid of SHA-3 and SHA-2; and when AES was invented no one suggested using it in a hybrid with Triple DES or some other cipher--is the desire for PQ hybrids a reflection of the distrust we have in the fundamental primitives that underly our post-quantum schemes?

If we do trust these primitives, why the need for a hybrid?

Actually, we do trust many (but obviously not all) post-quantum cryptosystems more than traditional schemes. We haven't been using them because they fail to meet practical space and time trade-offs.

  When elliptic curve cryptography was first being deployed no one was suggesting using elliptic curve cryptography with classical RSA or Diffie-Hellman in a hybrid scheme.

A hybrid solution would defeat the primary motivation of switching to ECC; faster, smaller and more secure. PQ schemes may be faster xor smaller, but our interest is in their increased security.

  When SHA-3 was standardized no one suggested making a hybrid of SHA-3 and SHA-2. When AES was invented no one suggested using it in a hybrid with Triple DES or some other cipher.

Many applications use multiple hash functions either for cross version compatibility or increased collision resistance. I.e. MD5, SHA1, and SHA256 checksums for source or package distribution.

  Is the desire for PQ hybrids a reflection of the distrust we have in the fundamental primitives that underlay our post quantum schemes?

The primary applications for PQ where hybrids are desired involve forward secrecy in key exchanges. If we must spend the time and bandwidth for a PQ scheme, then using ECC in addition to this is almost negligible.

  If we do trust these primitives why the need for a hybrid?

If I audit a piece of software and I know it uses a hybrid scheme and I understand and trust one of its components, such as ECC, then I may be satisfied without having to learn about the particular PQ scheme in use. If an assumption in the PQ scheme is incorrect, I know the protocol is at least as secure as the traditional scheme.


Should I use the first or last bits from a SHA-256 hash? I have the need for a hexadecimal token that is smaller than the normal length of the hexadecimal representation of a SHA-256 hash.

Should I take the first bits or the last bits? Which of them contain the most entropy?

If taking the first or last bits of a SHA-256 output made any difference, it would be viewed as a serious blow against the security of SHA-256. Right now, no such weakness is known in SHA-256. So, as far as we know, you can use whatever bits you want.

If you need a more "administrative" answer, have a look at SHA-224 (also specified in FIPS 180-3). This is a hash function with a 224-bit output, which NIST defined in order to "match" (administratively speaking) the proclaimed 112-bit security of 3DES. They defined SHA-224 by taking SHA-256, changing the conventional IV, and truncating the output. For the truncation, they took the first 224 bits. If it is good for NIST then it is good for you: take the first bits.


Can blocks in AES-CBC ciphertext be manipulated in such a way that plaintext becomes shuffled? Say we have a sequence of N 16-byte plaintext blocks encrypted using AES in CBC mode, with an IV, resulting in N+1 16-byte ciphertext blocks. Can this ciphertext be manipulated in such a way that, once decrypted, the plain text would become shuffled (i.e. some of its N blocks become reordered), but with no other modifications otherwise?

Since each block depends on the previous one, if we just shuffle ciphertext blocks, some resulting plaintext blocks may become reordered, but at the cost of others being changed completely. One can also remove some M first blocks of ciphertext, which would make M first blocks of the plaintext disappear as well, but I see no way to append those ciphertext blocks to the end of the message to decrypt properly. Does there exist some other ciphertext manipulation which would result in reordering the plaintext blocks once decrypted, but with no other change otherwise?

It does not seem like this is possible. Consider the simple case where a 2 block (32 byte) plaintext message has been encrypted using AES-CBC with key $k$ and initialization vector $IV$. Let the plaintext blocks be referenced as $P_1$ and $P_2$, and let the corresponding ciphertext blocks be referenced as $C_1$ and $C_2$. In this case, knowing that $\text{AES.encrypt}(k, P_1 || P_2) = C_1 || C_2$ and that $\text{AES.decrypt}(k, C_1 || C_2) = P_1 || P_2$, you are trying to find out whether $\text{AES.decrypt}(k, f(C_1) || f(C_2))$ can possibly equal $P_2 || P_1$, where $f$ is some manipulating function applied to the ciphertext.

From the regular CBC decryption of $(C_1 || C_2)$ into $(P_1 || P_2)$, we are guaranteed the following relationships:

$\text{AES.decrypt}(k, C_2) \oplus C_1 = P_2$

$\text{AES.decrypt}(k, C_1) \oplus IV = P_1$

In order for $(f(C_1) || f(C_2))$ to decrypt into $(P_2 || P_1)$, the following relationships must be true:

$\text{AES.decrypt}(k, f(C_2)) \oplus f(C_1) = P1$

$\text{AES.decrypt}(k, f(C_1)) \oplus IV = P_2$

And then, by substitution, the following must also be true:

$\text{AES.decrypt}(k, f(C_2)) \oplus f(C_1) = \text{AES.decrypt}(k, C_1) \oplus IV$

$\text{AES.decrypt}(k, f(C_1)) \oplus IV = \text{AES.decrypt}(k, C_2) \oplus C_1$

In order for the first equation to be true, $f(C_2)$ must equal $C_1$ and $f(C_1)$ must equal $IV$, and in order for the second to be true as well, $f(C_1)$ must equal $C_2$ and $IV$ must equal $C_1$, giving us the following:

$f(C_2) = C_1$

$f(C_1) = C_2$

$f(C_1) = IV$

$C_1 = IV$

$f(C_1) = C_1 \rightarrow C_1 = C_2$

So the only way that you can manipulate blocks in the 32-byte AES-CBC output to decrypt to rearranged blocks of the original plaintext is if the output blocks $C_1$ and $C_2$ are identical. Clearly if this was the case, the corresponding input blocks would also be identical, and there would be no point for a malicious actor to rearrange them in the first place.


Which stream cipher can we replace the RC4 in the SSL? In cryptography, the Fluhrer, Mantin and Shamir attack is a particular stream cipher attack, a dedicated form of cryptanalysis for attacking the widely-used stream cipher RC4. The attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream.
  The Fluhrer, Mantin and Shamir attack applies to specific key derivation methods, but does not apply to RC4-based SSL (TLS), since SSL generates the encryption keys it uses for RC4 by hashing, meaning that different SSL sessions have unrelated keys.

From here. Does it mean that RC4 is not so secure as we want? And which stream cipher can we replace the RC4 in the SSL?

There are several ways to answer your question:

You cannot "replace" RC4 in SSL. SSL is a standard protocol in which any algorithm may be used only if both client and server support it and agree to use it. Thus, in practice, you do not get to replace algorithms as you wish, unless you control both client and server code; and even then, it would not longer be "the standard SSL (actually known as TLS)" but a custom variant.
If we want to define a TLS variant, then we can define new cipher suites which use a stream cipher distinct from RC4. There are some good candidates for the job, in particular the eSTREAM portfolio: these algorithms did get a fair share of analysis, and "seem strong". There is no known detectable bias in them, contrary to RC4. They also happen to be substantially faster.
Standard TLS now defines cipher suites with GCM. GCM is a block cipher mode of operation which builds on a block cipher with 128-bit blocks (usually AES); the block cipher is used in CTR mode, which actually turns it into a stream cipher. So we can say that using GCM-based cipher suites really is replacing RC4 with another "stream cipher".

Note that SSL/TLS ensures not only confidentiality but also integrity; thus, there must be a MAC somewhere. When using RC4 for the stream cipher, the MAC is HMAC with a hash function (MD5 or SHA-1). If you replace RC4 with a super-fast stream cipher which does only encryption, then the HMAC may become the bottleneck. GCM uses the block cipher for both encryption and the MAC, so a fast block cipher actually speeds up the whole thing. On modern x86 processors, there is hardware support for AES which includes an opcode specially suited for GCM. On smaller architectures, where performance issues are actually much more probable to matter, GCM is not necessarily a good choice ("fast" implementations of the binary field multiplication in GCM use big tables which are not that fast on CPU with a small L1 cache).


Piggyback on Bitcoin for independent data verification? The recent threats to EPA data integrity have me wondering if it's possible to archive data in a way such that one can later check whether the data have been tampered with since the original archival.

One commonly used mechanism in the open source software world is hash verification. After downloading some software you compute an md5hash of the tarball and then compare that hash to a "golden" hash served by a trusted website. Of course, you trust the website because its certificate checks out with whichever certificate authorities you trust.

But if that trusted website is centrally managed by some stakeholder in the data, then the golden hash is suspect. It seems like there ought to be some kind of P2P or distributed record system that can be used for this. What I thought of was blockchain technologies such as bitcoin. Getting to critical mass with a new blockchain system built for the sole purpose of data tampering detection seems like it would not be feasible because there would be little incentive to actually join that system.

It seems like it might be easier to somehow piggyback on the existing Bitcoin system. I feel reasonably confident in saying that the Bitcoin system is unlikely to disappear any time in the near future.

Is it possible to store even tiny amounts of user data--such as a few md5hashes--in the Bitcoin blockchain?

I think what you might be looking for is an append-only data structure for example "Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure". A similar concept is used for certificate transparency as specified in RFC6962

Edit: If you definitely want to use the bitcoin blockchain you should look at this or this.
Somebody actually has asked this question before.
A PoC implementation can be found here.


hash collision chance using a 5 chars hash made of a-z A-Z and 0-9 (62 chars total) What is the chance for collision or resistance of a hash made out of 5 chars randomly picked from this sets a-z A-Z and 0-9 (62 chars total).

Also, what is total amount of combinations without collision that I can get, AFAIK :

$62^5 = 916.132.832$

Thank you.

There are indeed $62^5 = 916\,132\,832$ possible hashes in that syntax.  If they are uniformly distributed, then the standard birthday paradox applies to the probability of a collision in $n$ independent choices of $k$ possible hashes.  For $n < \sqrt{k}/4$, the probability of collision is between $(n - 1)^2/(4k)$ and $n^2/k$.  For example, among 10 000 hashes, the probability of a collision is at least $$\frac{9\,999^2}{4\cdot916\,132\,832} > 2.7\%,$$ and at most $$\frac{10\,000^2}{916\,132\,832} < 11\%.$$

Of course, if these are hashes from a fixed public hash function like SHAKE128-30 (add two more characters to your alphabet like the base64 + and - to make the numbers work out), it is easy for an adversary to spend the energy to compute a few tens of thousands of hashes offline without interacting with you in order to find a collision with high probability.  The lower bound on the collision probability gives a guarantee on the adversary's chance of success after a certain amount of work.

So with numbers as small as this, not much can be said about fixed public hash functions.  On the other hand, this analysis remains relevant for a secret hash function, a pseudorandom function family (PRF), like SipHash or KMAC128 or keyed BLAKE2 under a secret key not known to the adversary.


How is this affine function a pair wise independent permutation? Can anybody explain how the below is true ?

  $I_n$ denotes the set of all n-bit strings, ${\{0,1\}}^n$.
  (..)
  Let $A$ be a finite field then the permutation $f_{(a,b)}(x) = a \cdot x + b$,
  where $a \ne 0; b \in A$ are uniformly distributed, is pair-wise independent. Thus, there are pair-wise independent permutations over $I_n$ (the permutations $f_{(a,b)}$ with operations over $GF(2^n)$ ).

This is stated in section 2.3 of the below paper, the context is that they use pair wise independent permutation in first and last rounds of Feistel network to get better security guarantees. But they do not mention why the above is true.

[1] Moni Naor and Omer Reingold, "On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited", in Journal of Cryptology January 1999, Volume 12, Issue 1, pp 29-66.

Addition: The question's quote (at least: also) appears in an apparently earlier version of the paper, made available by the first author (pdf).

By definition, a distribution $F$ of permutations over $A$ is pair-wise independent if for all distinct members $x_1, x_2$ of $A$, the following two distributions are identical:

$\langle f(x_1),f(x_2)\rangle$ where $f$ is distributed according to $F$;
The uniform distribution over sequences of two different elements of $A$.

A family of functions F is a pairwise independent permutation if:

Each member of the family is itself a permutation, and
For any fixed $A$, $B$ (with $A \ne B$, and both from the input set of the permutation), and $f$ is a random member from the family $F$, then the pair $f(A), f(B)$ is equidistributed over all distinct pairs from the output range of the function.

In particular, if the size of the output range $2^n$, then for any $C \neq D$, then the probability that both $f(A) = C$ and $f(B) = D$ is $(2^{2n} - 2^n)^{-1}$

By applying the above definition, it is easy to see that the function family $f_{(a,b)}$ meets it; each $f_{(a,b)}$ is a permutation (remember, $a=0$ is prohibited), and if $f$ is a random member of that family, then $f(A), f(B)$ is a equistributed distinct pair; that is, given any pair $C \ne D$, then there is a unique $a$, $b$ with $a\ne 0$ such that $f_{(a,b})(A) = C$ and $f_{(a,b)}(B) = D$.  Each such pair $a, b$ occurs with probability $(2^{2n} - 2^n)^{-1}$, and so we have $f(A) = C$ and $f(B) = D$ holding simultaneously with that same probability.


Computing inverse of BN256 G2 point in golang x/crypto/bn256 library I'm trying to confirm a vulnerability in a signing scheme I'm helping with. To do this I need to simulate a rogue key attack on a BLS aggregate signature using the golang bn256 library https://godoc.org/golang.org/x/crypto/bn256 This requires computing the inverse of a public key.

I'm not a crypto expert but do have a fairly strong algebra background... So if g is the generator of order n then the inverse of p is just p^(n-1) right? But I have no idea what n is.

Any help would be greatly appreciated

Actually, computing an inverse of a point (that is, the inverse of X is the point Y such that X+Y is the identity) is quite easy.

For a curve in Weierstrass format with characteristic > 3 (which bn256 is), the inverse of the point (x, y) is the point (x, -y).  That is, you compute the negation of the y coordinate (which, in this case, is modulo $p$ the characteristic of the curve, as it's a prime curve).

BTW: you stated that you "don't have the time right now ... to learn the basics"; if you want to do anything with Elliptic Curves, I would suggest you take the time (the basics shouldn't take several semesters...)


While using onetime encryption is it possible that one can deduce the key of a message if the contents of the message are already known? Let's say we have a randomly encrypted message and I pasted the contents of that message on a blog for some reason I do not share the key.

Would you be able to figure out the key?

This is the message not encrypted:

This is the message.

This is the encrypted message:

 -----BEGIN OneTime MESSAGE-----

Version: OneTime 1.122

Pad ID: b1255b5389588da3c0e00b87213afb6bd79a0bbb

Offset: 0

QlpoOTFBWSZTWUyTjxYAAAJ+gAgCA4FKYABwSAEoAQAQIAAigA0xMEKBpoZGTEHGQdDBjUXXyo7R
HxdyRThQkEyTjxY=

-----END OneTime MESSAGE-----

The package will not let you use keys twice. Its protocol follows this rule especially for communicating to two computers over telnet, nc, ssh, etc. The protocol can be found here in this link https://www.red-bean.com/onetime/ .

Knowing the plaintext and ciphertext will allow you to recover (a portion of) the key.

The OneTime package referenced in the comments implements a simple one-time pad.  Because the plaintext and ciphertext are related by a simple XOR it is trivial to calculate the portion of the one-time pad that is used for that message.  If all of the rules for using a one-time pad are followed (e.g. no re-use, truly independent random values for each bit, etc), then that portion of the key can be calculated, but it wouldn't provide any value beyond what was already known.


Zero-knowledge proof for multiplication in the exponent We have $c_1=g_1^x$, $c_2=g_2^y$ and $c_3=g_3^{x/y}$, where $g_1,g_2,g_3$ are generator of a group of order $n$ and we don't know the DL between them. Is there any sigma protocol or zkp that can prove the language $L=\{c_1,c_2,c_3\mid \exists\, x,y, \text{ such that } c_1=g_1^x \ \& \  c_2=g_2^y \ \& \  c_3=g_3^{x/y} \}$?

If the generators were the same, then this would be a standard Diffie-Hellman tuple sigma protocol. In order to see this, note that a Diffie-Hellman tuple is defined to be $(c_1,c_2,c_3)$ such that $c_1 = g^a$, $c_2 = g^b$ and $c_3 = g^{ab}$. Setting $a=y$ and $b = x/y$, we have that $ab = x$. Thus, all you need to prove is that $(c_2,c_3,c_1)$ is a Diffie-Hellman tuple.
However, given that they are not the same, the above isn't correct. The first thing to notice about this language with different generators is that it is actually trivial. That is, it is always possible to solve and find $x,y$ that fulfil the equations. Thus, such a proof would only be interesting as a proof of knowledge (as such, one should refer to the relation and not the language, and $g_1,g_2,g_3$ must of course be part of the public statement).
Beyond that, I don't think it's trivial. I have played around a bit for a few minutes and the naive things one could do won't work. However, from experience, sigma protocols typically aren't that hard to build, and this looks like something that should work. But it may be hard and require research. I am leaving this partial answer here, even though it isn't correct, in order to be of some help regarding finding the direction.


What would be an adversary advantage in case of GCM authentication? Philip Rogaway has written a formula for CCM mode where the adversary advantage is given as:
$$adversary\_advantage \leq \frac{q_{dec}}{2^t} + \frac{\sigma^2}{2^b}$$

Can we use this formula to find GCM data integrity? Is there a similar document for GCM mode?

Can we use this formula to find GCM data integrity?

No. This bound only holds for CCM and can not easily be transferred to other modes as it depends on the security proof which is different for each mode.

  Is there a similar document for GCM mode?

"Breaking and Repairing GCM Security Proofs" by Iwata, Ohashi and Minematsu (2012) has the current security proof for GCM. In section 7 you will find the various security bounds. As you specifically asked for the authenticity bound (Theorem 2) here it is:

$$\mathbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm}(n),\tau]}\leq \frac{(\sigma+q+q'+1)^2}{2^{n+1}}+\frac{(q+q'+1)(\sigma+q)(l_N+1)}{2^{n-22}}+\frac{q'(l_A+1)}{2^\tau}$$

where

$\tau$ is the length of the authentication tag in bits.
$n$ is the block size of the permutation in bits, e.g. 128 for AES.
$q$ is an upper bound for the number of answered encryption queries.
$q'$ is an upper bound for the number of answered decryption queries.
$\sigma$ is the total number of plaintext blocks (ie associated data blocks are not included and only encryption queries are considered).
$l_N$ is an upper bound for the nonce-length in blocks.
$l_A$ is an upper bound for the input length in blocks which includes associated data and plaintext (for decryption queries replace "plaintext" with "ciphertext")

If these variable descriptions are "too vague" for you, the start of section 7.3 has them as more formal definitions.


Is use of pre-shared key for sharing session key in symmetric key cryptography vulnerable to MITM? Consider the following protocol:

Alice                    ------------------------> R1     Bob
Alice        k(R1),R2    <-----------------------         Bob
Alice                     ------------------------> k(R2) Bob
Alice         k(S)       <------------------------        Bob

Where

k is pre-shared key, known only to Alice and Bob;
k(x) is the encryption of x under key k
R1 is a random number generated by Alice;
R2 is a random number generated by Bob;
S is the session key, generated by Bob.

Is this protocol susceptible to MITM? If yes, then how?

An obvious, but not serious weakness, is that numbers R1 and R2 will be sent in plain text. This means that MITM is able to modify R1 or R2 so that Alice or Bob will always fail at authentication, although they have a legal key K.

I have one suggestion how you can improve this protocol. Just because in the last step of the protocol, Bob only sends encrypted S, MITM can wait while previous steps will be completed successfully, and then send some old message K(S_old), where S_old is an old session key, which was compromised. To avoid such danger, add number R2 to Bob’s last response K(S,R2).


Any speed up methods for finding the index of a random value produced by the Inversive congruential generator? The Inversive congruential generator produces random values with:
$$x_{n+1} = a\cdot x_{n}^{-1} + b \mod P$$

(special case if $x_n=0$ -> $x_{n+1}=b$)
starting with an initial value $x_0$

With well choosen $a,b,P$ it produces all values in $\mathbb{F}_P $ (which are $[0..P-1]$)
That's the case if there is no r with $r^2 \equiv 4 a + b^2 \mod P$ with $P$ a prime.

Question: Is there any way to compute the index $n$ for a given value $v \in \mathbb{F}_P$ with $x_n=v$ ? (with $a,b,P$ well chosen and known)
Or is there any way to compute it faster than brute force?

For the $n$'th random value a equation exists with:
$$x_n=(q_{n+1}\cdot  x_0 + a\cdot q_n)(q_{n}\cdot  x_0 + a\cdot  q_{n-1})^{-1} \mod P$$
with $q$ a sequence again:
$$q_0=0$$
$$q_1=1$$
$$q_{n}=a\cdot q_{n-2}+b\cdot q_{n-1} (\mod P)$$

q is similar to the Fibonacci sequence. Without modulo there is an equation for the $n$'th element as well:
$$q_n=  \frac{ (\frac{b +\sqrt{4 a + b^2} }{2})^n - (\frac{b - \sqrt{4 a + b^2}}{2})^n}{\sqrt{4 a + b^2}}$$
(I don't know if there also exists a form modulo $P$)

Update:  $q_n$ equation modulo P
with:
$r^2 \equiv 4 \cdot a+b^2 \mod P$
$1 \equiv t \cdot 2 \mod P$

$$q_n = ((b+r)^n-(b-r)^n)\cdot t^n \cdot r^{-1} \mod P$$
This equation also works in $\mathbb{F}_P$

However for the target values $a,b$ there exists no such root $r$.
  (For other $a,b$ which can not produce all values it does work)

Update 2: simplification
For simplification we can assume $x_0=0$.  With this the equation for $x_n$ would be:
$$x_n=(a\cdot q_n)(a\cdot  q_{n-1})^{-1} \mod P$$
$$x_n=q_n\cdot  q_{n-1}^{-1} \mod P$$

Any way to compute index $n$ for given value $v=x_n$?

Update 3: some test in wolframalpa
wolfram alpha has a solution for the non-modulo version (with $x0=0$):
https://www.wolframalpha.com/input/?i=solve+(((b%2Br)%2F2)^n-((b-r)%2F2)^n)%2F(((b%2Br)%2F2)^(n-1)-((b-r)%2F2)^(n-1))%3Dv+for+n?

$$n = \frac{  \log(\frac{(b - r) (b + r - 2 v)} {(b + r) (b - r - 2 v)}) + 2 i \pi c_1}{\log(b - r) - \log(b + r)} $$

Using this I get a complex number for $n$ with real and imaginary part $\not\in \mathbb{N}$. If I compute $x_n=q_n/q_{n-1}$ and with this $v$ in $\mathbb{R}$ for an example it does work.
Any idea how to transform this to $\mod P$ (for values $a,b$ which don't have a root $r$)?
Or how to transform a $v\in \mathbb{F}_P$ to $\mathbb{R}$?

Update 4: Get rid of $r$ in $q_n$ equation
$q_n$ can be multiplied at top and bottom with $r$ to get $r^2$ only. With $x0=0$ the equation for $x_n$ would be (for $n>2$):
$$x_n=q_n q_{n-1}^{-1}= \frac{2 \cdot \sum_{k=1}^{\lfloor n/2\rfloor}   {n-1\choose 2k-1}  b^{n-2k}(r^2)^{k} }{4\cdot \sum_{k=1}^{\lfloor (n-1)/2 \rfloor} {n-2  \choose 2k- 1} b^{n-2k-1} (r^2)^{k } } \mod P$$

The lower part need to be the inverse and not a divisor for $\mod P$.
  However I don't see any way to extract a formula for $n$ out of this. Do I miss something?

(too long for a comment)

You can calculate $x_n$ directly by your formulas, if you know, how to calculate in a quadratic extension field of a prime field $\mathbb{F}_p$.

Here is the code in python:

# global parameters
p = 65537
t = (p+1)/2
r = 313
s = 997

# from https://stackoverflow.com/a/9758173/99978
# modular inverse based on extended Euclidean algorithm
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
# for generating sequence x_n
def succ(x):
  return (r*modinv(x, p)+s) % p

# check that 4*r+s^2 does not have any root mod p
for i in range(t):
  if (i*i) % p == (4*r+s*s) % p:
    raise Exception('not irreducible')

# conjugate in field
def conj(x):
  a, b = x
  return [a, -b]
# subtraction in field
def minus(x, y):
  a, b = x
  c, d = y
  return [(a-c)%p, (b-d)%p]
# multiplication of a+bX with c+dX in field F_p/[X^2+4*r+s^2]
def mult(x, y):
  a, b = x
  c, d = y
  return [(a*c+b*d*(4*r+s*s)) % p, (a*d+b*c) % p]
# exponentiation in field
def exp(x, n):
  y = [1, 0]
  while n > 0:
    if n % 2 == 1:
      y = mult(y, x)
    x = mult(x, x)
    n = n/2
  return y
# inverse in field (same as exp(x, p*p-2))
def inv(x):
  a, b = mult(x, conj(x))
  if b != 0:
    raise Exception('error in inverse')
  return mult([modinv(a, p), 0], conj(x))
# your formula for q_n
def qn(n):
  x, y = mult(mult(minus(exp([s, 1], n), exp([s, -1], n)), exp([t, 0], n)), inv([0, 1]))
  return x
# your formula for x_n given q_n
def xn(x0, n):
  return ((qn(n+1)*x0+r*qn(n))*modinv(qn(n)*x0+r*qn(n-1), p)) % p

# a short test
x = 97
for i in range(500):
  x = succ(x)
  if xn(97, i+1) != x:
    raise Exception('wrong result')

Extending a prime field $\mathbb{F}_p$ ("prime fields" are the minimal fields, the finite ones are the fields of order $p$, the infinite one is $\mathbb{Q}$) by the square root of an element $z\in\mathbb{F}_p$ that does not have a root $\bmod p$ works the same way as extending the real numbers $\mathbb{R}$ to the complex numbers $\mathbb{C}$: Just invent an element $X$ whose square is $z$ (for $\mathbb{C}$ this is usually called $i$), and calculate with numbers of shape $a+bX$ using $X^2 = z$.

Formally correct this can be done by calculation in the polynomial ring $\mathbb{F_p}[X]$ modulo the polynomial $X^2-z$ or in code like you see it above.

You can slightly optimize the code by using the fact that conjugation (replacing $X$  by $-X$) is commutes with addition/multiplication/exponentiation in the field, but I doubt that you will be able to invert the function $n\mapsto x_n$.


plaintext and its encrypted version known I have a (long) text in two versions, encrypted and plaintext. I think it was encrypted using a substitution cipher method (I'm pretty sure, indeed).

I'm not good in this matter, I know little about it, but I would know if there's a way to know the function/secret used for encrypt that text.
I'm ready to study, anyway :)

If it is a long text and you are sure it is a substitution cipher there are a lot of statistical methods to find the key.
Statistical methods rely on the frequency at which alphabets occur in a language. Not just single alphabets but even pairs. For eg in the english alphabet 'E' is the most frequent alphabet followed by 'T' and 'A'. Also some characters such as 'CH' 'QU' 'TH' are found together frequently. All these results can be used to identify the key for the substitution cipher. The longer the text you have the easier it is to identify these patterns.
There are quite a few tools online that help you analyse these patterns.
Also as mentioned in another answer if you already have parts of the plain text too it is trivial to find the mapping of those characters.

Detailed explanation:
http://people.csail.mit.edu/hasinoff/pubs/hasinoff-quipster-2003.pdf

simple explanation:
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/