In which situations is a length-extension attack a problem?

The archetypal situation where the length-extension property becomes problematic is when ones builds a Message Authentication Code from a hash function as $$\textrm{BadMAC}(K,M)=\textrm{Hash}(K||M)$$ where $K||M$ is the concatenation of the Key and the Message.

The length extension property then translates directly into the capability to forge a different message, starting as the original, for which computing the $\textrm{BadMAC}$ is trivial.

In practice, that could allow adding an appendix to a text protected by $\textrm{BadMAC}$ (after a short rash of garbage in most cases, but often it could be invisible when printed). Also, that could allow extending the size of a short signed message so that it creates a buffer overflow after its integrity is checked using $\textrm{BadMAC}$.

HMAC is secure against that; and then more.

Another (artificial) example could be when it is asked the hash of increasingly long messages (with precisely the wrong content) as a Proof-Of-Work: one user knowing the hash constituting the POW of a user could abuse that into another POW indicative of slightly more work.


Is the following 4 digits code generator secure and non-deterministic?

I'm assuming that RNGCryptoServiceProvider is an interface to a properly implemented CSPRNG.  If so, its output should be impossible to predict (for an adversary with any practical amount of computing power, and no access to the internal RNG state) and uniformly distributed (i.e. every $n$-bit output is generated with the same probability of $1/2^n$).

Thus, assuming that your CSPRNG isn't broken, as far as the attacker is concerned you're effectively generating truly random 4 × 8 = 32 bit random numbers and then applying a known function (reduction modulo 10,000) to map them into strings of four decimal digits.

The only possibly exploitable source of bias is therefore the non-uniformity of your reduction function: if the function maps more of the 32-bit random inputs to some 4-digit codes than to others, an attacker will know that those specific 4-digit codes will be more likely on average, and can optimize their attack to try them first.

So, how biased is your modulo reduction, then?  It turns out that, while it's not perfectly unbiased, it's as close to unbiased as any map from 32-bit numbers to 4-digit codes can be.

Since the number of possible outputs (10,000) does not evenly divide the number of possible inputs (232 = 4,294,967,296), there must necessarily be some bias.  A perfectly unbiased reduction would have to map 429,496.7296 inputs to each output, but that's obviously not possible — the number of inputs mapped to each output must be an integer.  So at best, we can arrange for some outputs to be generated by 429,496 inputs and some by 429,497 inputs, making the latter ones about 1.0000023 times as likely to occur as the former kind.

The modulo reduction indeed achieves precisely this.  Specifically, using your generation scheme, the codes 7295 and below are about 1.0000023 times as likely to occur as the codes 7296 and above.

For all practical purposes, this bias is completely negligible.  Certainly, it won't be the weakest point of your authentication system, at least not compared to the obvious weakness that, regardless of how carefully you generate the codes, an attacker has a one-in-10,000 chance of getting the code right just by guessing randomly.

(If you did wish to eliminate even this tiny amount of remaining bias, you could either generate even more input bits for each code (e.g. 64 bits, for a bias of 1,844,674,407,370,956 / 1,844,674,407,370,955 ≈ 1.0000000000000004), or you could use rejection sampling and regenerate a new 32-bit number whenever the original one happens to be equal to or greater than 4,294,960,000 (= the largest multiple of 10,000 not greater than 232).  But, as noted above, this would surely be overkill.)


RSA public key same across all clients or different?

The full public key is usually published, not just $N$. The public key consists of $N$ and $e$ + meta data (ASN.1 encoding, object identifier for RSA, etc.). How the public key is encoded depends of course to the protocol.

If it is shared for e.g. transport security it is usually part of a certificate that also contains subject, issuer, validity period, key usuage etc. and of course the signature of the issuer over the certificate. This makes it possible not just to retrieve the public key but also to find out if the key should be trusted and how the key should be used.

Generally the public key uses the Fourth prime of Fermat (F4) as public exponent $e$. This makes public key operations somewhat faster and it allows for easy key pair generation. Some cryptographic libraries or runtimes restrict the size or value of $e$, so choosing a different value is not recommended. Still, most libraries will accept an $e$ that is, for instance, smaller than 4 bytes (i.e. $2^{32}$ for unsigned or $2^{31}$ for signed integers). Using F4 is generally not a requirement in protocols. That said, using anything different may cause compatibility issues.

Having a different $e$ doesn't affect the security of RSA, as long as it is relative prime to $φ(pq)$.

Notes:

Using 1024 bit RSA is not recommended anymore. Using a 2048 bit or higher key size is highly recommended.
$N$ directly depends on the two (or more) random primes used to generate the key pair so $N$ is always fully unique, making the public key fully unique - regardless of $e$. A hash over $N$ is generally used as key ID or fingerprint of the key pair. $N$ is part of both the public- and the private key.


The conventional ways to tackle similar problems involve trusted processors. That is, trusting that non-compromised processors

Can keep secret the data they manipulate (including instructions, keys)
Work without error, neither miss-executing instructions, nor correctly executing instructions which have been incorrectly designed.
Authenticate ingoing data (including instructions) as coming from non-adversaries and non-compromised processors. This is performed with Message Authentication Codes or Digital Signatures.
Can exchange data in encrypted form.
Initially contain at least an appropriate secret adversaries do not know, a set of authentic instructions, and perhaps a unique identifier.

Note: from an academic standpoint, authentication and encryption are separate functions: the later aims at confidentiality only. However authenticated encryption can provide data confidentiality and integrity, and a fragment of the question makes senses only for encrypted implying integrity too:

  if both data and processor instructions are securely encrypted, then processors can be trusted due to an inability to decrypt said information.

With the above assumptions, it is at least theoretically possible, with conventional networking and distributed computing techniques, to come out with instructions that will perform a computation in a distributed manner, and resist all adversarial attempts to produce an incorrect result that pass an authentication. Adversaries, and compromised processors (without the appropriate secrets) can't produce anything that non-compromised processors and users will accept. In theory, the worse an adversary can do is remove enough processors and suppress enough messages that no result will ever come out. It might even be possible to prove that a correct result will eventually come out if enough non-compromised processors (and their communication links) remain. In practice that is uneasy (in particular errors tend to creep in all but tiny list of instructions).

Ensuring confidentiality of instructions and data is even harder, including in theory. In particular, encryption of everything manipulated is not enough, because traffic analysis (measuring time of transmission and length of encrypted data exchanged) has the potential to leak what is performed, including data.

Despite these difficulties, modern distributed computing systems use trusted processors and achieve some level of security. One important technique that helps is layered security, where the practically inevitable security failure of a processor or set of instructions (due to bugs) is isolated as much as possible. That's a reason to use asymmetric cryptography (which aims to insure that compromise of a processor does not compromise the keys of other devices), and operating systems which attempt to isolate processes (with a useful level of success).

If on the other hand we make lesser hypothesis on the processors, we are moving into poorly charted territory.

As pointed in comment, potentially homomorphic encryption can ensure that non-trusted processors perform some computation but can't leak what they compute. It is also theoretically possible to ensure that if a rogue processor manages to alter the computation, the result fails an integrity check, as with trusted processors.

However homomorphic encryption tends to come at extremely high computational overhead, even without integrity thrown in. Making it feasible at all for simple common tasks is a research topic, and has been for long enough that many IT architects are tired. And I don't know if distributing homomorphically encrypted computation with some quantified level of tolerance to adversarial fault is even a research topic yet.


Is having AES tables on a distinct physical page enough to avoid cache timing attacks?

No

You are misunderstanding how such attacks work. It's not that your page gets shared to some attacker process. Attacker might not even be present on your computer, only measuring time over internet.
Such attacks only depend on fact that if you access index 5, then every next access to index 5 will be faster. It doesn't require any method to remove data from cache (it will go away on it's own), but those can make attack faster.

For example here is attack that only used a server that included a cycle-exact time. No attacker program was present on victim machine.

As a side note: When process is attacker running as a normal-privileged process, it has access to all other normal-privileged processes in many OSes (for example Windows), so attacker can simply read key.


Usage of twists at pairing-based cryptography

I'm not sure I understood your question, but... twists are used to improve performance. In your example, without twists, $G_2$ is $E(\mathbb{F}_{p^{16}})$. With a quartic twist, you can use $E'(\mathbb{F}_{p^{4}})$, which is much more efficient (the reason for this is that the homomorphism $\Psi$ maps the point coordinates to sparse elements of $\mathbb{F}_{p^{16}}$, i.e. with a lot of zero coefficients, which can be multiplied much faster by ignoring the internal multiplications by zero).

The splitting of the scalar $m$ into $m_1, m_2$ is known as "GLV method". While it is used to speed up point multiplications, as far as I know it can't be applied directly to the pairing computation. But it can be used for pairing-based schemes that use point multiplication along with the pairing computation.


Why does Encrypt-Then-Sign not yield a CCA-secure public-key encryption scheme?

I am not sure how the IND-CCA experiment in this case works.

Well, it doesn't really. There are no verification keys designated as such in the CCA experiment and there is no designated sender in the definition of a public key encryption scheme at all.
So, the only way to communicate to the receiver who supposedly encrypted a ciphertext would be to put it in the ciphertext itself. However, the encryption process takes as input only the encryption key and the message. So where is the signing key going to come from?
The answer is: Either it needs to be an input, in which case what you have is no longer even syntactically an encryption scheme, or you could generate a fresh keypair every time you encrypt. But since those would not be bound to anything this would be useless.

How can an adversary use this property to win the IND-CCA security experiment?

