Is there a hash tree scheme designed for complex data structures? I have a JSON object with private data. It has the following (complex!) structure:

{
    name: "JB",
    age: 35,
    children:
        [ {
           name: "Alice",
           age: "5",
           favColor: "pink"
          },
          {
           name: "Bob",
           age: "8",
           favColor: "blue"
          },
          {
           name: "Charlie",
           age: "9",
           favColor: "green"
          },
       ]
}

I want to create a hash tree (or similar) that allows others to verify pieces of the data I send them - e.g. by declaring the root on public blockchain. The data structure is arbitrary - it could be anything.

For instance, I'd like to be able to share my age ONLY, and have the receiver be able to compute the hash and check that it is correct. Later, I may want to disclose to a different user that my first child is named "Alice" and her favorite color is "pink".

My understanding is that Merkle Trees are binary - each node has two leaves only - this seems to be the case in the npm libraries I’ve seen. Is there a fixed schema or method for 'flattening' complex structures like the one above into a merkle tree consistently?

Alternatively, is there another type of hash tree structure that provides this kind of complexity innately for data?

For example:

       Root ( = hash of name + age + children)
     /  |  \
    /   |   \
 name  age  children  (= hash of all children in array)
           /      | \
          /       |  \
         /        |   \
      [0]        [1]  [n]
     / | \
    /  |  \
 name age favC

It seems that however the tree is constructed, it is important that the original data's structure is somehow preserved and is can be scrutinised by the validator.

e.g. to prevent me from providing a child's age instead of my own.
In the case of a binary merkle tree: to account for the fact that a leaf index may represent entirely different data depending on the number of children they have.

What is the best way to approach this problem? I'm using Node.JS, and the neat Merkle Tools package, but I'm not sure the merkle tree is the right tool for the job.

Another way of phrasing this question is to ask: is there a hashing schema that allows us to consistently render an arbitrary Json object into a hash tree-like structure consistently? And which facilitates validation by sharing the data + the other hashes. Should I just combine a hash table with trees? Or a hash list with certain nodes being trees?

If I've missed anything important out, or you have any clarifying questions, I will do my best to improve the question. I have redirected the question here, on the advice of the S.O main site.

Many thanks.

The general technique for tree hashing (independently of the issue of partially revealing content) is to define the hash of nodes as the hash of the concatenation of the hash of their leaves, with a suffix (or prefix) that makes the input of the hash different for leaves and nodes. Demonstrably, this inherits from the cryptographic hash it's properties of collision-resistance, preimage-resistance, and security in the Random Oracle Model. Proof is left as an exercise to the reader.

The devil is in the details, in particular in

defining a canonical form of things that must have identical hashes;
defining if the order of leaves matters;
if nodes are typed or/and named beyond being a leaf or not (in which case that type/name extension must be hashed);
making sure that the format of the input of hashes used for such extensions can not lead to collision (perhaps deliberately).

I know no ready-made hash standard for JSON, aka ECMA-404. I hereby semi-seriously propose to pick a cryptographic hash such as SHA-512, and define SHA-512-JSON-V1 as:

The hash of a JSON array is the hash of the concatenation of the hash(es) of its value(s), ordered as they occur in the array; and a final octet 41h (ASCII A).
The hash of a JSON object is the hash of the concatenation of an even number of hashe(s), with the first hash of a pair the hash of the name of a member of the object, and the second the hash of the corresponding value, with the pair(s) ordered in lexicographic order of the concatenation of the two hashes of that pair; and a final octet 4Fh (ASCII O).
The hash of any other JSON value (that is string including a name, number, the special values true, false, null, and anything else not defined by ECMA-404) is the hash of the concatenation of their UTF8 character representation (excluding leading and ending " for strings that came with that, and with conversion to lowercase for the three special values); and a final octet

53h (ASCII S) for string including name
4Eh (ASCII N) for number
56h (ASCII V) for yet other value.

Notes on object:

Order of leaves never matters to the hash, since (quoting ECMA-404)

  JSON syntax (..) does not assign any significance to the ordering of name/value pairs

Case matters including in names. Doing otherwise would be a nightmare with unicode, unless we restricted case normalization to ASCII letters.
Multiple occurrences of the same name in the leaves of an object can be tolerated (as in ECMA-404), or not, without changing the hashing scheme.
Update per comment: the proposal orders the pairs of hashes (one per per name:value pair in an object) per the concatenation of the two hashes (one for name, the other for value). That ensures the hash result is identical regardless of the order of nodes. If we ordered per the hash of the name only, or per the name, this would not be insured for multiple occurrences of the same name in an object (which is possible, see above bullet). Further, ordering directly per what's hashed allows to substitute ordering with any order-independent hash, enabling a sizable optimization for large objects; see last section of this answer.

Notes on coding of value:

UTF8 has the advantage that it is compact, endian-neutral, and assigns each unicode point a single representation as octet string (including if it has no UTF-16 representation).
For example, the hash of JSON's "4\u00e9\u144E\uD834\uDD1E" (the four-character string "4éᑎ" , with the last character represented by the last two hexadecimal escape sequences), is the hash of the 11 octets
  34h C3h A9h E1h 91h 8Eh F0h 9Dh 84h 9Eh 53h
with 1 (resp. 2, 3, 4 and 1) octet(s) for the first character (resp. second character, third character, fourth character, and suffix octet).
The question uses a JSON relaxation in which a string used as the name of a field needs not be quoted. It is thus intentionally specified that in an object, age: 35, false:0, True:true, 1e0:42,{}:{},[0]:{} (if accepted by a parser) hashes the same as "age":35, "false":0, "True":true, "1e0":42, "{}":{}, "[0]":{} even though some of the derogatory names could otherwise be of type value, number, object, array.
Specifying that special value true is hashed in lowercase leaves unspecified if and where True is valid and its type, but specifies that if it is a special value assimilated to JSON's true, then it must hash as the later does.
More generally, freedom is left for parsing relaxation/extensions: for example, an extra ',' can be allowed before ] or } at the end of an array or object as in the question, or alternatively it can be allowed to omits null after a ','. The hash will follow whatever convention the parser uses.

Notes on coding of number:

As is, numbers that are equal (in some sense unspecified by JSON) can still have different hashes. For example zero can be (among an infinity of possibilites)
  0   -0   0.0   0e0   0E0   0e+0   0e-0   0e00314
If we wanted to fix this, there are choices to be made, and they are not easy. For a C compiler, 0.0 and 0 are not the same. For an experimental physicist, 1.2e4 and 1.20e4 are not the same.

Note: It is used a suffix rather than a prefix because that nicely aligns data for object and array, especially for hash algorithms which internal data block size is twice the output size, such as SHA-512.

Efficiency: SHA-512-JSON-V1 allow computation of the hash of any JSON of length $n$ in time $\mathcal O(n\log n)$. The $\log n$ term is only due to sorting of the hashes of a large object. We could get rid of this term, and often considerably reduce the memory used, with the technique in the second section of this answer, which outlines how to make an order-independent hash with an online algorithm using constant memory beyond input. We leave this for future extension!


Why not use random world events instead of a proof-of-work algorithm? Taking a combination of world events-- thunder, astronomical imagery, vote outcomes, stock index value-- and deriving the ID of the source of truth from a hashed combination of them could be used instead of a proof-of-work algorithm. Why isn't it used?

A true source of randomness or a Common Reference String (CRS) as it's referred to in cryptography, could potentially be used in some cases in the place of Proof-of-Work, although as forest pointed out it isn't immediately clear how to achieve this or whether it is possible, especially in settings such as blockchains where something closer to a Random Oracle (RO) is needed. However, it may be possible to substitute the two in settings such as Proof-of-Stake, like Ouroboros is doing. In the latter case, because of the design of the system, a CRS is not really needed – the participants can generate their randomness locally.

However, for the sake of argument, I will now describe some reasons for which using the types of events you mentioned as a CRS is inappropriate for designing cryptographically secure decentralized systems.

Public verifiability. It is easy for any machine to locally verify proof of work in polynomial time. If you give a piece of proof of work to a mobile phone or a laptop, they can check to make sure it has been computed correctly. However, they cannot do so for thunders, unless they constantly monitor the earth. Public verifiability means that anyone can verify, even after the fact.
Consensus. Participants can easily agree on whether a piece of proof-of-work is correct. The condition is clear and well-defined. However, for real world events, this may not be so. For instance, there are weird physical phenomena which may be considered thunder by some scientists and not by others, or a thunder may be captured by one observer, but not by others, even if they are actively monitoring for such events. This disagreement can break consensus protocols which require that all participants agree.
Sustainability. Proof-of-work is a system which will continue to work ad infinitum, because it is based on a mathematical formula. Systems such as stock indices may not. Stock exchanges close down and indices are redefined or sunset. While these events may be rare, if we are building the economy of the future which we want to last for more than a hundred years, we want a system that can continue to function regardless of such changes. If these changes do happen and we rely on them instead of proof-of-work, we would have to redefine our systems every time a change happened, and such a redefinition would require making difficult consensus decisions (which can lead to forks in the case of blockchains).
Centralization. It is difficult to define an objective source of truth for the values of these events. If the source of truth is defined as, say, the stock exchange website, then the central party that runs the website can manipulate the values that are displayed there. This makes the system prone to centralized manipulation. For instance, a court can order the exchange website to display false data in order to subvert the system.
Distribution. It is difficult to say what kind of distribution is followed by various sources of randomness such as the stock market. The fact that the stock market is just a random walk is controversial, and using this hypothesis to ensure our economy's future is an incorrect approach, especially because we cannot quantify it and prove our claims. While there exist ways to extract good randomness from skewed randomness, some quantification of the entropy in the source is needed, for which we also have a limited understanding.
Manipulation. This is related to the last two points above. Some of the systems you are proposing may be possible to manipulate by participants, given enough incentives. For example, if I am a rich investor, I could buy or sell a particular stock to change the value of the index, skewing the randomness in a particular predictable manner. If this artificial biasing is something I can use in my favour to make more money than I need to invest to cause the skewing, then it may be rational to act in that manner. It is difficult to give a game theoretic argument that such acts are impossible. With proof-of-work, the outcome cannot be artificially manipulated.


Safe and computationally efficient way to verify a curve25519 identity? A client identifies itself as a curve25519 public key. The server wants to verify the client owns the associated private key. Is there a safe and computationally efficient way of doing so? Which approach could be regarded to be “the most recommendable” from a safety point of view, while keeping it computationally efficient?