Choose two arbitrary messages $m_0\neq m_1$ and output them as a challenge. Receive the challenge ciphertext $C^* = (c^*,\sigma)$ where $\sigma$ is a signature on $c^*$ under some key which we will have to assume that the receipient magically knows.
Generate a new keypair, sign $c^*$ again, resulting in $\sigma'$ and ask the challenger to decrypt $C'=(c^*,\sigma')$. Since $\sigma'$ is valid, and therefore $C' \neq C^*$ is distributed identically to a ciphertext honestly generated by the attacker we will receive back $m_b$, thus breaking CCA security.


PBKDF2 (as defined by RFC 2898) is a function of the form

$$DK = \text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$$

In most practical use cases, the $\text{PRF}$ is $\text{HMAC}$ instantiated with a Merkle-Damgård hash function such as $\text{SHA-1}$. The time to compute $\text{PBKDF2}$ is roughly linear with the iteration parameter $c$, all other things being equal. The output $DK$ has $dkLen$ bytes, and can be thought as a random-like function of $Salt$ dependent on $Password$, or vice versa.

When used to manage passwords, $c$ and $dkLen$ are typically assumed public; $c$ from 1000 to 100000 is common (much more tends to be taxing for normal use). $dkLen$ could be 16 (or other value making it practically impossible that a particular $DK$ is reached by chance). $Salt$ typically depends on the username, and should also include a server-unique value, preferably secret (at least in part). Normally, neither this secret, nor $DK$ values, should be accessible to an attacker. However PBKDF2 is here to act as a second line of defense should this information leak, and therefore the standard assumption when considering an attack using PBKDF2 to protect passwords is that all $(DK,Salt)$ pairs have leaked (as well as $c$ and $dkLen$); again, that itself should be avoided inasmuch as possible (which is not much more than it is possible to prevent an adversary from accessing an unencrypted backup of the system; notice that if an adversary somewhat can pwn the system, that's at least equivalent, and may give more direct ways to get at the passwords).

With these assumptions (and constant $c$), the best known attacks basically try various $DK,Salt,Password$ combinations, computing $\text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$ until that matches $DK$: this will reveal an acceptable password for the username extracted from $Salt$ on the system attacked, which will also be the original password with overwhelming certainty for common $dkLen$ (perhaps allowing to attack that user on other systems where he or she uses the same password, or a similar one). For large $c$, the attack duration is dominated by the evaluation of $\text{PRF}$ at least $c$ times for each $DK,Salt,Password$ tried.

If the passwords are random and equally likely among $N$ (e.g. consist of $n$ symbols each chosen randomly among $m$, leading to $N=m^n$), having many $DK,Salt,Password$ does not help, and an attack is expected to find the password of a given user with odds $p$ after no less (and about) $N\cdot c\cdot p$ evaluation of $\text{PRF}$; that's an expected $N\cdot c/2$ $\text{PRF}$ evaluations. For example, with the iteration count $c$ set to 100000, $m=26$, $n=9$, and $\text{PRF}$ HMAC-SHA1, an attack is expected to require about $2^{60}$ evaluations of the round function of SHA-1. That's about the number of hashes performed every 5 second for the purpose of bitcoin mining by mid 2014 according to that source, or what could be done by a 2000-core general purpose computer in a year of operation. So with the iteration count set to 100000, the expected duration for an attack ranges from little for a resourceful adversary doing the job with ASICs or FPGAs, to somewhat too much for the average guy with a bunch of PCs.

If the passwords are chosen by users, the best attack tries the password from most likely to least likely, for each $DK,Salt,Password$ available. For 8 letters perhaps 1% of users will pick password as the password, and even for 9 letters, with a few hundred users, finding a valid $(username,Password)$ will be trivial for any adversary worth consideration after $DK,Salt,Password$ leaked.

There are better alternatives to PDKDF2; notably scrypt, which requires a parameterizable amount of RAM to perform the calculation, making ASICs and FPGAs much less practical; and can be distributed on multiple cores, allowing a corresponding increase in the iteration count (thus security) in some setups. As pointed in another answer, that's an active research area.


Pseudo Random Generator (PRG) from Rabin function


Teach myself an uncommon written language like Esperanto or Klingon which very few people can read

That's not a bad idea. Although if you had to choose one I'd personally advise you to use Klingon instead of Esperanto. The amount of worldwide Esperanto speakers is about 1 in 4000 (0.03%), whereas Klingon is spoken (fluently) by only 20 - 30 people.

The goal of Esperanto (as you might know) was to introduce a universal language with the intent of making the learning process fairly easy, some might even say that Esperanto is very easy to learn. Many words are derived from European languages:

  [...] took most of [...] Esperanto root words from languages of the Italic and Germanic families, principally Italian, French, German,
  Yiddish, and English. A large number are what might be called common
  European international vocabulary, or generic Romance

  - Esperanto etymology (Wikipedia)

It's likely that European speakers can recognize some words from Esperanto and maybe in rare instances connect the dots to gain contextual knowledge of a text.

Additionally, there are numerous Klingon & Esperanto online translators (if anybody should get hold of a text).

  Replace the symbols I use to write letters with alternatives, like Elian-script

That's probably a good method. If you do this every day it should be fairly easy for you to learn reading and writing in a cipher and obviously you can invent such a cipher yourself.

However, I have to say that it's unlikely to go beyond a monoalphabetic substituition cipher. Polyalphabetic substituition ciphers are rather hard to do fast by hand / mentally for numerous reasons.


If the PSK is known, is it possible to decrypt traffic from other clients in a WPA2 wlan network?

Curiously, the answer is »Yes« to both questions.

Each client (STA) establishes a different pairwise transient key (PTK) with the access point (AP) for each session, but this PTK is derived from the pairwise master key (PMK). And if you are using a pre-shared key (PSK, usually derived from a password entered by the users), this PSK is used as the PMK.

The derivation of the PTK uses a pair of nonce values sent by both STA and AP in clear text as the first two steps of a 4-way handshake, as well as their MAC addresses (which are public anyway) and the PMK (all hashed together with a hash function).

So, listening on those first two handshake messages and knowing the PSK allows an attacker to listen to any messages between AP and STA, as well as impersonate one or both to do a man-in-the-middle attack.

The standard IEEE 802.11-2007 contains a note about this (page 190, in the PDF on page 239):

  NOTE—When an ESS uses PSKs, STAs negotiate a pairwise cipher. However, any STA
  in the ESS can derive the pairwise keys of any other that uses the same PSK by
  capturing the first two messages of the 4-Way Handshake. This provides malicious
  insiders with the ability to eavesdrop as well as the ability to establish a
  man-in-the-middle attack.


When the output of the hash function is $n$ bits, then there are $2^n$ possible outputs.

For a preimage attack you are given a hash $h$ and you need to find a message $m$ where $h = H(m)$.

Since there are $2^n$ possible outputs, the probability of guessing an input that that maps to the given output is $\dfrac{1}{2^n}$. So on average you need to try $2^n$ preimages. That is where the $2^n$ complexity comes from.


You have listed two properties for something to be a PRF, efficiency and pseudorandomness.

The function $F'$ is clearly efficient as $F$ is efficient and $F'$ calls $F$ in just about every case. The one case where it doesn't is a very easily computable case too.

So, that leaves pseudorandomness. What that property is basically saying is imagine you are given a black box. You can feed it inputs (the x and k values) and see the outputs. If there exists a probabilistic polynomial time (PPT) algorithm that can, given the outputs, decide whether or not the black box implements $F'$ vs a random function, you do not have a PRF. On the other hand, if such a PPT algorithm does not exist, then you do have a PRF.

So, ultimately, the question is asking whether or not you can construct a PPT algorithm that can distinguish the outputs of $F'$ from outputs of a random function. If you can construct such an algorithm (fairly easy in this case), then you have proved that it is not a PRF.

Let's suppose, however, that the problem were setup differently and in fact $F'$ were a PRF. How would you prove that? You can't go through every possible PPT algorithm and show that it cannot distinguish outputs of $F'$ from outputs of a random function. Instead, you would assume that $F'$ is not a PRF and show how this would lead to a conclusion that $F$ is also not a PRF. In other words, a proof by contradiction.


Can elliptic curve point common factors be detected?

Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field?

(Actually, you mean the size of the group)

Technically, the answer is "yes, it is easy to determine that".  The easiest subcase is if $G$ (and hence $X$ and $Y$) belong to the large prime subgroup of x25519; then the rule is "unless Y is the point-at-infinity and X is not, the answer is "yes".

That is, there will always be an $a$ such that $X = aY$.

It's a little trickier if $G$ generates a larger subgroup, but it is still easy (it might take a little computation on the attacker's part).

Of course, the fact that it's always true (whether or not you consciously generated such a relationship between $X$ and $Y$) means that the attacker can't deduce anything from that information.


I think my definition of 'simple' is different from yours. : )

  Are there any evident attacks on it?

It's vulnerable to man-in-the-middle attacks, like:

Step 9: M replaces $\langle b_{U}, v'_{U}, h'_{U} \rangle$ with $\langle b_{U}, v_{M}, h_{M} \rangle$, where they've calculated their own random bit string and used their own key to encrypt it. Now M can log in as U (and U can't).

That means it's probably no more secure than if you left out the server identification in step 4. and all the related $v_S$ and $h_S$. The identification isn't strong, because there's no authentication for any of the other data exchanged.


Can we develop a working asymmetric crypto message protocol without an asymmetric encryption algorithm?

Use DLIES, which is essentially Diffie-Hellman with an ephemeral sender key. Assuming you know the receiver's public key, that will cost no extra round trips.

The sender does:

(eph_sender_private, eph_sender_public) = Generate_Key_Pair()
shared_key = SHA-512(Diffie-Hellman(receiver_public, eph_sender_private))
ciphertext = Encrypt(shared_key, message)
encrypted_message = (eph_sender_public, ciphertext)