The community seems unsure whether curve25519 can be used for ECDSA. It should be safe to authenticate a nonce using a secret-key agreed with ECDH, but wouldn't ECDH itself be enough? The server sends a one-time use public key, the client returns a hash of the ECDH shared key and the server compares it.

Yes, it is possible to authenticate using ephemeral-static Diffie-Hellman. You would however first trust the public key of the static key pair. One way to do this would be to put it into a DH-based certificate, signed with a CA. It's not so common because usually certificates are used to establish trust, and certificates commonly use a public key used for signature generation when it comes to authentication. Of course you cannot use ECDH to sign/verify certificates, so you'd be stuck with a different algorithm to verify a certificate, if you decide to go that way.

After you've trusted the received public key you can perform normal DH-key agreement, then use the resulting session keys derived from the established secret to perform HMAC authentication. Within this authentication you would need to make sure that the ID's are used, that the nonces are random, that the public keys are included etc. etc. So generally we make it ourselves easy and lift the handshake procedure from an existing, known secure protocol, as indicated in the comments.


Testing the Fortuna random number generator? I have implemented the Fortuna random number generator as described in chapter 10 of "Practical Cryptography" (Ferguson and Schneier, Wiley, 2003), the result can be found at http://www.seehuhn.de/pages/fortuna .

My question: How can I test my implementation?  Or more specifically:

Are there any known-correct test vectors for the Fortuna generator available?
Are there automated tests for the cryptographic properties of the output?
(I know how to test the statistical properties of the output, but I don't know how to test the cryptographic properties.)
Any other testing methodologies I should consider?

Perhaps obvious, but couldn't you download other implementations, design a test set of your own, and run it through multiple implementations to verify the same results?

There are these implementations:

http://sourceforge.net/projects/fortunaprng/
https://github.com/dlitz/pycrypto/tree/master/lib/Crypto/Random/Fortuna

If system entropy is an issue, you might be able to tweak all implementations to fudge the updates to be equal.


Difference between X25519 vs. Ed25519 I am reading https://en.wikipedia.org/wiki/Curve25519 and it states

Also in 2018, RFC 8446 was published as the new Transport Layer
Security v1.3 standard. It requires mandatory support for X25519,
Ed25519, X448, and Ed448 algorithms.[24]

I understand from various answers on this site that the ECDSA is a different algorithm than EdDSA with EdDSA being simpler, faster and more secure than ECDSA. I am not familiar with the math behind ECC. I am looking for answers to the following questions.

Is X25519 and Ed25519 the same curve?
Is X25519 used by ECDSA?
What does the X in X25519 and X448 stand for?
Is the security advantage of EdDSA a result or the Ed25519 curve or the different algorithm it uses than ECDSA?
If ECDSA is used with the 25519 curve is it just as secure as EdDSA?
Is ECDSA considered to be secure as of Oct 2020?
Should EdDSA be always used over ECDSA?

Is X25519 and Ed25519 the same curve?

No. X25519 isn't a curve, it's an Elliptic-Curve Diffie-Hellman (ECDH) protocol using the x coordinate of the curve Curve25519. Ed25519 is an Edwards Digital Signature Algorithm using a curve which is birationally equivalent to Curve25519.
Is X25519 used by ECDSA?

No. It's not a curve, it's an ECDH protocol.
What does the X in X25519 and X448 stand for?

The X coordinate is what's transferred, the Y coordinate doesn't need to be transmitted due to the way these protocols work.
Is the security advantage of EdDSA a result or the Ed25519 curve or the different algorithm it uses than ECDSA?

Both (and somewhat neither). EdDSA's algorithm allows it to use curves that are more secure while being fast (ECDSA could be done using the complete point addition formulas over ANY elliptic curve, but it would be slower for many curves).
Additionally EdDSA is deterministic: there's no need to generate a nonce, and no need to track that a nonce is only used once. On the other hand, signing a message twice with the same key will reveal that the same message was signed.
If ECDSA is used with the 25519 curve is it just as secure as EdDSA?

Maybe. It would depend on how the math is done, and on how the nonce generation is handled.
Is ECDSA considered to be secure as of Oct 2020?

This depends on the particular implementation. It's NIST approved, and can be used securely if implemented well.
Should EdDSA be always used over ECDSA?

Not at this time. Some things will require ECDSA, for example the US government's FIPS 140 compliance doesn't allow EdDSA (yet). Also EdDSA signatures are deterministic (as mentioned above) which might pose problems to some schemes (though it does eliminate the security issues of nonce reuse that ECDSA has).
As kelalaka pointed out there already exist answers to most of these questions here, I've not bothered to link them.


Brute Force on 3DES with Reduced Keyspace and Unknown IV I'm trying to brute force a 3DES problem given a reduced keyspace (ie I know the first half of the key) but with an unknown IV. The code decrypts to plaintext. My first thought was that I could set the IV to the first 8 bytes of the CT, decode the rest and then substitute back to find the IV. This doesn't seem to work though - my brute forcer cannot find plaintext. I thought maybe it was getting confused with padding bytes at the end of the block being non-printable, so I removed the last 16 bytes as well, but that doesn't produce any results either.

Is there a flaw with my logic or is it more likely to be in my code?

Additional information from the comments

The ciphertext was generated using 3DES CBC and a 128 bit 3DES ABA key.

The key is 16 bytes, I know the first 10 (a ten letter word) and the next six are numbers (as in the ascii val of the digits 0-9). I'm basically brute forcing from WORDWORDWO000000 to WORDWORDWO999999.

My first thought was that I could set the IV to the first 8 bytes of the CT [and] decode the rest[.]

This is exactly how CBC works.

For all blocks but the first, encryption is defined by $C_n=E_K(C_{n-1}\oplus P_n)$ and, therefore, decryption is achieved by $P_n=C_{n-1}\oplus D_K(C_n)$.

Since there is no previous ciphertext for the first plaintext block ($P_0$), we just set $C_{-1}=IV$. So, yes, considering the first ciphertext block the IV will allow you to decrypt all remaining ciphertext blocks.

  [T]hen substitute back to find the IV.

That part is not that easy. The first block of plaintext is $P_0=IV\oplus D_K(C_0)$. If both IV and plaintext are actual text, there might be hope, although 8 bytes of text probably won't be sufficient for the standard tools (e.g., frequency analysis).

If the IV has been generated pseudo-randomly, it effectively acts as a one-time pad. This means that, unless you can deduce the first 8 bytes of plaintext from the remaining plaintext anyway, there's nothing you can do.


What is the difference between these AES encryption methods I am using AES encryption (Rijindael) with Base-64 encoding in Obj-C and VB. I am currently using the following two projects to achieve this:

Obj-C: https://github.com/dev5tec/FBEncryptor/tree/3c739f18c94ea257aba5cb7b6a97f49af2589977

Visual Basic:
http://www.codeproject.com/Articles/15280/Cryptography-101-for-the-NET-Framework#_articleTop

When I encrypt with what I believe is AES 256-bit on each platform, I get completely different results. Here is an example:

-Keyword: Hello

-Text To Encrypt (plain text): test

-Obj-C Result: 3V5u+L76l5sOOnlxzW7huA==

-VB Result: HR1TCsoEvFMDkdCjZui9Og==

Why are they so different if both claim to be the same type of encryption?
Does this have to do with the IV?

Could someone point me in the right direction, or at least confirm that both are in fact using AES 256?

EDIT: I've re-written the VB code with Microsoft's Rijndael Managed frameworks and it looks a little something like this: http://codeupload.com/6319

However, the Obj-C version still doesn't want to decrypt the text. I believe that it is due to a difference in IVs because as you can see, I haven't figured out how to randomly generate an IV. Also note that the salt is NOT static even though a static variable still exists. The Salt is generated through the GenerateSalt method.

I can immediately think of four reasons:

They're both not using AES256.  I see in the Obj-C document a direct statement that they are using AES256 (unless you deliberately change it), I don't see any statement in the Visual Basic document that says what key size they're using (unless that's what they mean by "Block Bits").
Different keys.  AES256 takes a key of 256 bits; there's no standard method to take a five character string and convert that into a 256 bit value.  Now, there are a lot of possible methods; there's no particular assurance that they both use the same one.
Different modes of operation.  The AES block cipher takes 128-bit values, and translates that into 128-bit values.  However, not all our messages can fit into 128 bits, and in addition, sometimes there are other things we'd like to do other than message encryption.  A Mode of Operation is a method that takes a block cipher, and uses it as a tool to perform some more generally useful function (such as encrypting a much longer message).  There are a number of standard modes of operations, the Obj-C document states that it is using CBC mode; the Visual Basic document has scary sounding words which might be a garbled explination of CBC mode.
IVs.  Some modes of operation (such as CBC mode) have the encryptor select an "Initialization Vector" randomly; that can be translated along with the encrypted message (because the decryptor will need that value).  One of the things that this Initialization Vector does if you encrypt the message a second time, the second ciphertext will not resemble the first ciphertext at all; that way, someone listening will not be able to deduce that you've just repeated a message.  The Obj-C document specifically says that it will pick a random IV (unless to tell give it one yourself).

As you can see, there are a bunch of reasons why the two ciphertexts may be different.  One thing you can try: hand the ciphertext from one to the other, and ask them to decrypt it; if they can, you can be pretty sure that both sides are doing basically the same thing.

One final warning: the visual basic document has some fairly egregious mistatements in it; either the author doesn't really know what he's talking about, or he is quite bad at explaining things.  I fear it may be the former; I personally would not trust any encryption software written by him.


What are the benefits of using AEAD algorithms as MAC I've seen in 2 places where NIST acknowledge the possibility of using AEAD algorithm for MAC (e.g. page 7 section 5.2 of GCM spec, summary for LAEM on page 6 of LWC status report).
And I see 2 problems with this:

An AEAD algorithm requires a nonce - something that doesn't fit well into the interface of $\text{MAC}_K(M) \rightarrow T$.

Most (and the correct) API for AEAD implementations (e.g. Web Crypto, Apple CryptoKit) receives input all-at-once - they are not progressively updated.

On the other hand, HMAC has several more application than authenticating messages - HMAC_DRBG, HKDF, to name a few. And they seems to be specifically instantiated from HMAC and cannot use other MACs, whether artificial like GMAC or associated with the algorithms they come with such as KMAC from SHA3/Keccak or keyed BLAKE2.
So to summarize, MACs derived from AEAD: 1) needs nonce, 2) needs different API (init-update-final) from that of AEAD (all-at-once), and 3) lacks usefulness.
So the questions:

Is there any benefit using an AEAD as a MAC (edit: specifically as a building block in constructs that expects one that behaves like a PRF such as HMAC) other than "it reduces code/circuit size"?

And what is (or was) NIST thinking when they acknowledge(d) using AEAD as MAC?

Think about 2 special cases when using AEAD:

Some confidential data but blank associated data
Some associated data, but blank confidential data

In first case what you get when using AEAD cipher (e.g. AES-GCM) is just Authenticated Encryption, as there is no associated data.
In second case what you get when using AEAD cipher (again, e.g. AES-GCM) is essentially a MAC - there was nothing to encrypt, and what you actually did was calculation of authentication tag over associated data.
BTW, "What are the benefits of using AEAD algorithms as MAC" and "What is (or was) NIST thinking when they acknowledge(d) using AEAD as MAC?" are actually two different questions. I hope I answered the latter.
EDIT:
If you look at MAC algorithms like Poly1305, Poly1305-AES or CBC-MAC, they also use nonce/iv.


Sweet32: Can a single 8 byte block session ID be exploited by this vulnerability? Im currently developing a authentication scheme. The authentication scheme will use a 64 bit encryption to encrypt its session ID.

Here is how the authentication system will work:

For each session, a 32 bit static session ID (one for each user, randomized for each login), and a 32 bit per-request session ID (one for each link on website, randomized for each new request) will be concatenated. This will be encrypted with DES or 3DES for n rounds, with different keys for each round. Also, I will randomize so sometimes the static ID is put first, sometimes the per-request ID is put first.

These session IDs will also be stored in database on server-side.

The reason I need to encrypt the session, instead of just randomizing the whole session ID and just sending it verbatim, is because I want to have a ability to invalidate ALL per-request sessions tied to the static session ID, if any attempt is made to submit a session that is either expired or invalid for some reason.

Eg, even if the sessions are deleted from the database because they are expired, I want to find every session still in database that is related (having same static session ID), and be able to delete them aswell, if any attempt is to submit a expired session ID.

Now you wonder, why so short session IDs. This is because some of these session IDs will be used as one-time passwords that is manually entered. With hex, this will result in 16 characters to be entered, and having longer blocks will of course result in a tedious typing for the users.

Now to the question: Will this scheme be vulnerable by sweet32? What I understand from the sweet32 papers, ciphers relying on a single block without any CBC or something will be safe right?

Or is it something I have misunderstood from Sweet32 vulnerability?

What I understand from the sweet32 papers, ciphers relying on a single block without any CBC or something will be safe right?

Yes Sweet32 applies to ciphers with block sizes of 64 bits in CBC mode. The idea is to collect enough ciphertext to find a collision (which due to the birthday problem will be around $2^{32}$ blocks), in other word two ciphertext blocks that are equal.

We can write these blocks as $E_k(C_{i-1} \oplus P_i), E_k(C_{j-1} \oplus P_j)$, as in CBC mode we encrypt the XOR of the plaintext block and the previous ciphertext block. We note that since the blocks are equal it must hold that $C_{i-1} \oplus P_i = C_{j-1} \oplus P_j$. We know what the ciphertext is so if we write the equality as $C_{i-1} \oplus C_{j-1} = P_i \oplus P_j$ we know the lefthand side and recovering the plaintext blocks becomes equivalent to solving a two time pad.

Note that beside only working on 64 bit ciphers in CBC mode, this attack also requires a huge amount of data. I think in the paper the researchers observed hundreds of gigabytes of ciphertext before finding a collision. Given the amount of data needed (I doubt you have hundreds of GBs of session IDs), and the fact that you are not using CBC mode you are not at risk.


Where is my private key stored when I communicate to a website that uses SSL/TLS? If I communicate with a website that uses SSL/TLS, my browser will generate a private key. Would the browser store that key on the hard disk or would store just it in the RAM?

SSL does not generate a private key. What is generated is shared secret key between the client and server.This shared secret key is only valid till the session lasts. So, this shared secret key resides in the RAM. It is not saved in to the hard disk.


Is allowing both digitalSignature and keyEncipherment certificate usages a bad practice? From what I see, many server and client RSA certificates in the real deployments have the "key usage" mask containing both digitalSignature and keyEncipherment.

Isn't this a bad (that is, potentially insecure) practice, given that there's a general guideline to use separate keys for different purposes?

As an example of protocol that appears to freely switch between this two, take TLS 1.2. If the key exchange method, that was negotiated between the client and the server, is ECDHE_RSA, then the digital signature capability of the certificate will be exploited during the handshake; if, on the contrary, the method is plain-RSA, then the key encipherment capability will be used. And these two specific instances are probably still widely used - assuming this after checking which methods have been deprecated by the most popular browser Chrome and which have not.

The guidance is more about keeping the certificates used for different operations seperate. Not keeping the certificates used for different ways of achieving the same operation seperate.

In the case of different TLS key exchange, the overall operation is still the same, i.e. Generating and exchanging a session key. While technically one method generates a key then sends it, with the other involves signatures they have the same overall lifecycle and consequence if the key linked to the certificate is disclosed.

The general guidance applies more to situations where the operation is different. E.g. With email signing there are two operations, encrypting the email (to prevent it being intercepted) and signing it (to prevent it being forged). As per this answer there are situations where you'd want to disclose the encryption key but not the signing key.

This doesn't apply to the different key exchange algorithms in TLS so the certificate usage is more of a technicality.

Of course if you then used the same certificate to sign something then that would be a terrible security practice.


What is the Advantages and Disadvantages of digital signatures over HMAC? I want know the advantages of using digital signatures over HMAC for message by message authentication.

I know that HMACs are inexpensive to implement compared to DS, but DS provides a very strong security also uses more processing power. Are these two the main differences?

Digital signatures provide non-repudiation, which is one of the basic principles of information security, and HMACs do not (since the key in HMAC is known both to the sender and the receiver).

And then of course the points you mentioned also apply.


Is a 256 bit HMAC-SHA256 key compromised if the tail is used for identification? Using a truncated hash of a key seems to be a safe way to identify the key (i.e. key fingerprint), but what about truncating a key itself in the case of HMAC-SHA256?

Example:

$ key=`openssl rand 32 -base64`
    $ keyId=`echo $key | cut -c 40-43`
$ echo $key
RlBDpvx3pCD/rs2SyeHX0enLOxCP7mEQCB8zvtQhD6g=
$ echo $keyId
hD6g
$

Is using $keyId as a way to identify the key secure?  I recognize that the security strength will be reduced, but is it a negligible/acceptable amount?  Is there something in the literature that addresses how disclosing the tail of a HMAC key impacts security?

This won't seriously impact the security of the key. HMAC is pretty resilient and changing the last part of the hash won't allow attacks on the a hash such as SHA-256.

Note that you only select 4 characters, of which the last one only encodes 4 bits (as it is at the end). That means you've got a check value the size of 2^22 encoded bits, i.e. a chance of 1 / 4194304 that you match a key that you didn't mean to match. If you generate a whole lot of keys you can certainly not use this to select one key from a set because of the birthday problem.

The security of HMAC is diminished with 22 bits as well, leaving you with 256 - 22 = 234 bits maximum security. Halve this for a usual setting of HMAC, so with a bit of handwaving, you're left with 117 bits.

Generally you take bytes from binary data before encoding to base 64. If you need base 64 you can separately encode the bytes afterwards.

Possible without significant reduction in quality: yes.

Advisable? Absolutely not, there doesn't seem any good reason to do this. Use a KBKDF (key based key derivation mechanism) instead to create a key fingerprint. You may use the HMAC using the normal key and an unlikely string for data for this.


Is there a deterministic number generator that allows me to share some (not all) numbers I've generated using a smallish seed? I was just wondering, is there a type of deterministic number generator that allows me to share some (not all) numbers I've generated using a smallish seed?

I have pairs of random numbers and need to make one number from each pair public. The point of sharing with a type of seed is, that my application needs to do hundreds and thousands of these and any space saving will result in massively decreased storage and transmission costs. Which one of the pair I want to make public is not known during key generation.

A really basic insecure example would be to use sha256(seed + n) where n starts at 0 and increases for each number. You would share the seed plus all the n values you want to share. Obviously this means people could generate the numbers I don't want them to by filling in the missing n values.

I'm not sure if such a thing exists, but I figured the folks at Crypto.SE would know if it did, or be able to invent it. Oh, and half of the pairs of numbers is about 2048 bytes, so any solution would have to be smaller than that to be worth it.

A really basic insecure example would be to use sha256(seed + n) where n starts at 0 and increases for each number. You would share the seed plus all the n values you want to share. Obviously this means people could generate the numbers I don't want them to by filling in the missing n values.

You could extend that idea and use $\operatorname{sha256}(seed || n || r_i)$, where $r_i$ are smaller random numbers. By using 32-bit seeds to produce 256-bit random numbers, you would save almost 90% of the transmission and storage costs.
However, anyone could tell an unrevealed number was one of the $2^{32}$ that could be created with that seed and n.

If that's not acceptable, you could build hash trees, where you start from one seed and at each level derive two seeds from one, eventually ending in the random numbers desired. (There would be one hash tree for "left" and one for "right" values in the pairs.)
Then you could reveal any seeds for which the whole subtree should be revealed. On average this could save almost a third of the data.

As a special case of the above, if you just used a new seed every other left/right value (i.e. left of the first two pairs would be derived from a single seed), you could save exactly 25% of the data on average with simpler logic than a whole hash tree requires.


High Throughput Global Entropy Source Is there an entropy source that provides the following three properties?

true randomness
for a distinct time-period, produces same (random) data on two devices that are less than 10 km apart from each other
high throughput, so recording randomness for a few minutes requires terabytes of data storage

I considered sources like atmospheric noise or similar, but I am unsure whether they fulfill property (2) (and (3))...

I am going to assume that you're a regular Joe (no offence), and not a rocket scientist or millionaire philanthropist with a huge research budget, as this determines the answer.

No.