The receiver does:

(eph_sender_public, ciphertext) = encrypted_message
shared_key = SHA-512(Diffie-Hellman(eph_sender_public, receiver_private))
message = Decrypt(shared_key, ciphertext)

Where Encrypt is authenticated encryption build from AES and SHA-512. For example you could follow the RFC Draft Authenticated Encryption with AES-CBC and HMAC-SHA which includes test vectors to minimize the risk of your messing it up.

If you feel fancy, replace the simply hashing in the shared key derivation by a proper KDF, such as HKDF-SHA-512.

To authenticate the sender, sign the message using a long term DSA key, which should be distinct from the long term DH key.


What's the most secure way to derive a key from a password repeatably?

Is there a better way to do this?

Yes there is, using tools specifically designed for this problem - namely key derivation functions (KDF). Good ones include PBKDF2 and bcrypt. A more modern, better alternative is scrypt, but it's relatively new and could use some more analysis before deemed safe.

All above mentioned algorithms take a password and a salt, as well as tweakable security parameter(s). I recommend storing a randomly generated salt (at least 128 bits) for each user in the database and passing that into the algorithm. The key used for encryption/decryption is simply the key generated. I can't give a recommendation on the security parameters - you'll have to do your own research as to what makes you comfortable.

  Also, if it isn't clear why I'm using this key to encrypt another key, my thought is that the second key is significantly more random (minimum 4500 passes of PBKDF2)

You do not have to do this with a good KDF.

  Plus it provides the potential to change the password without having to re-crypt every single user file.

Do you really want this? This means that if I managed to "hack" someone once I'll be able to read his files at any point in the future. If you still want this feature I'd suggest to store a randomly generated number (on the client side) encrypted using the key generated with the KDF (your idea) in the database. Make sure to inform your users about the decoupled password/key system in laymans terms, and give them the options to re-encrypt under a newly generated key.


Aes encryption -The relevance of static matrix in mixcolumns operation

Well, how that matrix works is important for the security properties of AES.  To see why it is important, we need to consider state differences, that is, if we consider two different inputs to AES and how they both flow through the cipher, how does those two differ in the internal state of the cipher at various places.

The important property of the mixcolumn operation is that it is a Maximum Distance Separable (or MDS) operation.  That is, if we consider two distinct inputs to a single column of the mixcolumn operation, and the two inputs differ in $A$ bytes, and if the two corresponding outputs differ in $B$ bytes, then $A+B \ge 5$.

This implies that if two consider two inputs to a single column of the mixcolumn, if those two inputs differ in a single byte (that is, $A=1$), then the two outputs will always have different values for each byte (that is, $B=4$).

If you go through how this applies to AES, that means that if round $I$, two encryptions has an internal state that differs in a single byte, then at round $I+2$, the two encryptions will have states that differs in all 16 bytes (and hence AES has wonderful avalanche).

More generally, this behavior allows us to prove strength against differential and linear attacks; in that any differential or linear characteristic will necessarily go through a large number of sboxes; the resulting probability that the differential/linear characteristic will survive all those sboxes is negligible.

All this may not be true (or, at least, would be considerably harder to prove), if we replace the mixcolumn operation with an operation that is not MDS.


How can one share information using the 'host-proof' paradigm?

Getting data from user A to user B securely generally works via asymmetric encryption. Encrypt the data with B's public key and store the result on the server. B then retrieves the encrypted data and decrypts it using his private key.

This assumes the server does not store the private key, or at least stores it in a form that can only be decrypted by the owner.


Is Indistinguishability Obfuscation Real?

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


The answer from the libsodium web site

  Only the recipient can decrypt these messages, using its private key. While the recipient can verify the integrity of the message, it cannot verify the identity of the sender.

While Bob can decrypt the message and cannot verify the identity with his public and private key pair, there is no way the Eve can determine with the only public key.

To understand the sealed box we must first see the crypto box.

Crypto Box Structure

Cryptobox encrypts and authenticates a message $m$ using the sender's secret key and receiver's public key and a nonce $n$.

$$c = box(m,nonce,recipient_{pk},sender_{sk})$$

The receiver, verifies the and decrypts the $c$ by using his secret key and sender's public key.

Sealed Box Structure

A sealed box constructed only using the public key of the recipient. The sealed box is;

$$sealed\_box = ephemeral_{pk} \| box(m, recipient_{pk}, ephemeral_{sk}, nonce)$$
$$nonce = blake2b(ephemeral_{pk} \| recipient_{pk})$$

an ephemeral private and public key pair (generated and used once) is generated and later the ephemeral private key is destroyed.

Therefore, the sealed box contains no information about the sender.
Since the sealed box can only be opened by the $recipient_{sk}$ the Eve cannot understand the recipient, too.

However, Eve can look for who downloads the message. Without it how is going to Bob know that there is a message for him? The best way to protect from this is;

Bob check himself
Bob uses Private Information Retrieval to hide the data he access.

Also, this answer for What is the difference between a sealed box and a normal box in libsodium? might be helpful.


Is there a standard padding/format for RSA Blind Signatures?

There are random oracle model security proofs for RSA-PSS and RSA-FDH.  There are standards for RSA-PSS but it requires randomness from the signer and thus does not work for blind signatures.  RSA-FDH works with blinding.

RSA-FDH might appear in some standard somewhere, but honestly "full domain hash" is kinda self explanatory to a cryptographer.  As an FDH example see  https://git.gnunet.org/gnunet.git/tree/src/util/crypto_kdf.c#n113 for the RSA code in https://git.gnunet.org/gnunet.git/tree/src/util/crypto_rsa.c used in GNU Taler.

There is afaik no standard for blind signatures per se, but you must use a full domain hash for both the message and the blinding factor, well formally the blinding factor is a FD-PRF, but that's the same code.

If you use too small a hash function for the message, then an adversary can factor message hashes, find enough colliding factors, and forge messages.   Or worse since even the basic signature scheme security proof requires FDH.  All the security proofs that protect against such "one more forgery" attacks require both FDH and the non-standard RSA-KTI "known target inversion" assumption.

If you do not use a FD-PRF for the blinding factor then you'll leak enough information with each message that an adversary can deanonymize you after well under 100 messages.

I'll emphasize:  If you have a 2048 bit RSA key n then your domain for the hash is [0,n) so you must generate a 2048 bit number r, test if it is less than n, and repeat if not.  You do not have an FDH if you merely generate one 2048 bit or 2027 bit number and use it directly.  RSA is not forgiving about this because an RSA modulus lands roughly half way between powers of two, unlike say elliptic curve group orders which are chosen very close to a power of two.


How distinct are the meanings of the terms "CSPRNG," "DRBG" and "stream cipher"?

The definitions are not all universal and there is quite some overlap.

The clearest definition is for PRG, which is the (synchronous) stream cipher model. A PRG maps a secret value to a long, random-looking keystream, so that an attacker cannot predict any part of the keystream from knowing other parts of it. For a precise definition, you can see the definition in Katz and Lindell (3.15 in my copy) or find the equivalent in some other textbooks.

Of course, there is the catch that most modern stream ciphers do not really fit just the PRG model (even if they are synchronous). They use an IV/nonce, allowing for multiple uses of the same key.
NIST defines DRBG as:

generating a sequence of bits that appear statistically random and independent
in a deterministic manner
from a seed (and possibly other inputs).

This sounds very much like a PRG, except for the other inputs, but they also mention access to an entropy source. It is quite vague and they also say that:

  A DRBG is often called a Pseudorandom Number (or Bit) Generator.

Clearly there is overlap.
CSPRNG is basically a catch-all term for random number generation that is cryptographically secure in some sense. I don't know that you will find a consensus on what it should mean. (Personally I would require things like reseeding and forward-secrecy, while perhaps also defining a way to map the bit sequence into random numbers, but those are not universally assumed.)

There are also ways of turning one of these into another, like the stream cipher -> RNG you mention, because these are after all requiring similar properties, if not exactly the same.


Attacking a cipher, not knowing what the plaintext should look like – how do you know you’ve successfully decrypted the ciphertext?

To address your first question, below are two fragments of text.  One of them is gibberish I copied from /dev/urandom; the other is a literary quotation of the same number of octets.  Each sequence of octets is written with graphic US-ASCII characters verbatim, and with control characters and non-US-ASCII octets written using \xAB hexadecimal notation.  Can you tell which is which?  (I randomized the order of fragments by flipping a coin, too.)

Kas siis selle maa keel / Laulutuules ei v\xc3\xb5i / Taevani t\xc3\xb5ustes \xc3\xbcles / Igavikku omale otsida?
\xe4xz\xfd\x11?\xbb\xfa\xeb\xb3a\x02Z\xe0\xdc_\xc3\xd3\x92\xa4ssa\x1an\xab\x1aa\x15\xa8\x02\xa5r}\xbe\x8f\xbc\n\xe5\x80\xd0B\xbeH\x17\xfex\x03\xd6\x99\x1d\xde$
\x89\xb4G\xd1\xea\xfb\x13@~\x87)\xb9\xd9\xcc\x18\x81\x01\x03$\xf23\x91\xb5c\xd0\xd1\x17\x11r\xee1"!\x03UiGB\x16\xc3{\xa0

(No cheating by knowing how to read Estonian!  We can do the exercise with a different language if you do read Estonian.)

To address your second question, suppose you didn't know it were Estonian.  It is highly unlikely that any language's orthography represented in octet strings has a uniform distribution, so you might, e.g., perform a statistical test to reject the null hypothesis of a uniform distribution, like a standard undergrad-statistician's $\chi^2$ test of bit or octet frequencies.  There is no way to make it ‘more complex’—there are already $2^{256}$ possibilities, each one having equal probability.