There is no true random number generator available to you that can meet all of your three tests.  By your mention of atmospheric noise, I'm further assuming that you're meaning a true random number generator based on physicalities, rather than a pseudo random number generator like the Mersenne Twister.

Specifically:

Yes.  True randomness and entropy are all around you.  I mean  sources of unpredictability.  The noise on your camera phone party pics, the jitter in your PC's system clock or noise on a voltage regulator valve.  These will not though produce uniformly random numbers without some randomness extraction.
Yes.  Any of the above will achieve this.  There is no interaction between the examples I've given.  (Even photon entanglement can be mitigated over a metre's distance but you won't be building one of those).
No.  Another assumption is you want a rate of 5 TB in 5 minutes.  That's >100 Mbits /s.  You cannot achieve this as Joe.  Unless you spend a great deal and are pretty clever building stuff.  I'm not aware of any simple devices like ring oscillators that can easily output this rate at the hobby level of construction.  (I exclude Intel CPUs as those are highly suspect undefined generators probably crippled by the NSA.)

3 1/2.  Be very careful with atmospheric noise.  I don't believe that it's possible for typical hobbyists to generate more than a few bits /s from this as the safety margin for true randomness will be enormous. The EM spectrum is full so your only course is to build a very broadband receiver and rely on the central limit theorem to achieve randomness. You can't use a tranny radio.  You will just end up sampling thermal noise on your receiving circuitry, oscillations of the phase locked loop FM detector or Lady Gaga's latest hit.  That probably happens at random.org and they just side step it with technobabble so don't be encouraged by their example.  Tip:  Use a 24V Zener diode. Enough true randomness for Joes.

Can I suggest that you see this question regarding your property 3?


Are there any downsides to key stretching an already high quality entropic key? For example, if we grab 50 bytes from a high quality source and run them through a key stretching function like Argon2 and have it generate a 32 byte secret for AES.

Is there any downside to this? Do we lose any entropy during this process since it comes from a high quality source already?

Even with perfectly random input, if your final key size is 32 bytes, you cannot have more than 32 bytes of entropy in it.

But it seems pretty useless to use key stretching if you already have more random bytes than your key length, you could just use 32 bytes of your 'perfect' source as an AES key. You just expose yourself to possible weakness in the key stretching algorithm without any benefit.


Triple-DES Brute Force Shannon's paper states:

  A system is pure if all keys are equally likely and if for any three
  transformations, $T_i$, $T_j$, $T_k$ in the set, the product
  $T_iT_j^{-1}T_k$ is also a transformation in the set.

But this is exactly the construction of Triple-DES! So, using this terminology, it is not a pure system, since that would mean a 56-bit DES brute-force attack could be successfully mounted against a 168-bit Triple-DES key. Is that right?

Yes.

For DES, it looks like the composition $T_i\circ T_j^{-1}\circ T_k$ is normally not a $T_l$ with another key $l$.

I do not have a proof of this fact.

So DES is not a pure system, and otherwise triple-DES would not more secure than DES itself.

In a comment, fgrieu linked a proof for a weaker fact, that DES is not a group (by Campbell and Wiener).

They actually did some experiments searching keys $i, j, k, l$ so that $(T_l \circ T_k \circ T_j \circ T_i)(\mathtt 0) = c$, with 50 different random values $c$ messages randomly selected from the full $2^{64}$ block set. They found such a set of keys for all 50 values $c$.

Since the set $K$ of DES keys has only size $2^{56}$, also the set $T_*(\mathtt 0) = \{T_m(\mathtt 0) \mid m\in K\}$ has at most size $2^{56}$. The probability that all 50 messages would be in this set $T_*(\mathtt 0)$ was estimated as $\leq (2^{-7})^{50} = 2^{-350}$. So very probably $(T_l \circ T_k \circ T_j \circ T_i)$ is usually not a $T_m$, i.e. the set of DES encryptions is not closed under composition.

The paper also provides some lower bounds on the size of the subgroup spanned from all the DES encryptions by calculating the cycle sizes of $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$ applied to various messages, which all must be factors of the order of the cyclic group spanned by $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$, which itself is a subgroup of the group spanned by all DES encryptions (and decryptions). The lowest common multiple they got was more than $10^{2499}$, much larger than the number of all DES keys (or even all triple DES keys).

What does this mean for our question?

DES (or any set of permutations $\{T_i \mid i \in K\}$) being a group (subgroup of the set of permutations) would include that for each key $i$ and $j$ the composition $T_i \circ T_j$ is a DES encryption $T_l$, and also each
decryption $T_j^{-1}$ is an encryption $T_m$. From that we could conclude that $T_i \circ T_j^{-1} \circ T_k$ is also a member of the group, i.e. that the set would be a pure set.

The reverse doesn't follow that easily, and neither is the proof directly applicable to our situation (both look at different corollaries from the group property).

I suppose one could do similar experiments as they did, search keys $i,j,k$ so that $(T_i \circ T_j^{-1} \circ T_k)(\mathtt 0) = c$ for random messages $c$ and argument similarly that this should give not as many matches as it does when that would be in $T_m$.

The other point of view is the practical one: If DES were pure, triple DES would be essentially the same as DES, and would be already broken by appliying a DES brute forcer on a triple-DES encrypted message. I can't believe nobody tried that yet.


Do MD5's weaknesses affect Oplop? Oplop is an algorithm that generates account-specific passwords from a master password and user-chosen nickname (typically username@domain). From the website:

Concatenate the master password with the nickname (in that order!).
Generate the MD5 hash of the concatenated string.
Convert the MD5 hash to URL-safe Base64.
See if there are any digits in the first 8 characters. If no digits are found ...

a. Search for the first uninterrupted substring of digits.

b. If a substring of digits is found, prepend them to the Base64 string.

c. If no substring is found, prepend a 1.
Use the first 8 characters as the account password.

The author says MD5 is safe. Is this true? Are there any flaws in MD5 that make it insecure as a one-way function (instead of a "thumbprint" of a string)? Is it secure when the attacker can access all 128 bits of the hash, or does the hash need to be truncated (as it is in Oplop) in order to prevent collision attacks?

The short answer is: technically, no. The weaknesses of MD5 are not an issue here. However MD5 is seriously inappropriate, for it is the wrong king of security primitive; also its reputation is tarnished.

If a collision attack was to be feared, then using MD5 would be a disaster, for it is now hopelessly broken w.r.t. to collision resistance; but that does not seem to be a serious threat in the stated usage. At worse, it seem possible to exhibit different (master password, nickname) pairs resulting in the same account password, but I fail to see that it leads to a practical attack.

The main technical drawback of using MD5 in the stated usage is, paradoxically, MD5's main quality: it is fast. That makes password cracking much easier than for a purposely slow Password-Based Key Derivation Function like PBKDF2 or Scrypt, and slightly easier than if using a hash stronger than MD5, like one of the SHA-2. However being fast is not considered an MD5 weaknesses; using a fast hash is a weakness of the proposed usage.

Also, from a Public Relation standpoint, using MD5 is a bad idea, much like using a tire known to explode at high speed is a bad idea for a manufacturer of low speed cars.

Update: Unless the master password is imposed on the user (which makes the scheme much less useful), a controllably slow Key Derivation Function is required, and as an aside should be followed by a better method to generate an acceptable password (as pointed in that other answer). I recommend Scrypt, because it uses controllably much RAM and (possibly) CPU cores, hence raising the cost of a determined attack for a given penalty to the user (a small parameterizable delay, and using the computer's resources during that time). See this table from the paper defining Scrypt:
:
Note: A letter is random among 26 lowercases; a character is random among 95 ASCII symbols; text entropy per NIST SP800-63-1.


Can randomness protect a list of signatures against forgery attacks? Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for each $m_i$.

If we proceed, instead of verifying all $n$ signatures, by verifying a set of $k \lt n$ messages chosen randomly and uniformly, for a random $k$, we could say that $S$ is valid for $M$ with a "certain probability" depending on how many messages we verify.

My question is: If an attacker wants to forge a list $M'$, say he uses $l$ messages from $M$ with their valid signatures, and adds $n - l$ new messages with invalid signatures, constructing new lists $M'$ and $S'$, hoping that $l \geq k$ and that we would only verify the $l$ valid ones, and assume that $S'$ is valid for $M'$ (which is not the case !).

Will he have a high chance or probability of forging such a list of messages, if he has no information about $k$ ($k$ chosen randomly on each verification)?

If $l<k$, then the attack will be detected with a probability 1.

If $l\ge k$, the probability of the attack not being detected is
$$\frac{l}{n}\cdot \frac{l-1}{n-1}\cdots \frac{l-k+1}{n-k+1}\ge (\frac{l-k+1}{n-k+1})^k$$

Whether this is large enough or not depends on $n,k,l$.

If the attacker does not know $k$, the best he can do is to choose $l=n-1$, which gives him the highest probability of not being detected.


Finding a secret key corresponding to a public key As far as I know, a secret key corresponding to a given public key is not unique. So, for example, there are actually multiple secret keys that can produce the same digital signature under RSA signature scheme.

What I wonder is, how can I compute the expected time to find a matching secret key of a given public key? I assume some details are given like the length of keys, the key generation algorithm etc.

Also, is there a public-key encryption scheme s.t. there's a unique secret key for each public key?

The expected time to compute a secret key from a public key is of course entirely dependent on the scheme and the security parameter. Of course for the scheme to be secure, the probability that an adversary can make such computation in poly time must be negligible.

Regarding your second question, you might want to look here.
Again this is entirely dependent on the scheme.


Why does SSH authentication protocol send a challenge message instead of using digital signature to verify client Why does SSH authentication protocol choose to have the server with the public key send a challenge message encrypted with this public key of the client instead of having the client send a message signed with it's private key along with client ID and have the server verify the signature?

Wouldn't verifying the signature be enough proof that the client really does possess the private key and hence is authenticated?

The server sending an encrypted challenge has a few advantages over the signature-based method you described:
1) It is more efficient for the client in the case that authentication is rejected outright.
If the server doesn't recognize the client's public key, there's no reason to have the client waste time and energy generating a signature.
2) It is more secure from the server's perspective since the challenge is, for all intents and purposes, completely unique per connection.
The server is not just trying to verify that the person who signed the message has the private key but that the client it is connected to is the one who signed the message.  So a signature would need to be of data that could not have been stolen from a separate communication (either with this server or another one).
3) It also helps protect the client's private key from clever attacks.
As described in section 3.4.2.2 of the O'Reilly book on SSH:

The client receives the challenge and decrypts it with the corresponding private key. It then combines the challenge with the session identifier, hashes the result with MD5, and returns the hash value to the server as its response to the challenge. The session identifier is mixed in to bind the authenticator to the current session, protecting against replay attacks taking advantage of weak or compromised random-number generation in creating the challenge.
The hashing operation is there to prevent misuse of the client's private key via the protocol, including a chosen-plaintext attack. If the client simply returns the decrypted challenge instead, a corrupt server can present any data encrypted with the client's public key, and the unsuspecting client dutifully decrypts and returns it. It might be the data-encryption key for an enciphered email message the attacker intercepted. Also, remember that with RSA, "decrypting" some data with the private key is actually the same operation as "signing" it. So the server can supply chosen, unencrypted data to the client as a "challenge," to be signed with the client's private key -- perhaps a document saying, "OWAH TAGU SIAM" or something even more nefarious.

4) A signature based method, implemented properly, would still require the same number of steps, due to the logic in (2).
That is, because the server wants to be sure that it the client has the private key, even in a signature based method it would be best for the server to send a random challenge and have that signed, making the process look very similar but without the benefits described above.


Blinding value of particular form I'm working with an implementation that creates a blinding value for RW signatures with the following C++ code:

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));

The Jacobi tests were added to remediate Sidorov's Breaking the Rabin-Williams digital signature system... and CVE-2015-2141.

Instrumentation is showing the loop can execute 1 time to 10 or 12 times (I believe the expected average is 8 times).

I feel like there's a way to speed up the execution of the loop. I started looking in the HAC and Google Scholar, but I did not find a related article or paper. I tried a couple of naive speedups, but they did not produce expected speedups or bound the worse case. The first was to generate a random integer in the range $[1, n - 1]$ that was congruent to $3 mod 4$. The second was to generate two smaller integers in the range $[1, p - 1]$ and $[1, q - 1]$ (both congruent to $3 mod 4$), and then multiply them.

Is there any way to speed up the execution of the loop so that the blinding value $r$ usually satisfies the condition in 1 or 2 tries or so?

Or is the implementation above ideal?

A related question is Rabin-Williams, blinding and size of Integer r? In this question, I explored smaller random integers to mask the operations.

What you are doing is the following:

Choose a random number $r$ in $[1,2^n-1]$.
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.
Check if $(\frac{r}{p})=(\frac{r}{q})=1$($(\frac{a}{n})$ denotes the jacobi symbol), if not go to 1.

So in order to speed this algorithm up, one needs to understand what the step #3 does.
"It calculates some Jacobi / Legendre Symbols" is too easy.
This step makes sure that $r$ is a square $\bmod p$ and $\bmod q$. Hence it makes sure that $r$ is a square $\bmod n$, because if r is a square $\bmod$ $p$ and $q$ than it's also a square $\bmod pq$. The calculations are split ub and not performed like $(\frac{r}{n})$ because $(\frac{r}{n})=(\frac{r}{p})*(\frac{r}{q})$ and if $(\frac{r}{p})=(\frac{r}{q})=-1$ then $(\frac{r}{n})=1$. So this doesn't work for optimzation.

But there's another way.
Step #3 makes sure we actually do have a square $\bmod n$, so why don't we construct $r$ to be a square $\bmod n$? Thus the "new" algorithm would look like this (sorry, I forgot the proper functions for Crypto++, post them in the comments please)

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    r = r*r%n; // square it, there was a better function for this IIRC
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero()); // we don't need the symbols because r is always a square

So what are the security implications with this?
I don't know for sure, you should contact the author of the paper in either case and make sure this solution works.
The squaring of $r$ shouldn't harm the randomness / unpredictability as if $r$ is random, $r^2\bmod n$ should be random / unpredictable as well.
Timing attacks? Shouldn't be a concern I think because an attacker may only observe one squaring and after this a related squaring making it really hard to use this. (if it's not impossible)

What else to say?
You even can store the "old" $r$ if you need the square root of the "new" $r$ in a later step.
The new algorithm looks like this:

Choose a random number $r$ in $[1,2^n-1]$.
Set $r \gets r^2 \bmod n$
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.


Does selectively generating keypairs with particular public-key hash prefix weaken the security? I'd like to embed 8-bits of information by selecting only keypairs where a hash of the public key begins with those 8-bits.  (The expected number of keypairs that will need to be generated is 256, so there is a little extra work required.)
The goal is to be able to determine the source of a keypair, to aid debugging in a distributed system.
Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?  (Assume that the hashing function is irreversible.)
If so, how?

Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?

No, if the hash used is independent of the public key cryptosystem. Then the selection of private keys made is equivalent to a random selection, and can't harm security. That's even provable.
In theory you'd have to use separate hashes for this selection and other uses. That can be implemented with separate prefixes for multiple uses of the same hash. In practice, if hashing data starting with the public key is nowhere to be found (e.g. because the public key is only hashed as part of a certificate with a non-empty prefix), one is likely OK with just selection from the hash of the public key, as in the question.


Knapsack Public to Private (Superincreasing knapsack) I need to convert a hard knapsack to a superincreasing knapsack.

I have these superincreasing values (3,6,11,22,43,87).
I also have w = 7 and n = 173.
I converted the superincreasing values to hard one (21,42,77,154,128,90)
by computing $a_i = x_i * w \bmod{n}$.

(3 * 7) mod 173 = 21
(6 * 7) mod 173 = 42
(11 * 7) mod 173 = 77
(22 * 7) mod 173 = 154
(43 * 7) mod 173 = 128
(87 * 7) mod 173 = 90

Question

I want to ask how can I get the superincreasing values if I have hard one.

example

Can I convert (21,42,77,154,128,90) to (3,6,11,22,43,87) with $w = 7$ and $n = 173$?
Or how can I find the x_i if w = 7 and n = 173?

(x1 * w) mod n = 21
(x2 * w) mod n = 42
(x3 * w) mod n = 77
(x4 * w) mod n = 154
(x5 * w) mod n = 128
(x6 * w) mod n = 90

Here's the idea: given $w$ and $n$, we find a number $v$ such that $vw \equiv 1 \pmod{n}$.  In your case of $w=7$ and $n=173$, we have $v=99$; such a $v$ will always exist if $w$ and $n$ are relatively prime, and can be found by the extended Euclidean algorithm.  The value $v$ allows us to map from the "hard values" to the "superincreasing ones".

Here's how it works, suppose someone wants to send you a message corresponding to the first, third and fifth indicies: to encrypt it, he takes the public key, looks up the first, third and fifth indicides and adds them $21 + 77 + 128 = 226$; he sends the value $226$ as the ciphertext.

What you (the holder of the private key) would do is multiply the ciphertext (226) by $v$ modulo $n$; that gives $226 \times 99 \equiv 57 \pmod{173}$.  You then go through the original superincreasing list to decode that, and easily see that $57 = 43 + 11 + 3$; that is the first, third and fifth indicies, correctly decoding the message.

This decoding method works quite well -- the problem with this crypto system is that it can be broken; this paper shows how an attacker can quickly decode even without the private key.


Does Encryption add difficulties to File Recovery? Seems Yes. People always tell us, it is very hard (or almost impossible) to recover an encrypted hard disk.

But after a second thought. I think this is not true.

Given that we know the KEY, and the method/algorithm of decryption, the decryption(key, encrypted_data) should be no different from plain text.

For example,

We mistakenly deleted a file. We have to examine the bits on the hard disk, identify the start and end positions of the file, and un-delete it. Of course the bits on the hard disk looks meaningless. However after decrypted, it appears no different from an ordinary hard disk.
Bad sector happens to the hard disk. For those error bits, those bits are lost, no matter encrypted or not. (Of course you can guess those bits and recover them.) For the rest intact parts of the hard disk, we can still decrypt those files as normal.

However there are some concerns that I am not clear about.

As some (or most) disk encryption algorithms are chaining previous and next sectors. Will this lead to whole hard disk not recoverable with just one error bit?
Consider the "bad sector example" above. If an error bit falls on an JPEG file. With a normal hard disk, we can still view the image, with display error on certain parts only. However with an encrypted hard disk, will encryption leads to whole image not viewable?

All-in-all, given that we know the KEY, and the decryption algorithm, does Encryption still add difficulties to File Recovery?

It depends on the circumstances, whether encryption will cause difficulty while recovering files. If you have your physical drive damaged then chances of recovering the data in the first place (encrypted or not) are bleak depending upon the extend of damage.
First let's think of this hypothetical situation when using file system level crypto on the contents (files) of a drive: If I have an algorithm (that does not use chaining) that uses encryption  with authentication to encrypt the contents of a drive. Say, my drive got physically damaged, but the damage was to a small extend. It so happend that the "error bits" were on a JPEG image. If I decrypt that content from my hard drive, my software would give me an error stating that, the file / content has been damaged and its integrity can never be trusted and would refuse to decrypt it. But If I know the algorithm and the key and I make a custom software to decrypt the contents of the file no matter what, I might get a decrypted JPEG that may be partially viewable/cluttered at some places. But still in essence the data is tampered and the whole purpose of "authentication" has been compromised!
But the above situation is practical if we are using file system level encryption/ decryption and that is why it is more recommended to use it than FDE (full disk encryption), at least you can view parts of the image / file.  But still the algorithm itself opens up difficulties
if I used AES CBC with HMAC to encrypt my file then the block where the error bit occurs, the decryption becomes cluttered and meaningless, and also alters the output of the decryption of the adjacent block but if I used a stream cipher like XChaCha20-Poly1305 the error byte will be meaningless, but I get the rest and in both cases the authentication tags will not match as a result of the errors in the data in the first place.
Secondly, if I used chaining algorithms AES CBC to do FDE full disk encryption, then the error propagates, from the block where the error occurs and also affects the bytes of the next block getting decrypted . It is mostly due to the fact that the encryption function themselves have an avalanche effect when their input bits are changed giving totally different outputs !
At most if you use chaining you loose blocksize*2 bytes of data for blocksize bytes error in a block. For AES this block size is 16 bytes.
Therefore it depends on the algorithm that you use and also the circumstances in which they are applied.
In practice we use AES XTS as the defacto standard for full disk encryption:
See:
Disk encryption theory