Finally, to address you third question, your obligation to satisfy the AES-256 contract is to provide a key chosen uniformly at random from all $2^{256}$ possibilities.  Normally you do this by asking your computer to do it for you, e.g. by calling on a hardware random number generator or by flipping a coin 256 times to seed your software random number generator.

If, however, you must deterministically derive a key from a password, then you should use a modern password-based key derivation function like scrypt or argon2.  A PBKDF is expensive to evaluate, which means the cost of testing a guess for a password is high, with some variations in the cost model—older ones like PBKDF2 consider only time cost on a sequential machine, whereas newer ones like scrypt and argon2 consider area*time cost on an arbitrarily large piece of silicon that may have many CPUs or lots of memory.  In some sense, a PBKDF behaves almost as if the password space were larger and the entropy of the password selection process were larger, because the expected cost of an attack is as much higher as if the entropy of the password selection process really were higher.


Will repeatedly applying a hash function to the prior result visit all possible hashes?

Given an infinite number of repetitions of the above, is it possible that all possible hashes will be computed an infinite number of times?

Yes, it is possible; however it is (to the best of our knowledge) extremely unlikely.  Not only would MD5 (on 16 byte inputs) be a permutation, it would also need to be a single cycle permutation.

Is it possible that given some initial message, there may be a revisiting of the initial hash just shortly after the start of the procedure

That is also possible, but again, unlikely (just not as blindingly unlikely as the previous scenario); for a random function, the probability of this happening would be circa $2^{-64}$
The most likely scenario would be that we would fall into a loop that does not contain the initial hash.
All this can be shown if MD5 is assumed to act like a random function.  Now, MD5 is not a random function, and it might have some unknown behavior that would change things.  However, from what we know about MD5, that looks unlikely.


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

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


Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted?

As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.


Is this discrete log generalization a well known cryptographic assumption?

Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime).

Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability.  Then, given a value $g$ and $h$, we can find $x$ with $g^x = h$ with nontrivial probability by:

Create random values $r_1, r_2, ..., r_n$ and $s$ between 0 and the group order (except that $s$ cannot be 0).
Compute $g_i = g^{r_i}$ and $t = h^s$.  Note that the values $g_i$ and $t$ are uniformly distributed (except that $t$ is not the identity).
Give the values $g_i$ and $t$ to your Oracle, which computes the values $a_i$ with nontrivial probability.
$x = s^{-1}\ \sum\  a_i r_i$

The only reason we needed to assume that the group order was prime was to be precise in the assumption that the elements be chosen randomly; if we relax that restriction on $t$, we can handle composite group orders as well.


How to derive a symmetric key from ECDH shared secret?

The general idea to derive keys from (ephemeral) Diffie-Hellman key agreement is to use a KBKDF - a key based key derivation function. KBKDFs are mostly ill defined with regards to what security requirements they adhere to. Fortunately creating a KBKDF isn't thought to be too hard. Using a cryptographically secure hash generally gets you a long way. You should however note that in that case the hash should not be vulnerable to timing- and other side channel attacks.
The input of a KBKDF or a hash is bits. Generally though only bytes are used as input. So you should be using the 66 bytes of the shared secret directly. Your conversion to hexadecimals likely already leaks side channel (timing) information. So the answer to the first question is: don't convert the x-coordinate at all.
You can indeed take any part of the SHA-512 hash as key. It is however more standard within the cryptographic community to take the first - leftmost - bytes of the resulting hash value. So that should answer question 2: just use the leftmost bytes as you're already doing.
If you want to be standards compliant and use a KBKDF then please take a look at HKDF.


In Zero knowledge protocols , the verifier trying to verify the validity of the prover's arguments or parameters. So according to the theory , the verifier doesn't know anything about the prover in the beginning and gain knowledge when the testing process goes along. This is a statistical approach and probability of the "truth" increases when you do more tests.

Contrary , if you using a PSK system, you have the knowledge about the prover and verification process is one time and binary(either true or false).

Yes the Zero-knowledge protocols requires more processing power and consume more time.


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

Long Version

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

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

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

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

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

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

So, no, your approach is not secure.


Why are there only positive value points on an elliptic curve?

Actually, strictly speaking, the $x$ and $y$ values on an elliptic curve point aren't integers; instead, they are field elements.  That is, the elliptic curve is defined in a field, which is a group of elements with addition and multiplication operations defined on them (along with a group of identities); the $x$ and $y$ values are members from these elements.

Now, you specify that you're doing a curve over $Z_p$; that field (often called $GF(p)$), which has precisely $p$ element, is most commonly represented by the integers between 0 and $p-1$.  With this representation, we perform the addition and multiplication operations by taking the represention, adding or multiplying the two values together (using normal integer arithmetic), and then perform a modulo $p$ operation (which maps the value back into the range of 0 to $p-1$.  If $p$ is prime, these operations satisfies all the required identifies of a field.

So, when you say that that points are always have positive numbers for $x, y$, what you're actually saying is that, using this standard representation, negative values never occur.  That's trivially true because this representation only contains values between 0 and $p-1$, and never takes on negative values. We can easily define an alternative representation which does contain negative values; we just don't have any reason to.


Variable length variable output encryption with out any padding?

It is important to understand that secure encryption - by the standard notion of security - must be probabilistic. This is so that the same value encrypted twice will look completely different. Otherwise, it is possible to compute statistics and learn a lot of information. The easy fact based on this is that secure encryption must increase the size (the ciphertext has to be bigger than the plaintext).

It is possible to also assume state. For example, if the encryptor and decryptor can keep track of a unique nonce (e.g., a counter), then it is possible to still get secure encryption. (For example, use CTR mode.)

If you don't have either of these, then you are in trouble. This doesn't mean that you can't do anything reasonable, but we don't have enough information about your application to help. Just encrypting using format-preserving encryption can be very problematic, depending on what you want to do. I refer to a recent paper by Seny Kamara and others that will appear at ACM CCS 2015 that presents attacks on databases encrypted using deterministic encryption.


Is it okay for a non-cryptographer to submit crypto code to an open source probject?

At least make sure that your code is reviewed. Verify you don't have possible buffer overflow or any kinds of implementation attack because of the use of non secure primitives. Moreover if you do so, test all your functions and in particular :

bitwise rotations
permutations
S-boxes...

Check everything as it is really easy to screw with it. Then use the test vector provided by the algorithm and check your results. For example here are the test vector I used when I implemented DES (which I don't use in production).

You can find other tests vectors of most ciphers here, i.e. for the AES-128-128.


Generate one-time-pad with pre-shared key and public randomness

You can relate your construction to the approach of using a pesudo-random function (PRF) in order to extend the key-length on the one-time-pad construction (in fact, it is more typicall to use a pseudo-random generator (PRG), but since this can be obtained from a PRF, and since your construction resembles more a PRF as well, I prefer to present it like this).

A PRF is a family of functions that resemble random functions, in a very precise way.
We say that a family of functions $\{F_s\}_{s\in \{0,1\}^\ell}$ is pseudo-random, where $F_s:\{0,1\}^n\to\{0,1\}^m$, if a function sampled at random from this set (which is done by sampling a random $s\in\{0,1\}^\ell$) is indistinguishable from a totally random function $f:\{0,1\}^n\to\{0,1\}^m$ (i.e. one were the image of each $x\in\{0,1\}^n$ is a uniformly random string in $\{0,1\}^m$).
If you have such a family of functions then you can build an "extension" of the OTP by simply using the pre-shared secret key $s$ as a seed to get a random function $F_s$, and using $F_s(0)\|F_s(1)\|\cdots\|F_s(N)$ as a (much longer) OTP key.

Now, if you think about it, when you consider your function $F(P,X)\to K$ you're sort of using this idea: you are using some shared secret randomness to expand it to a longer, perhaps not totally uniform key.
So, to answer your questions, your scheme is not information-theoretic secure but not really because you're reusing the key, but because the PRF is not really information-theoretic secure.

Remarks

Notice that, in particular, the source of randomness you call $P$ doesn't even need to be random! It only needs to ensure that the same value of $P$ is not reused among several different encryptions, and this can be achieved via a counter as I illustrate above. There is some randomness involved of course, but this is coming from the shared key.


Repeated Encryption using same/different Encryption systems

I found this information which may be useful for you:

Is encrypting twice good or bad?
Does encrypting twice using the same block cipher produce a security weakness?
Is there any benefit to encrypting twice with pgp?

The general rule as far as I know, is that encrypting twice (regardless if its using the same cipher or not) is rarely ever going to produce positive side effects. In some cases it completely breaks the cipher:

For example in rot-13, encrypting the plaintext twice simply decrypts it:

E(E(pt)) = pt

I should note that rot-13 is not a cipher you should be using in practice, but I included it here just to show how certain ciphers will exhibit weaker strength when used twice.

Having said all this, it is generally safe to encrypt twice (i.e. wont make the cipher text weaker) as long as different keys are used during each step (see here for a better explanation).


what is the state of the art algorithm to encrypt credit card data

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

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

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

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


How to detect duplicate values of sensitive data that needs to be encrypted

First, it is important to note that one important property of encryption is that you cannot determine if the same ciphertext is encrypted twice. However, assuming that you wish to give up on this property but you want it to be completely secure otherwise, then you still have to be careful.

Using regular encryption with the same IV is problematic. If you are using CTR mode then this completely breaks the encryption. If you are using CBC mode then if the first block is the same but the second is different, then you will be able to detect this.

The best solution is to use the AES-SIV or AES-GCM-SIV modes of operation with a fixed IV/nonce. These modes have the property that when encrypting different messages with the same IV, then you cannot learn anything apart from the fact that the plaintexts are different. Of course, if you encrypt the same message with the same IV then you get the same result.


My question is - are there any known methods (e.g. ever used in history) for selecting specified positions in point 2)?