AES XTS

Hope you understand what I wanted to convey...


Is Cramer-Shoup Lite IND-CCA secure? Recently, I studied about Cramer-Shoup encryption scheme. Then, I read a book which mentioned a simpler version of this scheme, the Cramer-Shoup Lite encryption scheme.
I was wondering if there is somewhere a formal proof of IND-CCA security of Cramer-Shoup Lite encryption scheme.
Any help would be appreciated.

It's far from a full proof, but if you use the sketch from Boaz Barak's lecture notes, together with the full proof of the full scheme from the Cramer-Shoup paper, you should be able to work it out.


Provably Secure Post-Processing of a True Noise RNG? My customer wants an RNG that uses a true noise RNG and a post-processor that will provide provable security against recovery of the true noise RNG output.

Is there a provably and post quantum secure hash function that I could use?

If your entropy extraction algorithm is well written and satisfies the relationship (entropy in) > (entropy out), there is no issue with recovery.  A lot of TRNGs do not even use cryptographic hash functions for extraction. A simple matrix multiplication acting as a compression function will do (as long as its compression window is wider than any length of auto correlation).

You can't recover the raw data if my above relationship holds true due to the pigeon hole principle, but even if you did it would be pointless.  That entropy has been used up and will never again be used. The TRNG will then create more entropy for the next set of random numbers. So as long as you're using a true random number generator with a good entropy extraction technique your concern is moot, quantum attack computer or otherwise.


Unique assignment of X.509 certificate to each client I'm trying to implement a short scale electronic voting application in a domain comprised of no more than 100 clients. System administrator is able to create new election instances and each client is able to cast his vote once for each election.

I do believe that a PKI (e.g. OpenSSL) is necessary here in order to issue a X.509 certificate for each client. Upon registration client will provide a unique identification code to the system so an obvious choice is to store this value in the "subject unique identifier" field which is possible in version 3.

What I'm trying to understand is how will the CA conserves the uniqueness of this field? Does it compare the value supplied for a new certificate with each certificate previously issued? Is this even a logical solution for this problem?

In a typical X.509 PKI implementation, the CA is somewhat heavyweight. Far more than just a special CA certification, running a CA typically implies running a web service to service certificate requests, perhaps an OCSP responder, publishing CRLs regularly, perhaps an SCEP server... This heavyweight notion works well for large enterprises, but somewhat less well for small deployments like your own. Suck it up, though, because there really isn't a good solution for lightweight deployments.

What I'm trying to say is that yes, the "correct" solution in this case is for the CA to check to make sure it hasn't issued a certificate to that user before issuing a new one. This is a fairly annoying extra requirement for a small deployment, but an utterly trivial task next to all the other crazy things a "standard" X.509 deployment is expected to do. I feel your pain, and I know it's not very elegant, but the easiest solution in this case is to just keep a list of all the ID codes served so far and fail if one is resubmitted.

In an ideal world, you'd be able to map the unique identifier you're talking about to a unique key, so re-issues wouldn't be a problem. However, that's not doable with X.509.

PS: I'm assuming here that you in fact want to do what the question title says: assign only a single certificate to each user. If, instead, you only need to prevent double-voting during the election, you could just record the subject unique ID of everyone who's voted already, which would make having more than one certificate for the same unique ID useless. Changing the logic of your voting application is probably easier than changing the logic of whatever CA service issues the certificates.


Winternitz One time signature security There are two versions of Winternitz-One time signature scheme, $W-OTS$ and $W-OTS^+$

Security of both is as following

  $W-OTS$ is strongly unforgeable under chosen message attacks if $F$ is a collision resistant, undetectable one-way function family

  $W-OTS^+$is strongly unforgeable under chosen message attacks if $F$ is a $2nd$-preimage resistant, undetectable one-way function family

My question is which version is more secure $W-OTS$ or $W-OTS^+$?

According to my understanding $W-OTS$ is more secure than $W-OTS^+$ because for attacker it is comparatively easy to find collision resistant as compared to $2nd-$preimage resistant.

If so is it secure to use $2nd-$ preimage resistant Winternitz one time signature scheme?

Ideally scheme should be collision resistant or $2nd-$preimage resistant.

W-OTS+ is stronger, as it makes weaker assumptions on the hash function.

Let us take a rather extreme example, let us consider W-OTS and W-OTS+ based on the MD5 hash function.

Now, the proof for W-OTS is quite invalid; it assumes that the hash function is collision resistant, and we know how to generate collisions with MD5.

On the other hand, W-OTS+ based on MD5 would appear to be secure; despite MD5 being "broken", we do not know how to create second preimages to MD5.

BTW: this appears to be more about the proof technique used to prove W-OTS, rather than the actual security; we can create MD5 collisions (invalidating the proof), however we don't know how to use those collisions to actually attack W-OTS-MD5; hence it would appear to be secure (but we can't prove it).

Also, one note: those aren't the only versions of Winternitz signatures in the published literature...


Key derivation functions (KDF): What are? Main purposes? How can they be used? What are KDFs? What are their main purposes? How they can be used, in other words, what's their drill in a cryptography scheme?

The HKDF paper provides as good a summary as any:

  A Key derivation function (KDF) is a basic and essential component of cryptographic systems: Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys.

Here it's important that you understand how the term "random" is used in probability theory vs. how it's (ab)used by computer people.  Very informally:

When us computer folks say "random" we more often that not implicitly assume that we're talking about a discrete, finite, uniform and independent random variable—one that takes on any value drawn from a finite set with equal probability as all the others, and earlier outcomes do not influence later ones, the way coin flips or dice rolls behave.
When statisticians say random, they aren't assuming as much.  For a statistician, for example, a stereotypical random variable has a normal distribution ("bell curve"), where values cluster around a mean and disperse according to a standard deviation—the way, for example, that inexact physical measurements have random errors that cluster around the true value.

So reading the quote with that in mind, a KDF is a cryptographically strong function that takes input that is random in the statistician's sense and produces output that is pseudorandom in the cryptographer's (preferred) sense.  This is useful in various contexts:

Diffie-Hellman key exchange with randomly selected keys produces a shared secret that is random in the statistician's sense, but its output is not uniformly distributed.  So to use this secret as a symmetric key you pass it through some KDF.
Cryptographic random number generators refresh themselves periodically from the values obtained by measuring random events like network packet timing, mouse movements or key presses.  These are also not uniform, so a KDF can be used to fix that.
Passwords are also not uniform, so to turn passwords into keys we use KDFs.  But in that case we use specialized password-based KDFs that also add a work factor to slow down brute force guesses.


Security of Fast Two-Party ECDSA Signing The paper "Fast Secure Two-Party ECDSA Signing" by Yehuda Lindell describes a system in which two parties, $P_1$ (with 1/2 of a share of a long-term ECDSA signing key $x_1$) and $P_2$ (with the other 1/2 share, $x_2$), cooperate in order to produce an ECDSA signature, $P_1$ being the party that actually outputs the final signature.

In Section 3.2, describing the process for distributed signing, it is said that a hypothetical attack by $P_2$ implies sending a malicious message such that if $x_1 \bmod 2 = 0$ then the final signature is incorrect (and hence $P_1$ will not output a signature), and if $x_1 \bmod 2 = 1$, then the final signature is correct (and hence $P_1$ will output a signature). The author refers then to the security proof for details on how to handle this.

If I am not mistaken, it is in Section 4.1, pages 20-22, where this is addressed (there is an alternative security proof in Section 5, but I am focusing on the one in Section 4). In this section, security is proven by reducing to the security of ECDSA (i.e., if we have an attacker $A$ that breaks the 2-party ECDSA, then we can build an attacker that breaks ECDSA).
Specifically, for the matter at hand, the strategy is to have the simulator simulate $P_1$ aborting at some random point. This makes the simulated view be indistinguishable to the real view with non-negligible probability, so we can use $A$ to break the 2-party ECDSA, then use this to break ECDSA, and so on.

Now, my doubt is: how does this demonstrate that a malicious $P_2$ is prevented from learning the LSB of $x_1$ if the hypothetical attack mentioned in Section 3.2 were possible. Or does this imply that, in practice, we would actually need to force $P_1$ to abort randomly? In that case, is this realistic in practice?

In real life, $P_1$ of course does not abort randomly; this would make no sense. The idea is as follows. Assume that a cheating $P_2$ can forge a signature with probability $\epsilon$ when interacting to obtain $p(n)$ signatures are signed with the system. Now, if $P_2$ cheats then there is a first place where $P_1$ aborts. An adversary for ECDSA can simulate everything and guess where this first abort happens and will be correct with probability $1/p(n)$. This implies that the adversary for ECDSA can forge a signature with probability $\epsilon/p(n)$. Since ECDSA is assumed to be secure, this means that $\epsilon$ must be negligible.


Security implications of slow-by-design hashes on relative security vs. hash size Would it be true to say that that one can get away with much smaller cryptographic hashes if the hashing algorithm is slow and expensive by design?

Example: let's say you want 128-bit hashes. This is considered insecure today since this is small enough to be able to be attacked via things like rainbow tables (if you have a ton of storage) and any partial break of the algorithm is more likely to be devastating. But what if your hash function is designed to be slow and expensive? An example would be balloon hashing or franken-hash algorithms like CryptoNight.

Slowing down the hash function makes each iteration expensive to compute, so theoretically it seems that one can get away with smaller security margins. For example let's say you use a partial break or a rainbow table to reduce the hash's strength to 2^64 bits. You still have to evaluate it 2^64 times. If each evaluation takes an average of 100ms even on very fast hardware, this still leaves millions of years to search for a collision even if you have a million CPU cores to work with. The same line of reasoning seems to apply to birthday and multi-collision attacks.

Obviously the wildcard here is ASICs, but techniques like memory hardness or intentional algorithmic complexity can reduce the advantage presented by an ASIC vs. a general purpose CPU (and greatly increase the design and production cost of an ASIC). An ASIC that speeds this up 1000X still takes many millions of years per ASIC for a brute force search. You'd need hundreds of millions of ASICs to search 2^64 hashes in reasonable time, which of course assumes you have some way of halving the security of a 2^128 hash.

Is this reasoning basically correct?

This builds on a previous question I asked about Grover's algorithm. Grover's algorithm can (only in theory so far) roughly halve the security of a hash, but it still requires one classical evaluation per quantum search iteration. This extends the question to include classical security.

You CAN get away with using less memory if the hash is expensive. However, that does not mean you should, and it would rarely make any sense.

So why would you try to "get away with" using smaller hash functions? You could save some storage space, which is definitely appealing. However memory is cheap, and using larger hash functions adds more security, it also has the benefit of being more future proof than a smaller hash.

But in the end, it depends entirely on your data. There are many uses for hash functions, and using a slow hash with ASIC preventative measures for a checksum would be silly. However, if you are storing passwords in a secure database, you would want to add a salt and/or pepper and use an ASIC-safe slow hash.

I also want to address a couple misconceptions:

Your example does not make much sense. A rainbow table is a set of pre-computed hash chains for some expected plaintexts. This means that you could compute a rainbow table for a 1024 bit function for a small factor more memory than a 128 bit function. And if you add a salt to all of your data, it becomes infeasible to use a rainbow table at all.
You say "any partial break of the algorithm is more likely to be devastating" Why is this? A flaw in a hash algorithm is a flaw. Assuming the search space is reduced, the more bits you have the safer you are; however this does not necessarily mean any flaw is "devastating", a flaw is nearly as likely to be devastating as in a larger hash function.


How to Compute C^2 in AES MixColumns Matrix? In mix Columns we have:

$$C(x) = \{03\}X^3 + \{01\}X^2 + \{01\}X^1 + \{02\}$$

In Viktor Fischer's Paper on MixColumn and InvMixColumn Resource Sharing, in page 2, Equation 8, it's been said that $C^2(X)$ can be computed as follows:
$$C^2(x) = \{04\}X^2 + \{05\}$$
Can anybody explain why is that?

hi Ruby i know how it comes. But before that i assume you have a good knowledge of finite field.

Actually, it's the problem of how to calculate $$C^2(x) = (\{03\}X^3 + \{01\}X^2 + \{01\}X^1 + \{02\})^2$$. Becuase the character of $K$(as in the paper) is 2, so $$C^2(X)=(\{03\}X^3)^2+(\{01\}X^2)^2+(\{01\}X^1)^2+(\{02\})^2$$.  But you have to know the meaning of $\{03\}$  $\{02\}$ and $\{01\}$. They are elements of $F_2^8$. For example $\{03\}$ stands for $x+1$, so $(x+1)^2=x^2+1=\{05\}$. Like this we get:$$C^2(X)=\{05\}X^6+\{01\}X^4+\{01\}X^2+\{04\}$$
Next as $R=K[X]/(X^4+1)$, you have to put them in $R$ by  $mod(X^4+1)$$(X^j mod (X^4+1)=X^{j mod  4})$. so we get:$$C^2(X)=\{05\}X^2+\{01\}+\{01\}X^2+\{04\}$$.
Next as $\{05\}=x^2+1,\{01\}=1,\{04\}=x^2$, so when we 'add'(this add in the finite field means XOR)then we get:$$C^2(x) = \{04\}X^2 + \{05\}$$


How is an AES Encrypted Message Decrypted with Random Padding? One thing I was surprised to learn about AES is that random padding can be added to the message to make it a multiple of block size. What I can not wrap my head around is how this random padding can reliably be removed from the message upon decryption, given that if it is generated by a truly random process, the recipient has no information about it.

What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?
Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?

What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?

You can do random padding with AES, but you'd have to reserve say the very last byte to tell how many bytes of padding were added.

For example, for a 4 byte blocksize cipher, say your message is 04 (in hex). To make it 4 bytes we need to add three bytes, so we add two bytes of random padding, then one byte 02. So what would really be fed into the block cipher would be 04 ac 92 02. The recipient needs to know that this scheme is being used. They would then read the last byte and know that two bytes of random padding were added. Those bytes would be removed and the final message 04 would be returned.

I believe most people using AES do not use random padding though. Deterministic methods are just as secure. RSA, however, needs random padding for security.

  Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?

Yes. Otherwise it would be impossible to strip off the padding. This information does not need to be secret and can thus be specified in a protocol field or upon handshake.


Should I use XTS or GCM to encrypt my hard drives? I want to start encrypting all of my hard drives, but I don't know whether to choose XTS or GCM mode. Why is it that XTS is recommended (since the most websites I visit use GCM in their HTTPS connection)? So my question is: should I use XTS or GCM, and why is one better than the other?

XTS is designed so that the plaintext and ciphertext sizes are the same. This is "needed" for disk encryption in order to preserve the sector size. However, when you are encrypting your disk at the file level, this is a completely irrelevant issue. Also, XTS is not "ideal" in the sense that it's not truly a wide block cipher (defined as a pseudorandom permutation over the block size). It's a standard which is actually somewhat a compromise.