Your construction is quite similar to the Running Key Cipher, which is soemtimes considered a variant of the Vigenere cipher. There they just start at one position and use all subsequent symbols as keystream.

  ... He told me that he thinks that such ciphers were used during WWII

As far as I know, in WWII rotor machines were the primary way to encrypt in WWII, including the well-known Enigma. By that time, classical ciphers were pretty much out of fashion already, because e.g. the Friedmann test (see link to Vigenere cipher) was invented in the 1920s, and frequency analysis has been known since the 9th century. So no, by that time encryption schemes had passed that stage already, although surely some people were still using it. Just like today some people use ciphers, which are known to be broken.

But considering the security of your scheme: If you use a keystream from a book, frenquency analysis will break that. Using e.g. only every 50th word from a book does not help, you are still linked to the characteristics of a language. If you use truly random keystreams, you are only on the safe side as long as that keystream is unknown to the attacker. If you publish those strings somewhere on the internet, you are relying on the attacker not knowing that.

The main aspect about classical ciphers in a pen-and-paper scenario is that you can actually do it without spending hours and hours for encrypting/decrypting short messages. Contrary to popular opinion, adding complexity does not automatically add security. But pretty much always it adds effort for the regular encryption and decyption. Therefore, I would suggest using one of the usual classical ciphers instead of trying to invent something new. E.g. the Vigenere cipher with long keywords (such that the message is maybe just 3-5 times the length of the keyword) works quite well, since frequency analysis doesn't work very well if there are very few letters corresponding to each letter in the keyword.

And a final note: If you assume the attacker uses a computer, classical ciphers offer basically zero security.


well it probably varies on how you want to access the key, one of the most extreme version could be an HSM which should keep it really safe but is also rather expensive.

another way would be encrypting it with a key that just you know  with plain AES and storing the base64 somewhere for example, that's what I do for some of them if you want to require entering a password you use use a key derivation function to create the key, but then you must make sure that you either use no salt or always the same.

when you want to do it for automatic access (like for needing the keys on a webserver) then you can either store the key somewhere in plaintext or you encrypt the key and save the encryption key somewhere ELSE, for example if your secret key is in a MySQL database, then store the encryption key somewhere deep in your Harddrive, even better if used with very strong permission management in there.

if you want automatic access you have to have direct access to the key which complicates it a lot.

by the way depending on how you set your HSM, you can use the key in an automated fashion, but not access the key itself.

essentially this means that you don't do the en/decryptions youself in your script/program/whatever but you send whatever needs to be crypted to the HSM which just does it for you (which also makes sure that you dont accidentially do bad things, which weaken the security drastically, because it can make it easier to use the crypto in the first place, because you just have your black box where you throw in your input and get the result).

of course it would still be annoying if someone broke in and got the ability to use your key as long as they are in, but as with HSMs you can usually not export the key at all, and even if you can, it's usually only if you supply extra permission credentials to do that. this means while the attacker can do a lot of stuff, as soon as he's removed from the machine, he cannot do crypto anymore because he didnt get the key.


Which block cipher modes of operation allow a predictable IV?

The short answer for the mode: use EAX.

There are several reasons why EAX is Good, but, in particular:

It includes integrity check, which is a must have (yes, really; defense against active attackers is often overlooked, and this is equally often deadly).
It needs a unique IV (a nonce) but tolerates predictable nonces.

As for OFB and CFB, see the Wikipedia page which has nice schematics. However, since neither does any kind of integrity checks, you would have to add some kind of HMAC, so choosing a nice integrated mode like EAX is simpler (and simplicity is good for security).

If for some reason you really cannot use EAX (or another similar mode), you can survive CBC by generating unpredictable IV the following way: use your source of "unique, predictable IV" to generate block-sized values, and encrypt each value with the block cipher, using a distinct secret key (which you do not have to share with anybody else). This is like using the block cipher as a PRNG. You still need a bit of randomness at some point (when you generate that extra key) but not as much as previously.


How to select "good" bits which pass NIST statistical tests x% of the time?

From the question:

  I have $k$ streams with $n$ bits each. (..)
  The original paper (..) states "For a given bit to be ‘good’, it must pass at least 3 of the NIST tests at least 75% of the time"

I read "given bit" as meaning "any particular bit index in each of the $k$ streams"; and "of the time" as meaning "of each test run performed for bits at this bit index" (among possibly many such tests because $k$ exceeds the number of bits a given NIST test consumes). Thus the literal implementation could be:

for $i$ from $0$ to $n-1$ (each of $n$ bit index in a sequence)

$p\gets0$ (the number of tests passed for bit $i$)
for each of the NIST tests considered (out of 15 at the last count)

let $b$ be the number of bits required by the particular NIST test (e.g. 100 for the Frequency (Monobit) Test; 1000 for the DFT test)
$f\gets\lfloor k/4b\rfloor$ (the maximum number of times the test is allowed to fail)
for $j$ from $0$ to $\lfloor k/b\rfloor-1$ (each group of $b$ streams)

perform the test on the $b$-bit sequence obtained by keeping bit $i$ of sequences $j\cdot b$ to $(j+1)\cdot b-1$ (numbering sequences and bits starting from $0$)
if the test fails

$f\gets f-1$
(optional: fail quickly) if $f<0$

break from the loop for $j$

if $f\ge0$ (the particular test passed at least 75% of the time)

$p\gets p+1$
(optional: succeed quickly) if $p\ge 3$

break from the loop for NIST tests

if $p\ge 3$ (at least 3 of the NIST tests passed at least 75% of the time)

that bit $i$ pass the original paper's criteria; remember to use this bit in the future.

It is possible to adjust $b$ for each test as a function of $k$ so as to reduce the proportion $k\bmod b$ out of $k$ bits that are not tested, or splitting the $k$ bits almost evenly across sequences tested (within 1 for tests with no constraint on $b$).

NIST tests with $b>k$ succeed for 0 out or 0 time they are run, and accordingly the "at least 75% of the time" criteria is met; thus a test that does not run still accounts in the minimum of 3 tests that pass; I'm among those thinking this is a telltale sign that the criteria is profoundly unsound. Main problem really are:

As far as we can tell from the question, NIST tests are run unmodified, thus with low $p$-value (like 1%), making the 25% failure rate tolerated seemingly unjustifiable.
When any test consistently fails, the bit sequence has been distinguished from uniformly independent bits, yet it is sometime kept; this means we are not using the tests for what they are designed to do: test sequences against the null hypothesis that they are uniformly independent bits.
Treating all the tests equals (when they are designed to detect very specific defects) is a telltale sign of an absence of method.

My algorithm is only the literal implementation of what the paper prescribes. This shall not be interpreted as a recommendation; rather, the opposite: the rationale of the prescription evades me. Advice only binds who trusts it.


The "path" is only a witness for your proof; you don't actually want to give the path to the verifier. Turns out that going from a NP-problem with witness to an actual zero-knowledge proof is not that trivial.

What you could do: one of your leaves $L_1, \dots, L_{n}$ has the value of your commitment $x$. You might write something like

$$\bigvee^{n}_{i=1}\left(L_i=x\right).$$

This is a satisfaction problem, so it's suited to be fed in a bunch of ZK libraries.

Lately, I've been playing with rank-1 constraint systems (r1cs), such as provided by libsnark or in a little time by dalek's ``bulletproof'' library. These provide non-interactive, fast, compact zero-knowledge proves.

You said your leaves could contain numbers. This translates very nicely in a r1cs system!

$$\prod^n_{i=1}(L_i-x)=0$$

You simply prove that one of the roots of the above polynomial equals zero, which is true when $x$ represents a leaf.


Why unit vectors should be encrypted bit per bit in that case?

The answer can be found in the lecture notes you link to.  You quoted from Section 2.2 of the lecture notes; if you read to the end of Section, you will find (on the very same page) the following statement:

  This encryption of a unit vector has applications to “private information retrieval”; details are in the BGN paper [1, Section 4].

This suggests that you might want to read Section 4 of [1] (the paper that introduces the BGN cryptosystem).  I suggest you particularly read Section 4.2, the part labelled "A SPIR scheme".

That part describes a scheme for private information retrieval.  If you work through the details of the protocol, you will discover that it involves having Bob encrypt a number (the index of the database that he wants to read) using the scheme described in Section 2.2 of the lecture notes.

Encoding the number as an element of the group would be fine in many cases, but it would not work for that particular "private information retrieval" protocol.  So, there's your reason.  That should answer your question.


AES CBC: how shall i get to know with AES CBC method, the received Cipher Text is padded or not

Your expected ciphertext is correct if you work with no padding. With PKCS padding the result is
6D251E6944B051E04EAA6FB4DBF78465881572C3A96A612C111055707BD7614E


How can non-nothing-up-my-sleeve numbers be used to exploit an algorithm?

It could be, for example, that this $N$ is a specially crafter prime number, that looks random and safe according to the NIST recommendations, yet discrete logarithms modulo $N$ can be solved considerably more efficiently due to its hidden structure. An attack of this type has been demonstrated last year at Eurocrypt in this paper; it uses a random-looking prime with a hidden structure that makes it especially sensitive to the SNFS algorithm. The team could solve discrete logarithms with respect to a $1024$-bit prime, while the current record for 'normal' primes is 768 bits.


I think you are mixing concepts.