If you are encrypting at file level, then I would recommend an authenticated encryption scheme. GCM is of course possible, but you need to make sure that you have a unique IV and you need to make sure you keep within the bounds. It is possible to use a nonce-misuse resistant version as well; this is highly recommended since nonce reuse is not disastrous (at the very worst will reveal that two files are identical, but if the file includes the path name then this can't happen). You will probably be concerned about speed, but good implementations are well under a cycle a byte and so cost nothing compared to the cost of reading/writing to disk.


Securely start a client server connection without ssl/tls NOTE: Pardon my ignorance of encryption, I learned about these concepts today
Going to rephrase this question, but I think I already have fine answers provided.  I need to have a block of data containing a message (user imputed) that is included in what I want to encrypt.  I also need to have some means of authenticating the user, such as a password.  The password will most likely be hashed for extra security.  I am considering using a RSA public and private key pair of which the attacker can know, but wont be able to use, as he/she will need to authenticate themselves with a password of which they cannot know.  Both the message (which I do not want the attacker to know) and the hashed password will be included inside the RSA encrypted data block (aka: RSA('message block', sha256('password')) ).  Right now, my main question is if this is secure or not.

if you want to use a password, SRP is probably a good choice.
alternatively, you could use ECDHE with ECDSA or RSA keys.
you should also use a MAC of some sort if you're using CBC (and encrypt then MAC). GCM or OCB would be much better choices.


Linear Cryptanalysis of hash function I've studied linear cryptanalysis, but i don't think I have it very clear.
I've the following doubt:
I've constructed a "cryptographic" hash function for an exercise, and now i want to show summarily that is secure from "linear cryptanalysis".

My idea was simply to create a linear approximation like this:

X_1 XOR X_2 XOR ... X_n XOR Y_1 XOR Y_2 XOR ... Y_m

which involves the input and the output (whose bits X_i, Y_j respectively, are XOR together) of my hash function, and for a very large set of random input (about 1000000), to count how many times the result of this operation was 0, and how many time was 1. Then if the number of 0 does not differ much from the number of 1 (i.e. with probability about 0.5 the result is 1, and with probability about 0.5 the result is 0), my function it's ok, otherwise it's not secure.

My doubt is: Is this method right? What bits of the input and output i have to include in the linear approximation, all?

PS: I don't have to do linear cryptanalysis but only a very general analysis based on it.

As @MaartenBodewes stated in the comments, just one method of cryptanalysis cannot show a hash function is secure.

Your question

  My doubt is: Is this method right? What bits of the input and output i have to include in the linear approximation, all?

has the following answer. In general, while doing linear cryptanalysis we try all possible subsets of input and output bits and look for biases in the resulting expressions. Thus there is a total of $2^{n+m}-1$ possible expressions to check.

Let $(a_1,\ldots,a_n) \in \{0,1\}^n,$ and $(b_1,\ldots,b_m)\in \{0,1\}^m.$ Then except for the case $(b_1,\ldots,b_n)=(0,\ldots,0)$ all the following expressions
$$
a_1 x_1 \oplus a_2 x_2 \oplus \cdots \oplus a_n x_n \oplus b_1 y_1\oplus \cdots \oplus b_m y_m
$$
need to be computed and their biases tested. We rule out $(b_1,\ldots,b_n)$ being zero since then then we're not computing anything interesting about the output of the hash function, but it is OK to let $(a_1,\ldots,a_n)$ zero since that tests the overall balance of the function, regardless of input.

In terms of more general analysis, there are obviously many other techniques, differential cryptanalysis, looking for collisions, looking for inverse images, etc. the latter two being directly related to hash function goals.


File encryption with one keypair? I'm working on a program that uses an ECC keypair in a (password protected) PKCS12 file (.pfx) to encrypt files. I like this method because I think it will be higher security (using ECDH to negotiate the key) and more easy to use (one PIN for all files). How I'm going about this is by using the public and private keys of the same certificate to negotiate a secret using ECDH. A SHA-256 of this secret is used every time to encrypt a random generated key just for that file. The program outputs file.enc, kek.iv, kek.enc, file.iv all in a zip for the encryption portion of the program. file.enc is the ciphertext of the original file, kek.iv is the IV used to encrypt the file-specific key (session key if you will). kek.enc is the ciphertext of the file-specific key that has been encrypted with the shared secret. And by "I'm working on this program", I mean I already wrote the program but it's not working and I'm starting to question the fundamental logic.

My question is, is it even possible to get the same ECDH secret every time between the same public/private key pair so that it can be used to encrypt files? If not, how can I achieve the goal of encrypting files with one keypair?

Btw I'm trying to implement Suite B so I'm using ECC(P-521) keys for ECDH and AES-256/GCM with BouncyCastle

The ECIES (Elliptic Curve Integrated Encryption Scheme) should be used for encrypting file and data. ECC(P-521) is over kill, P-256 is enough secure and more efficient.


How to compute the inner product on encrypted vector by using a third party? I want to compute the inner product of two vectors on a third party, i.e.
$f(x) \cdot f(y) = x \cdot y$
where $x$ and $y$ are two vectors. However, I do not want the third party knows the real value of the two vectors.

So is there any encryption scheme that can do this?

One possible way to calculate the inner product is by using fully homomorphic encryption schemes.
First, you encrypt each vector $$x = (x_1,x_2,\ldots,x_n), \quad y = (y_1,y_2,\ldots,y_n)$$
with your public key $$X = Enc_{pub}(x) \text{ and } Y = Enc_{pub}(y)$$ where $$X = (X_1,X_2,\ldots,X_n), \quad Y = (Y_1,Y_2,\ldots,Y_n)$$ and $$X_i = Enc_{pub}(x_i) \text{ and } Y_i = Enc_{pub}(y_i)$$
Now, you can send $X$ and $y$ to the server to calculate the inner product, IP, under FHE.
$$IP = \langle X,Y \rangle = X_1 \odot  Y_1 \oplus X_1 \odot Y_1 \oplus \cdots \oplus X_n \odot Y_n$$ when the server send you back the result, use your public key to decrypt the result. Where $\odot$ represent homomorphic multiplication and $\oplus$ represent homomoprhic addition.
$$res = \langle x,y \rangle = Dec_{priv}(IP)$$
Note 1 : You have to assume the server semi-honest. Here, there is no integrity against a malicious server.
Note 2 : For the implementation, you can use TFHE: Fast Fully Homomorphic Encryption over the Torus or Helib
Note 3 :  You can also use 2DNF by Boneh et.al, which support one multiplication but many additions. This work is enough for the calculation of the inner product under 2DNF encryption. The decryption, however, is not straightforward. As noted on page 4 of the paper;

To recover $m$, it suffices to compute the discrete log of $C^{q_1}$ of base $\hat{q}$
Note that decryption in this system takes polynomial time in the size of the message space T.
Therefore, the system as described above can only be used to encrypt short messages

Note 4: there is an article titled as Design and Implementation of Low Depth Pairing-based
Homomorphic Encryption Scheme by Herbert at. al that that

can handle the homomorphic evaluation of polynomials of degree at most 4.
and uses Elliptic Curves. And, they have an implementation posted on github.


How to calculate the branch number of a linear mapping? Is there an efficient algorithm which can be used to determine the branch number of any given linear mapping?

As explained in the answer to the question here
the branch number of a linear mapping
$$
A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x
$$
is the minimum weight of the linear code generated by the matrix
$$
G=[~I~|~A].
$$
For an arbitrary matrix $A$ this problem is NP hard, i.e., very hard. For structured matrices like the MDS matrix in AES the answer is known, see the link.
For the hardness result see Vardy's paper "the intractability of computing the minimum distance of a code". It or a related version is also available on citeseer. Since this code is linear minimum distance equals minimum weight.
https://ieeexplore.ieee.org/document/641542


About the Rijndael/AES sbox polynomial (subBytes) I've recently read a question about the irreducible polynomial behind the subBytes() operation in the Rijndael that has awakened and old curiosity I have:

Why $\,m(x)$ was chosen as $\,x^8+x^4+x^3+x+1$?

In the comments in the referenced question it has been mention that it was the first that fulfilled the task (be irreducible to have a finite field instead of a ring, isn't it?). Yes, it's true, but was this that simple? Would be useful any other property?

Let's say, one binary curiosity it has, is a Hamming Weight of $\,\lceil\frac{n}{2}\rceil$ where $n$ is the length in bits. This is a balanced weight that perhaps means nothing or maybe something.

Thinking in the maths behind this operation, with other sizes ($w$) than 8 bits (per word), let's say $w=7$ the first that does the job is $x^7+x+1$ and the first with a balanced hamming weight $(x^7+x^4+x^3+x^2+1)$ is the fifth that does the job.

I'm not seeing any particularity between the two field that they build, but exists?

I'm not seeing any particularity between the two field that they build, but exists?

First off, one basic truth about finite fields is that there is at most one finite field of a given size.  Given that both $x^7 + x + 1$ and $x^7 + x^4 + x^3 + x^2 + 1$ are both irreducible, they both generate the same finite field.  Where they differ is the representation; how they represent specific GF(128) field members as bit patterns.  For example, the member 0x02 in the $x^7 + x + 1$ representation is the same abstract element as 0x1d in the $x^7 + x^4 + x^3 + x^2 + 1$ representation.

So, the question becomes "which representation would have an advantage within AES"?  The answer to that would be "both are equally good"; as I discuss in this answer, both representations are equivalent; the rest of the AES structure can be adjusted so that the AES cipher as a whole acts equivalently.

So, the reason that $x^8 + x^4 + x^3 + x + 1$ was chosen was because it was the lexically smallest; they had to pick one, and there was no reason one polynomial representation was better than any other; it was simply an arbitrary choice.


How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$ Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form?

This is actually a homework problem with a hint that if a $n = p^a$$q^b$ then exactly half of the elements in $Z_n$ with jacobi symbol +1 are quadratic residues mod n and we assume that initially verifier knows a quadratic non-residue x with jacobi symbol +1.

I stuck there because it seems extremely difficult to convince Verifier that n is of given form. It is not simply like after Verfier sends a challenge number to Prover and Prover shows that he knows the fact that if the challenge number is QNR or QR. For me to convince Verfier all jacobi +1 elements have to be generated in $Z_n$ and Prover has show that exactly half of them are QR. (Assume that Verifier can generate with x itself thus it does not violate Zero knowledge. But I am not sure if it is easy(polynomial time consuming) to generate all Jacobi +1 elements yet. Well it is true that if we let $z = r^2$ for a randomly picked r from $Z_n$ then $y = r^2x$ is also a QNR with jacobi symbol +1... So finding another QNR with jacobi symbol +1 is easy for verifier... ) But To show "exactly half" then Prover will need to show which one is QR and which is are QNR then it will violate Zero knowledge property since V is not suppose know that. But any other way to show "exactly half"?

Any hint or help is greatly appreciated. Thanks!

Actually, it is not necessary for the prover to show that "exactly half" of elements with Jacobi symbols being +1 are, in fact, QR.  Instead, here are some hints:

Assuming that n is not of that form (and also n is not of the form $n = p^a$, which is easy test for), the probability that a random element with Jacobi symbol +1 is a QR is at most $q$ (homework assignment for you: what is the value of $q$)
If we get a value $x$ from the verifier which is a QR, how can we show in a zero knowledge way that $x$ is a QR (with probability $> 1 - \delta$)?
If the provider gives us a series of random $x$'s, and we either respond to each $x$ with 'not a QR', or 'it's a QR; here's the zero knowledge proof with probability $> 1 - \delta$', how many trials with random elements would be needed before the verify can conclude (with probability $> 1 - \epsilon$) that the fraction of Jacobi symbol +1 elements which are QR are $> q$?


Decrypting arbitrary numbers with RSA I want to construct a hash-chain where I want to share millions of small AES-128 keys with Bob over a period of time. Bob should not be able to predict the future keys if he knows the past keys. I also want to avoid having Bob storing all these keys, but rather be able to derive them so that if they know the key from time $t$, they should be able to derive the keys from time $t-1, t-2$, and so on. So, future-to-past derivation should be possible. Past-to-future derivation should be hard.

The hash-chain way of doing this is to start with a random string, hash it with sha256, say, 1 million times, and start the chain with the 1 millionth hash. This way, if Bob is at the 10th iteration of our protocol, and wants to go back to the 6th iteration, he hashes the 10th iteration key 4 times to get the 6th key.

I am wondering if we can do the same with some encryption scheme like RSA. I give Bob my RSA public key $([e, n])$. I start the chain with a large random number in the range $(2, n-1)$, and decrypt it. I am assuming that every number in this range has a valid decryption. This decryption chain can continue as many times. If Bob wants to reconstruct keys, he uses the encryption algorithm, for which he has the public key. I can use some KDF to derive the AES-128 key from this large RSA "number".

Is the RSA-chain scheme as safe as the SHA-chain scheme?

The proposed system seems to be as follows:

At generation, Alice selects odd $e>2$ and random large primes $p$ and $q$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$; computes $n\gets p\,q$; chooses random $s_0$ in $[1,n)$; and publishes $(n,e,s_0)$. She computes and keeps secret $\lambda(n)\gets(p-1)(q-1)/\gcd(p-1,q-1)$ and $d\gets e^{-1}\bmod\lambda(n)$.
For successive times $t\in\Bbb N^*$, Alice computes $s_t\gets{s_{t-1}}^d\bmod n$ and publishes $s_t$ at time $t$.
For $t\in\Bbb N^*$, anyone with knowledge of $(n,e,s_{t-1})$, e.g. Bob, can check an alleged $s_t$, by verifying that $0<s_t<n$ and ${s_t}^e\bmod n=s_{t-1}$. Alternatively, $s_t$ can be verified from $(n,e,s_0)$ by verifying that $0<s_t<n$ and ${s_t}^{(e^t)}\bmod n=s_0$.
By convention, $k_t=H(s_t)$ where $H$ is some 128-bit PRF, e.g. the low-order 128 bits of SHA-256.

Anyone with knowledge and trust of $(n,e,s_0)$ and knowledge of $s_{t'}$, e.g. Bob, can compute and trust $k_t$ for $0\le t\le t'$.
The intention is that it would be infeasible to derive $k_t$ for $t>t'$. That holds, with some degree of reduction to the RSA problem. Some arguments:

Given how it is generated, it is overwhelmingly likely that $s_0$ is coprime to both $p$ and $q$. Assuming that, it follows that for fixed $t$, each $s_t$ is uniformly random in $\Bbb Z_n^*$.
Knowledge of $s_{t'}$ subsumes knowledge of earlier $s_i$ with $i<t'$.
Finding $s_t$ from $s_{t'}$ for $t>t'$ is solving the RSA problem for public exponent $e^{t-t'}$, or equivalently public exponent $e^{t-t'}\bmod\lambda(n)$, which itself takes quite random-like values in $\Bbb Z_{\lambda(n)}^*$.


Random Permutation polynomial I need to know, please:

(1) Is there anyway to pick uniformly at random permutation polynomial in a field of prime order?

(2) Are there many permutation polynomials in a field?

(3)  In a finite field of q elements how many bijective polynomials exist whose degree are smaller than d ?

***Indeed has the permutation polynomial used in this way in cryptography to generate uniformly random value? If yes, where?

Are there many permutation polynomials in a field?

For a field $F$ of order $q$, every function from $F$ to $F$ is expressable (uniquely) as a polynomial of order $q-1$.  $q!$ of these will represent permutation polynomials.

Is there anyway to pick uniformly at random permutation polynomial in a field of prime order?

Given a function from $f$ with $f(x_i) = y_i$, it's not difficult to write the polynomial that generates it.  It's just a sum of terms like $(x y_0/x_0)(x-x_1)(x-x_2)(x-x_3)... + (x - x_0)(xy_1/x_1)(x-x_2)(x-x_3)...$.  If you are generating the permutation on the fly, you can compose simpler permutation polynomials.  I don't know if there are more efficient methods.