In an interactive proof system, you have two communicating entities: the prover and the verifier, where the prover tries to convince the verifier about the validity of some statment.

The witness you mention is not another entity. To understand that, we need to know what kind of problems make sense to be dealt with in a proof system, which are the problems in the so called Non-deterministic Polynomial Time class, or $NP$ for short. Imagine all problems (not only those in $NP$) as being described by a string $x$. A problem $x \in NP$ has the additional property that, it can actually be efficiently verified to belong in $NP$ when you are given a value $w$ related to this $x$. More interestingly, if you are not given this $w$, it is (conjectured) to be hard to decide whether or not problem $x \in NP$. This is why these $w$'s are typically called witnesses.

Now, getting back to proof systems, it makes sense that they deal with problems where the prover needs to prove something that is not trivial to obtain. This is where witnesses (and $NP$ problems) come in. So, in order for the proof system to be meaningful, we restrict to $NP$ problems where the verifier cannot do the computation unless she interacts with the prover, who knows a valid witness for $x$.

Summarizing, the prover needs to have a witness in order to convince the verifier of the validity of the ($NP$) statement being dealt with.

A proof system being zero-knowledge further requires that the verifier does not gain any knowledge beyond the validity of the statment. Specifically, that she does not gain any information about the witness being used by the prover.

Note that I have introduced interactive proof systems. But there are non-interactive proof systems too. Actually, these are the ones you most probably want to use in a blockchain. As the name implies, in an interactive proof system, the prover needs to be active during the proof process and several communication rounds take place. But in a blockchain, assuming this would be doable is probably very unrealistic: blockchains are of a highly decentralized nature and you cannot expect the prover to be active at all times (even more assuming that blockchains are expected to last "forever"). In a non-interactive proof system, the prover just "creates" the proof and sends it to the verifier, who can verify the proof without further interaction.

Finally, then, getting back to your payment example: "The prover needs to use a witness in order to demonstrate to the other nodes (the verifiers) that she owns 100 dollars". How is this witness used depends on the nature of the proof and would most certainly not be just a hash function (although using hash functions is one step of a common approach to convert interactive proofs into non-interactive ones which, as I said, would be needed in a blockchain).

Note: I have been extremely vague (and possibly incorrect if we are being strict) when introducing the related concepts, specially in the definition of the complexity class $NP$. If you are interested in precise definitions, I urge you to lookup  some more formal source. You can begin with Wikipedia and the links therein, or any textbook on computational complexity theory, or the original works on knowledge and interactive proof systems by Goldwasser, Micali and Rackoff.


Create a CR hash function where truncating one bit leads to collisions

Assume there exists a collision-resistant $H$ from $\mathcal M$ to $\{0,1\}^n$; that $\mathcal M$ has at least two distinct elements $x_0$ and $x_1$, which we can exhibit (otherwise, any function from $\mathcal M$ to any set is collision-resistant); and $n>0$ (otherwise we can't define $H''$).

Proposition: there exists a collision-resistant function $H'$ from $\mathcal M$ to $\{0,1\}^n$ such that $H''$ from $\mathcal M$ to $\{0,1\}^{n-1}$ with $H''(x)\;=\;H'(x)[1\ldots n -1]$ is not collision-resistant.

Proof: Define function $G$ from $\mathcal M$ to $\{0,1\}^{n-1}$ by $G(x)\;=\;H(x)[1 \ldots n -1]$.

Define function $\hat H$ from $\mathcal M$ to $\{0,1\}^n$ by
$\hat H(x)\;=\;\begin{cases}
1\|G(x_0)&\text{if }x=x_1\\
0\|G(x)&\text{otherwise}
\end{cases}$

If $G$ is not collision-resistant, define $H'=H$, from which it follows that $H''$ is $G$. Function $H'$ is collision-resistant, because it is $H$, which is collision-resistant; but $H''$ is not collision-resistant, since a colliding message pair for $G$ can be found, and is a colliding message pair for $H''$.

Otherwise (that is, if $G$ is collision-resistant), define $H'=\hat H$, from which it follows that $H''(x)\;=\;\begin{cases}
G(x_0)&\text{if }x=x_1\\
G(x)&\text{otherwise}
\end{cases}$. Function $H'$ is collision-resistant, because any colliding message pair for $H'$ would be one for $G$, which is collision-resistant; but $H''$ is not collision-resistant, because $(x_0,x_1)$ is a colliding message pair.


Where can I get the correct and precise algorithms for elliptic curve cryptography?

Standards for Efficient Cryptography Group has published SEC1: Elliptic Curve Cryptography (pdf) about elliptic curve algorithms. If it does not explain the mathematics well enough for your purposes, there is also Fundamental Elliptic Curve Cryptography Algorithms (RFC 6090, from IETF) you could look at.

There are a lot of issues you can run into, so hopefully this is an exercise of some kind, rather than someone expecting you to write production code from scratch. For production code I would recommend using existing libraries.


The question largely boils down to:

  What does $n$-bit security means in practice for a given value of $n$?

TL;DR: as secure as a good symmetric cipher with an $n$-bit key.

There's not a single more precise definition, even if we restrict to attackers using classical computers (rather than quantum computers), as this answer does.

One generally accepted meaning is that the number of "steps" to break the system is believed to be $2^n$; or more precisely that the probability to break the system with $s$ "steps" is not known to be more than $s\,2^{-n}$ by any method for any $s$. However "steps" and "break" are not precisely defined.

In theory of symmetric encryption,"step" is typically taken as one execution of the cipher with a new key. This way, an ideal cipher with a key of $n$ bits has $n$-bit security, under brute force key search. When we move to practice, attackers are not bound to brute force key search, and the definition of a "step" has to become a number of sub-steps comparable in number and computational cost to the sub-steps required for one execution of the cipher with a new key for a plaintext the size of the key. With this definition, a practical cipher with a key of $n$ bits has at most $n$-bit security, and aims at that ideal.

When we move to hashes, the definition of a step could become a number of sub-steps comparable in number and computational cost to the sub-steps required for hashing a new message the size of the hash output.

One of many problems with the above is that there is no agreement about if we should count or not the cost of memory and memory accesses in the computational cost. The safe thing from a user's perspective is not to count it, but that can be be of paramount importance for an attacker.

The definition of "steps" becomes even more murky when it comes to asymmetric cryptography like RSA. In theory, "steps" might be one computation in the algebraic structure used for the cryptosystem; like, for RSA, one evaluation of modular multiplication $(a,b)\mapsto a\,b\bmod N$ for arbitrary integer $a$ and $b$ in $[0,N)$, where $N$ is the public modulus. But there are problems moving this to practice, in particular for RSA: the best known attack is to factor the public modulus $N$ using the GNFS algorithm, which computational cost is dominated by operations having little similarity with modular multiplication, and of practical cost dominated by memory and accesses to memory. Which puts use back to the vague definition in the TL;DR.

  how to calculate the time of attacking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?

"80-bit security RSA" is not to be understood as RSA with a 80-bit public modulus $N$, which is terminally insecure. If we had the size of $N$, we could estimate the difficulty based on that and previous experience (see this and its links). But we do not, and there is no consensus on the size of $N$ for RSA with 80-bit security: 1024-bit is often cited, but depending on hypothesis, and who you ask, that's grossly too much or too little. Thus the best is to ignore that we are talking about RSA, and get back to: as much time as needed to break a good symmetric cipher with a 80-bit key.

Which brings us to:
$$\text{Time}=\frac{2^n\times k\times p}{\text{Frequency}\times\text{Number-of-CPUs}}$$
where $n$ is the security level in bits, $k$ is an estimation of the number of CPU cycles to evaluate a good cipher using an ultra-optimized algorithm, and $p$ is the residual probability of success of an adversary. Depending on perspective we might take $k=1$ (which saves examining the particulars), $k=32$ (because that's still less than in the best attacks against good ciphers using a general-purpose computer), or much more. Depending on perspective, we can take $p=1$ (most prudent from a legitimate user's perspective), $p=1/2$ (yielding the expected time in the case of a block cipher), or a smaller $p$ if we want a security margin¹.

For example, with $n=80$, $k=1$, $p=1/1000\approx2^{-10}$, $\text{Frequency}=4\text{GHz}\approx2^{32}\text{s}^{-1}$, $\text{Number-of-CPUs}=1000\approx2^{10}$, we get $\text{Time}\approx2^{80-10-32-10}\text{s}=2^{28}\text{s}$, that is about 8 years. In other words, our 1000 CPUs have only a very small probability of success against 80-bit symmetric crypto, until they become technically obsolete.

On the other hand, 1000 CPUs is a tiny fraction of worldwide CPUs, and bitcoin mining conclusively shows that 80-bit crypto is no longer enough against adversaries with the capabilities to design ASICs, build them in massive quantities, and sustain the energy costs for their operation; see this.

¹ The $p$ term in the formula is the most prudent from a legitimate user's perspective, but it causes $\text{Time}$ to be underestimated in many attack scenario. For example, in collision search, the correct term would be more like $\sqrt p$.


AES-256 example code encrypting multiple subsections of plaintext with the same initialization vector

It seems like that chunking the input text and encrypting each chunk using the same initialization vector is a bad idea

You are quite right to be concerned. It wouldn't only be a bad idea; it would be an absolutely dreadful one.  With OFB mode, reusing an IV would cause the same bitpattern to be exclusive-or'ed with the plaintext to form the ciphertext; hence if the attacker takes the two ciphertexts with the same IV and exclusive-or's them, they'll get the two plaintexts exclusive-or'ed together.  From that, it is often not that difficult to recover the original plaintexts (as real plaintexts often have enough redundancy to allow this).

However, that's not what's happening here.

As a part of its processing, aes_ofb_crypt updates the IV it was passed; hence calling it multiple times will cause it to use a different IV each time.  Hence, this problem is avoided (and so this code is safe).


Crypto hash function vs encryption algorithms

The speed of individual algorithms strongly depends on their implementation. This goes for both hashing algorithms as well as encryption algorithms. This quickly becomes clear if you take a look at efforts like “eBACS: ECRYPT Benchmarking of Cryptographic Systems” and the results presented.

Also, you should not ignore that some algorithms have specifically been created with an eye on hardware implementation, while others were created with the clear goal of software implementation. This can result in the fact that an algorithm which was actually meant to be implemented in hardware, shows a low speed performance when being implemented and benchmarked as software version.

Therefore, you can not generally assume one algorithm to be slower or faster than another, without looking at their actually assumed implementation. Anything else practically results in rather incorrect (better: rather unfair) benchmarks.

Looking at DES

As you´ve mentioned DES… DES shows a bad performance as software implementation because it was intended to be implemented in an application-specific integrated circuit (ASIC). When you look at hardware designs of DES, you´ll see it perform pretty well in relation to speed.

Of course, things like its successor – AES – for example are able to beat DES out of the water both as hard and software implementation. But you have to remember that the Data Encryption Standard has been created more than 2 decades ago. As technology evolved, so did cryptographic algorithms.

Is it fair to compare DES with encryption algorithms like AES?

Not really. AES (First published in 1998) came around and about 20 years later than DES (First published in 1975, standardized in January 1979). In those 2 decades, both hardware as well as software evolved… and the creators of AES surely had the benefit of being able to look back at DES and its issues (both in relation to cryptanalysis as well as in relation to different implementations).

Is it fair to compare DES with hashing algorithms like SHA2?

Same as before: not really. SHA2 (First published in 2001) benefitted from similar things like AES. While we now may have access to cool things like personal computers et al, things looked quite different back in the 70´s… not only from a technological point of view. While DES includes several bit-oriented operations, SHA2 (and AES) were clearly designed with modern CPUs in mind, which logically results in better performance on modern computer systems (which they were designed for).

Wrapping it up

Whenever you compare speeds and something outperforms something else, the reason might be as simple as the fact that one of them is older and therefore slower due to not being as advanced as what you´re comparing it to.

In relation to cryptographic algorithms, looking at individual publication dates can tell a whole story…


Initialization vector based on data which can be changed by an attacker

The communication between the device and the software can be
  intercepted and changed by the attacker.

Because of this, you really should use authenticated encryption (e.g. CCM).

  Is it wrong to send a randomly generated value from the software to
  the device, hash it using SHA-256, and use that for the initialization
  vector?

For CBC, the IV needs to be unpredictable to an attacker. Hashing an attacker-known values doesn't make this value unpredictable, however if you encrypt the the value sent to your device using your AES engine, this value would be unpredictable and thus suitable as an IV for CBC.
Note though: CCM doesn't require an unpredictable IV and thus a simple (monotonic) counter would do, as long as the IV / nonce isn't re-used for the same key on either side.


Finding CRC collisions for specific divisor

I don't have that book, but I suspect that you are misreading it.

It's always easy to find collisions with CRC, no matter what the divisor (more conventionally known as a polynomial) is.  One easy way is to take the divisor and exclusive-or that bit pattern into an arbitrary place in the message (dividend); as in:

 10011    : Divisor (polynomial)
10101011  : Dividend (message)
11100111  : Modified message

111001110000 / 10011 = 11110110 R 1010

Here, we picked an arbitrary place in the message (starting at the second bit), and bit-wise exclusive-or'ed the divisor there, flipping any bit of the message where the divisor had a 1 bit.  The resulting modified message has exactly the same CRC as the original message.  Also, note that the quotient that we came up with is exactly as the original quotient with the second bit flipped; this is not a coincidence.

Given how easy this is, there wouldn't appear to be an even easier way that is specific to this polynomial.


What's the likelihood of a collision if I use a hash to detect data change?

When syncing two data set over the internet one can basically two choices;

send all the data and compare: This is slow but complete.
send the hash of the data: This is very fast but there is a tiny-tiny-tiny change of a collision is almost zero. If you are that lucky, you probably become reach or hit by an asteroid. This is very common on Linux's CD/DVD image downloads.

In your case, you want to just send a hash of one huge list. If you fear that the almost zero ( $2/2^{256}$ for a 256-bit bash function) is bothering you, you can decrease the change below almost zero by taking another hash function to have two hashes, though not necessary.

and, yes, Cryptographical hash functions are designed to have collision resistance, however, over the time one might find better attacks than generic collision attack like SHA-1 and it has already removed from the standard. This attack, actually, searching for different inputs, where the data structure enables, to find a collision. And the generic collision attack is $2^{80}$ on SHA-1, that is low in today's standards if you consider that Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019. Reaching $2^{128}$ way beyond classical computing.

Stick to a good hash function, SHA-256, SHA-512, SHA3, Blake2.


Is there a deterministic one-way collision-free crypto algorithm?

At SEJPM indicated, MD5 and SHA-1 probably are resistant enough for you never to get a collision. However, that doesn't mean that either of them is secure. Neither is SHA-2 or SHA-3. That is, given that the usernames do not have a special structure that makes them hard to guess.

The problem is that user names can - generally - easily be guessed. So whatever you do to them, a deterministic algorithm will expose them. You can just perform a dictionary attack and find the resulting value in the set of stored user names. This way most usernames will easily be found.

If you want to protect them you may need a second system (trusted third party, an entity other than the user or service provider) that performs username encryption / decryption or password hashing with a pepper - a secret value just like a key.

But in general it is better to make sure that knowing the username gives the adversary few - if any - advantages. This is the case in the majority of cases, although may systems may not indicate if a username or password is incorrect - making guessing of the combination of both just that little bit harder.


From my reading on crypto.stackexchange.com I understand that HKDF is probably a better function to use for deriving EncKey and AuthKey then PBKDF2 but in the development environment I'm in (.Net) I don't have access to HKDF from an authoritative source.

Discretion is the better part of valor, so more often than not it makes sense to try and use algorithms your environment provides over having to implement your own.  In this case, however, I think we have a reasonable exception; if your environment provides PBKDF2, and thus presumably HMAC, I think HKDF is simple enough that I'd say just write your own implementation of it.  The most useful source is the RFC:

https://tools.ietf.org/html/rfc5869

In particular, if your MasterKey is already uniformly distributed, section 3.3 tells you that you can skip the HKDF-Extract function (section 2.2) and implement just the HKDF-Expand (section 2.3), which is little more than a fairly straightforward chain of HMAC calls:

HKDF-Expand(PRK, info, L) -> OKM

Options:
   Hash     a hash function; HashLen denotes the length of the
            hash function output in octets
Inputs:
   PRK      a pseudorandom key of at least HashLen octets
            (usually, the output from the extract step)
   info     optional context and application specific information
            (can be a zero-length string)
   L        length of output keying material in octets
            (<= 255*HashLen)

Output:
   OKM      output keying material (of L octets)

The output OKM is calculated as follows:

N = ceil(L/HashLen)
T = T(1) | T(2) | T(3) | ... | T(N)
OKM = first L octets of T

where:
T(0) = empty string (zero length)
T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)
T(2) = HMAC-Hash(PRK, T(1) | info | 0x02)
T(3) = HMAC-Hash(PRK, T(2) | info | 0x03)
...

(where the constant concatenated to the end of each T(n) is a
single octet.)


(-5)^(-x) = (-5)^((-1)*x) = ((-5)^(-1))^x

The above link also has a good "Computation" section.


Let's shortly recall, how HMAC looks like:

$HMAC_K(M):=H((K\oplus opad) || H((K \oplus ipad) || M))$

As you may observe here, the calculation of the outer hash is fully independant of the message.

So the standard approach into implenting "update" functionality is to store the key and go as follows:

Init(Key):
Store the Key in K
Init two Hash-function instances H1 and H2
Feed (K XOR IPAD) into H1
Feed (K XOR OPAD) into H2

Update(Message):
Feed the Message into H1

Final:
Get the digest of H1 and feed it into H2
Output the digest of H2


CRC32 vs. low 32 bits of cryptographic hash

If we're talking about a malicious and intelligent attacker, you are mostly wrong, but not for the reasons you might expect.

If we assume an intelligent attacker, then a CRC does not help; they can obviously modify a file, and either figure out how to update the CRC32, or how to make sure that the modifications do not change the CRC.

On the other hand, if we use a SHA256 hash, that's not much better; if they can modify the hash as well, then they can compute the SHA256 on the new file, and replace that hash with that.  If they cannot modify the hash of the file, then if we truncate the hash to 32 bits, then they can try to modify the file $2^{32}$ different ways, and compute the hash on each; it's likely that they'll find a modification that leaves the hash unchanged.  This is obviously more work for the attacker; however it might be a weekend project for a single PC.

So, the bottom line is that there isn't a great deal of difference between a CRC and 32 bits of SHA256 in this scenario.

And, if we start looking at random changes, the CRC might actually be stronger in that case; if a random change is isolated to be entirely within a block of 32 bits, then a CRC will always detect the change (because the CRC will always change); the SHA256 will detect it with probability $1 - 2^{-32}$.

The first answer we have for strong integrity checking is to use a Message Authentication Code; this assumes that the entity generating the MAC and the entity checking for corruption share a secret key (that no one else has); this key is stirred into the generated checksum, and someone who doesn't know the secret key cannot modify the message and the checksum (with any probability better than random guessing).


What would be an adversary advantage in case of GCM authentication?

Can we use this formula to find GCM data integrity?

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

  Is there a similar document for GCM mode?

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

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

where

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

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


Does having a hash of the plaintext compromise the ciphertext?

Yes, having a hash of the plaintext available weakens the security of your encryption scheme.

Semantically secure encryption schemes have the guarantee that ciphertexts should be indistinguishible, regardless of what plaintext is encrypted. Clearly hashes do not have this property, since they're deterministic for each plaintext.

Assuming that messages are not randomly chosen, an adversary can guess messages, hash them, and check whether or not the hash is correct in order to learn the plaintext for the ciphertext. With only access to the ciphertext, but not a hash of the plaintext, this would be impossible, since a semantically secure encryption scheme does not allow an attacker to guess the plaintext for a ciphertext, as ciphertexts appear to be completely random with respect to the plaintext. The confidentiality guarantee of your system should only rely on the randomness and size of the key used, and not on the randomness of the plaintext, so this scheme is insecure if a hash is provided.

As for whether or not it allows the attacker to generate the key, that depends on the security guarantees of your encryption. As long as the encryption scheme is CPA secure (which is pretty much the weakest level of security that's "acceptable" for an encryption scheme), then one can't recover the key from plaintext and ciphertext.


what problem happen if we always use IV Zero in CBC Mode?

It become a deterministic encryption key: Same message encrypted twice, produces the same ciphertext. This has negative consequences on the security of the cipher, because an adversary know if you encrypt the same message, which means she can distinguish encryptions.


What's the generally accepted way of padding more than 255 bytes?

Bit padding is one way to do this. There are also padding schemes that do pad using a special length encoding. This can be more efficient as you don't have to parse all the bytes. But in general bit padding should suffice.

Bit padding first (and always) adds a single bit valued 1 to the plaintext. Then it adds bits valued zero to the right until the length you require. It is extensively used internally for hash algorithms but sometimes it is also used for block ciphers. Unpadding consists of removing all zero bits from the right and then the one bit set to 1. This padding scheme is fully deterministic; it doesn't depend on the plaintext at all.

In bytes you get values such as:

6F 77 6C 73 74 65 61 64 - 80 00 00 00 00 00 00 00

for padding a value

6F 77 6C 73 74 65 61 64

up to 16 bytes (block size).

That means one bit set to 1 (byte 7, the highest bit usually), 7 zero bits to make a full byte and then any number of zero valued bytes.

It is easy to see that you can use this for any size of input, and any size of padding.

A variation of this scheme is to simply pad with bits that are a complement of the last bit of plaintext. Then you can just remove bits that are identical to the last bit. This scheme however depends on the plaintext, which makes it more cumbersome.


Cryptographic hash where the hashing function input is similar to the result

If you mean that for all $x$, $H(x) = x$, this is usually known as the identity function.  It has the convenient property that it is guaranteed not only to be collision-resistant, but to have absolutely no collisions whatsoever.  However, it has the inconvenient property that finding preimages is slightly easier than one might hope, which one might consider to be a ‘weakness’.

That said, whether it is weak or not depends on what security goals you are hoping for it!  There are many kinds of things called hash functions, even in cryptography—universal hash families like Poly1305 and GHASH, message authentication codes like Poly1305-AES and AES-GMAC, stream ciphers like Salsa20, pseudorandom function families like SipHash, collision-resistant hashes like SHA3-256, password-based key derivation functions like argon2, etc.  But the identity function is usually not considered a hash function.

If you mean that there exists $x$ such that $H(x) = x$, called a fixed point of $H$, well, for a uniform random function $H$, what's the probability this can happen?  Let's suppose the input and output are $h$ bits long.  We can ask the complementary question of the probability that there are no fixed points, and note that for each distinct $x$ independently, $\Pr[H(x) = x] = 1/2^h$.  Then

\begin{align}
  \Pr[\exists x. H(x) = x]
  &= \Pr\bigl[\lnot \forall x. \lnot(H(x) = x)\bigr] \\
  &= 1 - \Pr[\forall x. H(x) \ne x] \\
  &= 1 - \prod_x \Pr[H(x) \ne x] \\
  &= 1 - \prod_x \bigl(1 - \Pr[H(x) = x]\bigr) \\
  &= 1 - \prod_x (1 - 1/2^h) \\
  &= 1 - (1 - 1/2^h)^{2^h} \\
  &\approx 1 - e^{-1} \approx 63\%.
\end{align}

So there are better than 50-50 odds that a fixed point exists in a uniform random choice of function.  We often use this to model functions like SHA3-256.  Does this indicate a weakness?  Well, there are two sides to this:

The traditional properties that we might think of when we hear ‘cryptographic hash function’ after reading Wikipedia without consulting any cryptography literature are preimage resistance, second-preimage resistance, and collision resistance.  Knowing a fixed point of SHA3-256 doesn't mean you can find preimages, second preimages, or collisions.  So in that sense, a fixed point does not indicate a weakness.  Indeed, it is very easy to find fixed points in the internal compression function of any Davies–Meyer hash function like MD5, SHA-256, etc., although that doesn't mean a fixed point on the full hash function.
On the other hand, the probability that you come upon a fixed point by happenstance in a single trial is $1/2^h$.  For, e.g., SHA3-256, this is unimaginably improbable for all imaginable numbers of trials—so the inference one might draw in practical terms is that there likely is a weakness in SHA3-256 that enabled you to find it, but the details would depend on how you found it and on details of SHA3-256, not on the general fact of a fixed point, and while it would cast serious doubt on the security of SHA-3, it might not actually have any practical consequences in any real protocols.


UNIX password scheme and encryption function

Most people would not call what we do to store passwords encryption as it is not reversible. It's a cryptographic hash.

Also the diagram has some specific numbers which correspond to the orignal unix DES based system which nobody should be using any more for many reasons but mainly only 8 chars ASCII passwords. The principals however remain the same.

We want to protext the system also in the event of data from the shadow file is leaked ans to a limited extent from the system adminstrator. It should be impossible to recover the plain text password from what we store, anyone trying to brute force the passwords should need to this one password at a time and not all together. Brute forcing passwords should be a slow process.  It should not be practical to precompute rainbow tables for even a faily modest collection of passwords. We should still be able to verify a given plain text matches the stored record and it should be extremely unlikely another password will accidentally match.

We do this with a special kind of cryptographic hash function and with the help a random salt. The salt (originally  12 bits nowadays more) makes attaxking passwords together and building rainbow tables very difficult. And the hash function should be slow so a single password brute force is impractical.

Since the original implementation we also add that speed should be paramaterized so we can increase compute difficulty as computers become faster. This was missing in the original unix implementation.

Also we want to support long passwords and we want the hash function to preserve as much of the entropy in the password as possible (unlike the infamous LanMan). The hash function should be preimage and collision resistant (unlike the LanMan). Some may want to add diverse charset support which many now use to increase password entropy.


Tell me like I'm 5: How are algorithms secure if people can see them

A modern cipher algorithm concentrates the required secrecy into the key instead of the algorithm. This is helpful because a key is relatively short, compared to even the most compact binary representation of a simple cipher. This means there is actually less to protect then the algorithm itself. Only the person(s) who know the key can encrypt or decrypt messages.

Physical Locks work the same way. A lock can only be opened or closed with the key. Knowing that there is a lock on the door does not help in getting past it, even if you know what type of lock it is.

People learned a while ago that obscurity and quantifiable security are not the same thing. This is usually referred to as Kerckhoffs's principle.

As for your question about open source/proprietary algorithms:

Firstly, the open source equivalents aren't just open source, they are industry/government standards, like the Advanced Encryption Standard and Secure Hash Algorithm families
A proprietary algorithm may not have seen review by any or more importantly enough other cryptographers, for long enough.
There exists snake oil cryptography, which advertises itself as being supremely secure, but is sometimes outright silly to those who understand well enough.


Random Number Generator based on AES CTR

First, the obvious advice is not to use this in practice. Rolling your own is fine for learning, but you should use standard primitives when you need actual security. E.g. one from SP 800-90A which poncho linked in comments.

Now, some observations. I haven't read all your code, so I may misunderstand things.

  Is this a good way to whiten the data? Is there a better way?

Looks unnecessarily complex. AES output is already white, unless AES is broken, so you shouldn't need to do any whitening on the output. The massive table which you use for stretching doesn't seem very secure. For example, you are using secret array indices, which may allow for timing attacks.

  Is there an ideal interval at which an AES CTR generator should be reseeded?

A normal AES generator should be reseeded after $2^{48}$ blocks of output at the latest, according to NIST. That number prevents the attacker from having more than a $2^{-32}$ probability of an advantage.

  Is reseeding too often introducing patterns that might be exposed by some form of differential analysis?

If you have a good source of numbers to feed it, you can do it often, but then why not use those numbers directly? (Performance, maybe, in which case you want relatively infrequent reseeding, but much more often than required is possible.)

Seeding with bad input should only hurt if you use an update system that overwrites previous state and can lead to identical key & IV.

  How can this be made stronger? How would you improve upon this? ..and are there any serious flaws in the implementation?

I would rip out the whitening stage, for the reasons I mention above, and use AES output as the random output. If you want frequent reseeds and don't have access to a fast TRNG, you could leave an SHA-256 loop for updating the AES key.

Alternatively, if security is the objective, decouple the hash based RNG from AES and run them independently, e.g. XORing the outputs.

A couple more things that seem unnecessary: you are XORing two halves of an SHA-256 output together – using one would be as strong unless SHA-256 is broken; you are XORing the AES counter into the IV, when I think you would be better off treating it as a single counter with a longer period.