How does the PRESENT cipher's permutation affect all rounds when it repeats after every three rounds?

Yes, you might think that the bits return to their original positions.  But they don't because those aren't the bits you're looking for.  They've changed.  Specifically, you need to consider the effect of the s-boxes.  If a single bit goes into a s-box, it's very nature means that on average, two bits come out.  Similarly, if three bits go in, two bits still emerge on average.  This is the substitution component of PRESENT.  What you've focused solely on is the permutation component.  To achieve full and proper diffusion of bits throughout a substitution /permutation network (SPN), you need both components to work together.

This repetitive substitution and permutation (what Shannon termed confusion and diffusion) creates an avalanche effect through the internal state.  If such a network happened to have the same number of s-boxes as their width (ie. 8 boxes of 8 bits), you would achieve full avalanche effect in two rounds.  If the ratio is different like PRESENT's 4/16 construction, full avalanche won't occur till more rounds happen.  It's a function of the ratio.  I don't know how many rounds PRESENT needs, but it clearly happens way before the total 31.  These networks tend to have a very generous and conservative round count to help security.

So it's the effect of the s-boxes in conjunction with the permutation that ensures all bits affect all other bits.  The diagram below is for a generic SPN but illustrates a bit's travel through it:-

One bit went in and as expected on average 8 bits come out.  It simply doesn't work if you just consider the permutations on their own.


Let divide the problem into two cases;

The file encrypted and stored on the cloud for access.
For this case, to decrypt the file people will need the key. So, if the expiry date is not passed you will transmit the key. They will download and decrypted. From this point, they will not need your key and encrypted file. Nothing can prevent them to take a copy of it. They can use screen capture softwares etc., if this is prohibited in hardware, they can take photos. If no want accessed the file you can delete the file from the cloud. Actually, you will never be sure that a copy was taken. So, in the future when your encryption scheme is broken the file will be accessible.

The file encrypted and not stored on accessible storage for the third party.
You can safely delete the file and the keys.

As point of view, there can be some solutions depend on the environment that this system applied. If the user is in a very strict environment where the cameras or similar devices are prohibited and the computers are highly secured as no input-output ports etc. However, all these are nothing to do with Cryptography.


Can I use the output from a DRBG directly as K for AES, or do I need to use a key generator algorithm?

It you need a deterministically derived key for AES, the DRBG algorithms of NIST SP 800-90A are suitable, and their output is directly usable as an AES key. An example use case is when computing an AES session key from a longer-term master key, and the nonce corresponding to that session.

AES will expand its key (128, 192 or 256-bit) to 128-bit subkeys (one more than there are rounds, thus 11, 13, or 15 subkeys), using an algorithm known as the AES key schedule, but that's considered internal to AES.

Notice that any DRBG needs a seed input, and that must be random and secret, thus best generated by a True RNG.

Update following comment: to my knowledge, NIST has no publication fully describing a particular TRNG (which they designate as nondeterministic random number generator); the closest thing (pointed by Thomas M. DuBuisson) seems to be draft NIST SP 800-90B, which gives general recommendations for (mostly: the conditioning of) entropy sources.

NIST does have publications, in particular FIPS 140-2, on how a TRNG should be tested (both during use and for certification purpose) and used; quoting that (as current in 2003):

  Until such time as an Approved nondeterministic RNG standard exists, nondeterministic RNGs approved for use in classified applications may be used for key generation or to seed Approved deterministic RNGs used in key generation. Commercially available nondeterministic RNGs may be used for the purpose of generating seeds for Approved deterministic RNGs. Nondeterministic RNGs shall comply with all applicable RNG requirements of this standard.

Quoting a 2012 draft of annex of FIPS 140-2 annex C on RNGs

  There are no FIPS Approved nondeterministic random number generators.

NIST maintains a list of cryptographic devices with a certificate made in relation to the aforementioned publications.


Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?

The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the key is fixed to 0, but any fixed key value would give the same effect). This is due to the fact that AES is a permutation and so when $k$ is uniformly distributed, then $\operatorname{AES}_0(k)$ is a uniformly distributed value. More formally, for every $c$ and every $x$ there exists a $k$ such that $c=\operatorname{AES}_0(k)\oplus x$. In order to find this, compute $k = \operatorname{AES}_0^{-1}(c \oplus x)$.

Now, when encrypting $\operatorname{AES}_k(x)$ the same argument fails. This is because for $c=\operatorname{AES}_k(x)$ there is no guarantee that decrypting $c$ under all possible keys gives all possible plaintexts. Thus, it is possible that there is only one $k$ (or a few $k$'s) that give you the known initial portion.


Decrypt AES-128 with key file but missing IV?

First of all, I suggest you to try use as IV first 16 bytes of encrypted file.
Because in general IV is the first block of ciphertext.

But if that doesn't work, then – of course – you can decrypt all message except first block.
Just use first block as IV, and start to decrypt from second block. That will work because CBC does not provide integrity, and you can decrypt parts of the message picking any part of the ciphertext.

To better understand how this works, I also suggest you to read about CBC.


Repeated modular square roots to recover original base

How can I eliminate square roots before I go all the way down the "tree"?

The obvious thing to do is eliminate intermediate values that are not quadratic residues.  Here is one way to do it:
Define the set s := [ c ], that is, s initially consists of a single element c.
For i := 0 to 63 do
    Set the set t := [], that is, initialize it to be the empty set
    For each element a \in s
        Use the Toneli-Shanks algorithm to find the square roots b, -b of a$
        Check if b*b = a mod p; this cannot hold if a is not a quadratic residue
        If the check holds, then add b, -b to the set t

    Set s := t

At the end, the set s will consist of all the possible $2^{64}$th roots.
This won't iterate through $2^{64}$ values because the Quadratic Residulosity check will reject about half of the incorrect paths (as half the possible values are not Quadratic Residues)
.  Instead, the sizes of the sets s, t should be reasonable (in my experience based on similar algorithms, possibly hundreds of elements)


Why I can't permutate an email and get away with it?

I can understand why a simple substitution cipher can be broken easily due to English letter frequencies can be used and even English diagrams like th can be used, also a complete random substitution will have a key length of 26! which can be done(around 2^88 maybe NSA)

The first part is correct. A thousand years old Frequency analyses can break this very easily. Many times this is given as homework on the Introduction to Cryptography courses. Note that this may require longer text in some languages or in some contexts (Gabel's Novel without e). In real-life both are assumed to be known since the attackers know you.
Trying all permutations is not the correct way since it can lead to many false positives and a long process to go.

but what about emails according to google emails have an average word count of 400 words so I guess letters count will be at very very least 800 letters. Brute forcing 800! (assuming complete random permutation function) is not possible. I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption so why is that, How to get around brute-forcing 800!.

I think you mixed about how the permutation cipher works. Or you are referring you generate a larger permutation like the permutation of two characters instead of one where you will have $26^2$ elements to permute in the standard English letter. That will contain $26^2! = 676!$. And it has 1622 decimal digits, try here, or around 5386 bits. This is still applicable to diagram-based frequency attacks therefore insecure.
Now, what about the key size? How do you exchange this key? It is not practical since you need to send an array of size $676*2^{10}$.
A cryptosystem besides being secure needs to be practicable, and this is not practicable. The common wisdom is using the substitution/permutation (confusion/diffusion) to achieve a computationally secure cipher like AES and be practical.

The kind of permutation I mean is we have 800 letters so 800 positions are possible. The first letter will go into one of 800 positions the second letter goes into 799 positions and so total =800!. From your answer, I guess this approach is completely safe (if letters length is large), but not practical right?

That is a positional permutation that only scrambles the letters. It is not as secure as one may think of since all characters are there. It may take time to place them correctly. The e-mails have some known beginning and ending and that will help to find the permutation. And keep in mind that that is not even secure under the Known-Plaintext Attack. The key size still is the issue.


Is public-key cryptography the only option in this scenario?

"Is to be encrypted" is not a ultimate goal. You do not encrypt data for the sake of it; you encrypt data as a way to ensure a given security property, e.g. transmitting some data between two machines, without compromising the data confidentiality with regards to attackers who may spy on the transmission line (or even alter data in transit).

If:

your problem is indeed a question of data transmission;
you can arrange for both sender and receiver to share a common password;
the transmission uses an online protocol where messages can flow in both directions;

then you can use a secured data tunnel, with a Password-Authenticated Key Exchange protocol to establish a shared symmetric key (used for tunnel encryption and integrity) with mutual authentication relative to the password. PAKE protocols ensure that attackers spying on the line, and even active attackers who can try to impersonate the client or the server, learn nothing which can be used to "guess passwords". With a PAKE protocol, each "password guess" must imply some communication with an honest system (the real server or client). Server and clients can then easily detect brute-forcing attacks after only a few dozen tries. Therefore, PAKE protocols are secure even with passwords of low entropy.

A secure tunnel with a PAKE protocol is a complex beast, easy to get wrong in many ways. Hence you really should rely on an existing, well-analyzed protocol. I suggest SSL/TLS with SRP; this is supported by at least the opensource GnuTLS library.

If the transmission is offline (e.g. in an emailing context: the sender must send all its data in one go, and that must be sufficient for the receiver who acts only afterwards), then a password will not be enough, although you can make it quite hard for the attacker by using an appropriate key derivation process, in which the password is hashed many times with a random salt. Usual recommendations are PBKDF2 and bcrypt. A password with about 30 bits of entropy is sufficient if you use a key derivation process which implies at least a few seconds of computation on a reasonably recent PC.

To get more security than that, you must use a stronger shared secret key; if this implies an unsolvable key distribution process, then you can go to a public-key based scheme, the archetypal protocol being OpenPGP (see GnuPG for an opensource implementation). You still need to make sure that the sender has the genuine receiver's public key, but (at least) this implies no sharing of secret data.

Edit: with the new phrasing of the question, the answer is now clear: PAKE. You want to get a shared secret with mutual password-based authentication, and resilience against offline dictionary attacks. PAKE protocols are precisely designed for that. All currently known PAKE protocols involve some "public-key-like" elements, so you will not avoid at least some mathematics. SRP is an adequate, well-documented PAKE protocol.


Steganography - How many bytes of information can you hide in a $1024 \times 768$ photo?

This is one of those answers that - depends.

The amount of data that can be hidden inside an image depends on the image.  This is one of the concepts that most steganographers miss.  We have to go to the definition of steganography.  Hiding a secret message with emphasis on the hiding part. That means that a message may or may not be contained within the pixels of an image, creating plausible deniability.  If you overtly don't bother to hide it, you might as well traditionally encrypt the message with AES, append it to an email and add "Secret message attached" to the subject heading.

It is also a requirement that the message is compressed /encrypted or generally whitened.  Whist encryption is not absolutely necessary for steganography to be successful, the message has to be converted to almost randomly distributed bits.  Any uncompressed /unencypted pattern can be easily discovered via heuristic or frequency analysis of the image. After all, image noise is almost uniformly random.  If compression is used, the amount of data is becomes contingent on it's type and therefore it depends.

From a capacity and mathematical deniability perspective, the following type of image is optimum:-

It's just random noise in all three colour channels.  If the least significant bit contained the compressed message, and the message was textual, you might expect 9 Mbits of capacity£.  You may have issues of plausible deniability though if you're sending many of these images without a really good excuse.  And they'd have to be in the form of a lossless format, which again is uncommon.  Tools like OpenPuff can use lossy formats but that then reduces the message capacity.

This is also a problem image:-

Here the whole mountain side is blown out.  Image analysis would easily identify manipulation of the least significant bits of the mountainside as they're all meant to be exactly 255,255,255. Almost half of the image can't be used.  The steganographic tool would have to determine this.  An image with deep shade presents the same problem featuring an expected RGB of 0,0,0 for that part of the image.  So again the message size depends.

So you're left with using images like:-

In this instance you might get 9-18 Mbits of text$, but you're reduced to sending grainy images all the time for this message capacity. The sensor noise will mask the whitened message, especially if you use less than 1 bit per channel per pixel.  And they have to be lossless formats like BMP /JPEG2000 /TIFF or PNG.  None of these are particularly common in the social Facebook world, compromising the plausible deniability argument.  A lossy format will reduce the message size again.

Algebraically, you can form an equation like:-

capacity = (usable %age) X (encoded bits) x (no.pixels)

which represents the difficult relationship of:-

capacity = F(artistic composition, SNR, image size)

In summary, the message size is very difficult to quantify without a detailed analysis of your photo.  Why don't you post it?  The most important take away here is that the issue with steganography is not encrypting a message in an image, but being able to deny that there is one in the first place. This is similar to the deniability issues with disc encryption software like TrueCrypt.

£ I'm assuming that a large sample of English prose can be compressed to 2 bits /byte.  Capacity = 1024*768*3*4 =~ 9e6 bits where 4 is the compression ratio.

$ In an image this noisy (low SNR), it might be possible to utilise 2 bits per image byte for the message.  Or even more?


What is the difference between a hash function and a pseudorandom function?

A hash function is a stateless "primitive" function: given an input of X, it always produces the same output Y, where Y is a fixed length.  A cryptographically secure hash function has some additional requirements: given output Y = hash(X), it is hard to deduce input X; given output Y = hash(X1), it is hard to find output Y = hash(X2); and that it is hard to find hash(X1) = hash(X2).

Common random number generators that are used for statistical simulations are designed to produce a statistically even distribution of bits, and a hash function may be fine for this purpose.  But a statistics simulator doesn't need have the same security needs as a CSPRNG, as it isn't being used to generate cryptographic keys used to protect secrets.  A cryptographically secure pseudorandom number generator (CSPRNG) needs to output bits that are unrelated to each other, so that given output bits 0-n, plus knowledge of all internal state used to produce those output bits, it is hard to determine bit n+1.

To achieve this level of unpredictability, a CSPRNG needs a source of unpredictability, called "entropy".  Entropy is surprisingly difficult to come by inside a computer; as a computer is deterministic, it generally doesn't have an internal source of randomness.  Sources of entropy are often based on unpredictable external analog data (thermal noise on a Zener diode, radioactive decay, nanosecond timing of human inputs, etc.)  But the number of bits available are limited by the time required to collect them, so there is often not a large enough "quantity" of entropy to directly output the bits of entropy to all the clients who need random numbers.

To meet the higher demand of a modern computer system that needs lots of random numbers, the small quantity of entropy available is frequently expanded using a "cryptographic sponge" function.  This is a complex algorithm built of primitive functions that are used to collect the available entropy (called "harvesting"), gather the bits in a pool, and they then "stretch" the few bits in the pool into a larger quantity of relatively unpredictable bits.  A hash function is at the core of many of the sponge functions and can be used to expand a relatively small number of bits into a larger number of unpredictable bits, but the sponge needs extra logic in order to manage the incoming bits, to produce the queue of output bits, and to refresh itself.


You neglected the most important part, I believe; the encryption map itself may be probabilistic which means we might have $$c \leftarrow \mathrm{Enc}_k(m),$$ instead of $$c =\mathrm{Enc}_k(m),$$ which is deterministic. In the first case a second encryption with the same key and message might result in a different ciphertext. Once you realise this and given that the key space is finite consider for each fixed key message pair $(k,m)$ the distribution of the random variable $$\mathrm{Enc}_k(m) $$ over $\mathcal{C}$ and note that this distribution where each probability is a real number can be approximated arbitrarily closely by a rational distribution with rational probabilities.

Let us say $p_i=a_i/b_i,$ is the rational arbitrarily accurate approximate probability for the ciphertext $c_i$ belonging to the set of texts that appear with nonzero probability for the given $(k,m).$ Rewriting the probabilities as fractions with denominator $\mathrm{LCM}(b_i)$ we can now replace the key $k$ with $$\mathrm{LCM}(b_i) a_i/b_i$$ keys all of which will now map deterministically to the single ciphertext $c_i.$

Proceeding this way for each $(k,m)$ pair we obtain a deterministic scheme.


When using DES, how large would the key space be if we only use letters as characters?

A DES key is 56 bits. If we assume letters are ASCII encoded and take 8 bits each this means a DES key of only letters would be 7 letters long. Given that there are 26 letters in the roman alphabet we would have $26^7 \approx 2^{33}$ possible keys, or if we allow uppercase and lowercase, $52^7 \approx 2^{40}$ possible keys. Both keyspaces can quickly be enumerated with modern hardware and can easily be brute forced.


What to watch for with openssl generating weak keys? (low entropy)

I will answer considering Linux OS, as being one of most popular Unix-like OS (between OSes which have urandom). If you need other OS, please, inform me.
Also I will answer using source code of random.c driver from Linux 3.3.3 Kernel, because it is one of best documentation of /dev/random mechanics. And the other is paper: Analysis of the Linux Random Number Generator, Gutterman
 2006, 086.pdf - check pages 4-6 and Figure 2.1 (slides). Then you can check The Linux Pseudorandom Number Generator Revisited, Lacharme 2012, 251.pdf paper. Even wikipedia may be helpful here.

There are several random pools in Linux:

Primary pool of 512 bytes (128 4-byte words); incoming entropy is added to it;
Secondary pool of 128 bytes to generate random for /dev/random
Urandom pool (or another secondary pool) 128 bytes for /dev/urandom

Separate entropy counters are maintained for all three pools, but usually the counter of primary pool is mean. The 'available' counter is from primary pool.

When you asks for random data, portion of entropy is extracted from the corresponding secondary pool (using one-way functions involving SHA1), then it is partly added (mixed into) to the pool. Part of extracted data is given to the consumer of random data. Both user and kernel consume entropy, e.g. kernel uses API to random driver for starting processes when ASLR is enabled (it is enabled in most distros). There is interesting example when doing several cat /proc/sys/kernel/random/entropy_avail will stole most entropy, may be this is the your case too, proof at StackOverflow. To monitor entropy_avail you should use some daemon or simple C program which will reread pool several times without process restarting.

When Secondary pool has low entropy, some portion of entropy from Primary pool is extracted (again with using of cryptographic one-way functions), then part of it is remixed back into primary pool and part of it mixed to the consuming pool.

  1) How low does entropy have to be for it to be dangerous? If I run cat /proc/sys/kernel/random/entropy_avail i get anything from about 130 to a couple thousand. And it seems to fluctuate quickly.

I would like to consider the entropy_avail as estimation of "how many high-quality random bits may I extract from random source". /dev/random gives only high-quality bits and blocks when there is no entropy left, while /dev/urandom gives bits of any quality. When entropy is high, urandom gives high-quality bits, but when entropy is zero, it gives (probably) cryptographic pseudo-random number sequence (there are better examples of such CSPRNG generators in almost every other popular OS: FreeBsd/OpenBSD,MacOS,MS). But 251.pdf (part 4.3, page 16) says "Consequently, the Linux PRNG without entropy input is assumed to be secure if the internal state is not compromised and if the three pools are initialized by an unknown value."

The maths behind the entropy estimation in Linux is analyzed here (nothing useful for software engineer, just adding and subtracting numbers).

There is source code of /dev/random and /dev/urandom driver: http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L261  (you can turn on DEBUG_ENT to see the actual working of the random driver)

 /*
  * Configuration information
  */
 #define INPUT_POOL_WORDS 128
 #define OUTPUT_POOL_WORDS 32
 #define SEC_XFER_SIZE 512
 #define EXTRACT_SIZE 10  --- 10 bytes to be extracted from secondary pools

 /*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
  */
 static int random_read_wakeup_thresh = 64;

If the available_entropy is lower than 64 bits, no one will read from /dev/random. So, this is extremely low, and smaller values will block everyone who are reading from /dev/random

 /*
  * If the entropy count falls under this number of bits, then we
  * should wake up processes which are selecting or polling on write
  * access to /dev/random.
  */
 static int random_write_wakeup_thresh = 128;

If the available_entropy is lower than 128 bits, and there are some good guys who can give us more entropy from userspace, try to ask them to do so. So, even at 128 bits of entropy we are not in best form and willing for getting help.

 /*
  * When the input pool goes over trickle_thresh, start dropping most
  * samples to avoid wasting CPU time and reduce lock contention.
  */

 static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;

If there is more than 128*28 = 3584 bits, we are refusing to add all available entropy from external sources (but some "samples" still will be mixed into out primary pool); when there is lot of available entropy, some incoming entropy will be added to secondary pool (but not to urandom pool).

  1a) Is an attack feasible at 130, or how low would it have to go (50, 10, 1, 0)? I haven't seen any hard numbers on this. Is the attack just theoretical or how much work would it take to break it in practice?

To carry out effective attack the random driver, I think, attacker should somehow predict state of the primary pool. Check part 2.2 from the http://eprint.iacr.org/2006/086.pdf - Initialization. Primary pool is initially filled on boot of system, and attacker want to predict, how it is initialized (what random sources were used and what was the input data). This may be problem in embedded devices or unattended servers or virtualized servers, which have low number of unpredictable entropy sources. The major sources are: user-generated (keyboard, mice), periphery devices (interrupts, e.g. from network), devices with hard-to-predict response times (hard disk).

Most embedded devices will have no hard disk, low number of periphery devices (and all being standard for the model), no any user sitting in front of booting PC and moving mouse and pressing keys at unpredictable moments of time. Also they may have bad-quality timing resource (entropy data from external source is 32 bits of timestamp and 32 bits of attributes; if you can measure timestamp only according to 32kHz quartz you are in bad situation, much better is to use clock tick counter or modern Intel/AMD CPU, which is 3GHz with some hard-to predict variability).

Embedded devices have standardized setup with standard flash image (usually not updated at whole live time of device), and some devices or Read-only bootable medias (Knoppix, OpenWRT) misimplement saving/restoring of entropy at boot/shutdown. Right implementation is to save 512 bytes from some random to persistent storage at shutdown and feed them back into /dev/random early at boot time (there is also comment here in linux sources: Ensuring unpredictability at system startup; /etc/rc.d/init.d/random script in SysV-era startup systems).

There is fresh overview of some embedded problems and where to search good randomness on them: http://cseweb.ucsd.edu/users/swanson/papers/Oakland2013EarlyEntropy.pdf The conclusion of the work: "Randomness is a fundamental system service. A system
cannot be said to have successfully booted unless it is ready
to provide high-entropy randomness to applications."

I think the most dangerous thing is to generate some keys early after boot on them of in known moments of time on highly embedded device. To hack the keys, hacker is needed to backpredict all entropy sources and to model primary pool state and secondary pool state at the time when key was generated. This task is hard, but sometimes it is easier then attack the key itself. I can't show examples of urandom attacks now, but I think they are exist for some vulnerable installations.

Also I think that debian's edition of openSSL was more fatal than bad random quality: http://www.schneier.com/blog/archives/2008/05/random_number_b.html http://xkcd.com/221/ There were possible only around tens-hundreds thousands of keys for every fixed RSA key size, because urandom input was disabled and the only and best available entropy input for openssl was the process ID, or PID, which is usually limited to 32-65 thousands on linux.

  2) Does openssl block until there is sufficient entropy to generate a key? My understanding is that /dev/urandom does not block and is the default, but /dev/random does. I assume /dev/random is not the default for performance/consistency reasons?

openssl will not block (I think, didn't check on modern versions), because there is no clear way to application to detect moment when urandom had too low entropy and switched to almost-fully PRNG mode. There are only several ioctls on /dev/urandom to read avaliable_entropy. openssl only tries to use own PRNG, which is seeded by current time and openssl's pid  and data from urandom or from RANDFILE.

http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L109

 109 * The two other interfaces are two character devices /dev/random and
 110 * /dev/urandom.  /dev/random is suitable for use when very high
 111 * quality randomness is desired (for example, for key generation or
 112 * one-time pads), as it will only return a maximum of the number of
 113 * bits of randomness (as estimated by the random number generator)
 114 * contained in the entropy pool.
 115 *
 116 * The /dev/urandom device does not have this limit, and will return
 117 * as many bytes as are requested.  As more and more random bytes are
 118 * requested without giving time for the entropy pool to recharge,
 119 * this will result in random numbers that are merely cryptographically
 120 * strong.  For many applications, however, this is acceptable.

So, as says the source of random and urandom, you should not generate long-term keys from urandom, but still can use it to generate sessions keys for doing something not valuable (e.g. session key for SSL to facebook to view some more images with cats).

And when you are asking about openssl key generation, you should define what is the key to be generated. If it is session key for TLS, and you are on server, then using of /dev/random will limit how much clients can connect (there were no so much entropy and /dev/random will block, I think this is one of reasons to use urandom in openSSL).

But when you are generating some 4096-bit RSA key for 20-year SSL certificate, you want to use machine with good sources of external entropy, correct saving/restoring of entropy around reboots and which was used by human for some time.

Actually it is better to generate more valuable keys when true hardware random sources are available (not the Linux LRNG - PRNG), for example some balanced thermal noise measuring scheme (take only the lowest precision bit of Analog-to-digital converter - ADC). There is good hardware random source (thermal noise of loop of invertors with AES of their output) even in modern Intel CPUs (may be in VIA's cpus too, dont' know about AMD or ARM), check the /dev/hwrng device on your servers. Update There are possible flaws in some HW RNG (paper 2013) which are very hard to check, because the flawed random data is encrypted by private key of device maker.

And the only right way of working with high-valuable keys - is to generate them on (inside) certified HSM (Hardware security module) and keep them in full version (full private key) only inside tamper-resistance HSM (try to open such HSM's case, or remove their battery and your private key will evaporate. Funny case is when the key was the most master key of some bank - millions of PIN-codes may be lost in a moment...).  Extraction of the private key is allowed only as splitted form  - when there are N parts of key distributed around security officers (every part may be encrypted under officer's key) and K of parts are needed to reconstruct original key (e.g. via Shamir's scheme).

The main rule is to estimate the value of the information (e.g. your private photo costs around hundreds-thousands of money; but the SSL certificate of google or facebook costs billions of money), how long the information should be kept secure and how much will be invested to break your information. E.g. It may cost around 100-500 thousands money to setup a rubber-hose cryptanalysis (stealing somebody or something who knows/can access the secret/contains the secret and apply garage wrench/expostulations/soldering iron to get the secret -- soldering iron should be used only to unsolder flash memory chip from flashcard, not to something else), so the HSM and splitted backup of key is the only variant for valuable keys of banks and IT-giants.

  2b) Is there a flag or option in openssl where you can choose to use /dev/random instead in case you want to be sure?

There is a hack to force openssl to use data from /dev/random: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=88728

   dd if=/dev/random bs=1 count=1024 of=filename;
   export RANDFILE=filename
   # use openssl here

(you can verify with strace that openssl actually opened the "filename" to get random and did not open /dev/urandom)

  3) On a shared box, is there any way a neighbor could deplete all the randomness on the system, and force you to generate a weak key? It seems like blocking until there was sufficient entropy would solve this (#3) above.

There is a way to deplete most randomness, (even remotely, via TCP-syn cookie generation, see section 3.4 of 086 paper; around 64-128 bits are reserved to be available only to /dev/random, page 18 of 251.pdf). But even when depleted, neighbor can't predict your generated key via urandom cryptographic weakness only by listening to /dev/random and urandom. Both of you will get partial SHA1-s of different parts of SHA1 of pools (each refilled with parts of SHA1 from primary pool), and no one of your should be able to reconstruct state of primary pool. Worst case is when using urandom and there is 0 available_entropy (this may be bit hard to achieve). And even in this case your will get cryptographic pseudo-random generator with unknown seed. The attacker is forced both to hack recursive SHA1 and to precisely guess seed (128 bytes of random information if the entropy is depleted or 512 bytes of primary pool in non-depleted case). This task is unbelievable to be solved even when there is only one user in system which got all output of urandom exclusively (if he still have no primary pool contents at some time).

Root of shared machine can do everything: write kernel module to dump state of primary/secondary pool; emulate that there is 16 millions bits of available entropy while /dev/random will output in loop something like SHA1("THIS IS TRUE RANDOM,BELIEVE ME"); steal memory dump of your openssl process to dump the key; read your stored on the fs private key;  intercept the key presses sent from you to "your" openssl as passphrase to decrypt your safely stored private key. And the clever neighbor if he is the Wolf in sheep's clothing, will try to get root access to get your keys.

Clever attacker on shared machine may try to install side-channel attack against your crypto library and crypto algorithm, and there are actual attacks, e.g. using precise cache measurements (Bernstein 2005: "Cache-timing attacks on AES"), even if he lives in other virtual machine. This was one of reasons to e.g. move AES crypto inside the Intel CPU as separate hardware block not prone to cache side-channel leak.

So, don't use public/shared machines or machines out of your control (you should be root or somebody reliable should be) to do crypto with valuable information.

  4) Given a public/private key you've already generated - is there any way you can prove it was generated with low entropy?

I think no, if pools were correctly initialized, and their contents is kept secure (no root attacker).

In some very bad embedded installations without timekeeping (device boots to 1970), without pool saving/restoring (or with too late restoring, after urandom read, like in some ubuntus), without any random inputs before key was generated; when keys were generated by some startup script; then attacker may model the state of pool and regenerate the same keys.

And there is a paper with searching of weak keys generated on devices with low entropy: https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices". They detected bad keys ... by scanning millions of devices and comparing their keys:

  In the case of TLS, at least 5.23% of hosts use manufacturer default keys that
  were never changed by the owner, and another 0.34% appear to have generated the same keys as one or more other hosts due to malfunctioning random number generators.

And by checking for weakness in keys; again - by comparing a lot of scanned keys, for RSA they found many modules N1 and N2 where N1=p1*q1 and N2=p1*q2. I understand this situation as there are weak keys, but you can't distinguish weak key from good key. But if the key was generated from fixed low-entropy device state (first boot, early generation), then there is some probability to find another device (same HW platform) which generated same p or q as first device (if both, N will be the same).

  Even more alarmingly, we are able to compute the private keys for 64,000 (0.50%) of the TLS hosts and 108,000 (1.06%) of the SSH hosts from our scan data
  alone by exploiting known weaknesses of RSA and DSA when used with insufﬁcient randomness. In the case of RSA, distinct moduli that share exactly one prime factor will result in public keys that appear distinct but whose private keys are efﬁciently computable by calculating the greatest common divisor (GCD).

DSA requires the "ephemeral key k" to be generated with lot of entropy. k should not repeat for different messages, but some k were same.

  Nearly all (vulnerable hosts) served information identifying them as headless or embedded systems, including routers, server management cards, ﬁrewalls, and other network devices. Such devices typically generate keys automatically on ﬁrst boot, and may have limited entropy sources compared to traditional PCs

  .. Linux’s random number generator (RNG) can exhibit a boot-time entropy hole that causes urandom to produce deterministic output under conditions likely to occur in headless and embedded devices.


Problem about complexity of Chinese remainder theorem

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.
Any ideas?

Well, the standard way to solve for $x$ (given that $n_0, n_1$ are relatively prime) is to compute:
$$x = n_1 ((a_0 - a_1) n_1^{-1} \bmod n_0) + a_1$$
(where $n_1^{-1}$ is computed modulo $n_0$)
It is straightforward to verify that:
$$ 0 \le x < n_0n_1$$
$$ x \equiv a_0 \pmod{ n_0 }$$
$$ x \equiv a_1 \pmod{ n_1 }$$
As for the cost of the computation, $n_1^{-1}$ can be computed with $O(\log N)$ multiplication operations; the rest of the operations are two multiplication operations (one modulo $n_0$), and two addition/subtraction operations.

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.

So, in Pohlig-Hellman, you compute $H = a_0(n_1G)$ and $H = a_1(n_0G)$, and combine $a_0$ and $a_1$ to form the value $x$ s.t. $H = xG$.  Computing $a_0, a_1$ takes $O(\sqrt{\max(n_0, n_1)})$ multiplications (assuming the curve does not have any special form that allows us to compute the discrete logs faster); combining $a_0, a_1$ doesn't take any (because those are computed using integer computations, not elliptic curve operations).


Lattice attacks against Multilinear Maps [CLT13]

1. Why can't we find the vectors $\mathbf{r}_i$ by Gaussian Elimination?

The problem here is that $\mathbf{r}_i$ are small. You can use Gaussian Elimination to recover vectors orthogonal to $(\mathbf{u}_1, ..., \mathbf{u}_{t-n})$, but the vectors found will not be short vectors.

2. How to get encodings in level-zero?

Actually, one does not get encodings in level-zero. All the encodings are in level-one, i.e. multiplied by $z^{-1}$  (inverse modulo $x_0$).

However, this is irrelevant for the attack because the definition of the orthogonal lattice is:

$$L=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0 \}$$

Thus, considering encodings at level-one means that we have $\mathbf{x} \cdot z^{-1}$ instead of $\mathbf{x}$. Therefore, we are actually constructing the following lattice:

$$L'=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \}$$

But since $\mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \Leftrightarrow \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0$, it holds that $L = L'$.

Hence, having $t$ encodings at level-zero or $t$ encodings at level-one is equivalent in this attack.


In general, a MAC with a known fixed "key" is not a secure hash.  That is, you can have a secure MAC (that is, someone without the key, but with a large number of message/MAC pairs, cannot come up with another valid message/MAC pair) that is not collision resistant, or even preimage resistant, if the attacker does know the key.

In addition, you don't have to come up with an artificial example to demonstrate it; AES-CMAC is not even preimage resistant if you know the key.  This is easy to demonstrate; pick an arbitrary message that is a multiple of 16 bytes; then it is straight-forward to find the specific 16 bytes you need to append to make the CMAC come out to the 16 byte value you picked.

In addition, this isn't specifc to AES-CMAC; MACs based on univeral hashes also have this property.  In fact, the only MACs (in common use) that I can think of which is actually secure as a hash with a public key would be HMAC (which, of course, is designed around a secure hash function).

Now, you mention the use of a hash as an "integrity verification"; if you're checking the integrity of a transmitted message (and use a secret key), a MAC is a perfect choice for this operation (and, in fact, a hash function might not work as well).  However, if you need something which is actually collision resistant (e.g. as a part of a signature scheme), then a MAC with a fixed key may have serious problems.


What does the special form of the base point of secp256k1 allow?

One thing we know is that it doesn't allow any special attack.

Let us assume that we knew a special point $G$ that makes computing the discrete log easy, that is, given $xG$, it's easy (or at least, easier than expected) to recover $x$.

Then, given $H$ and $xH$, here's what we could do; we know that $H = yG$ for some $y$ (as $G$ is a generator), and so we can use our special purpose discrete log problem to recover $y$.  Similarly, we have that $xH = zG$ for some $z$, again, we can recover $z$.  So, we have $x(yG) = zG$, or $x = y{-1}z$; that immediately gives us the value $x$.

Hence, if they knew a 'weak point' $G$, that would imply that the entire curve is weak.  Since we don't believe that, we can assume that their special value $G$ is no weaker than any other point (as long as $G$ generators the entire group, which is true in this case)


If and why is it bad to scrypt a bcrypted password?

The combined strength of two key stretching algorithms is not greater than the sum of its parts. It is at best equal to the sum of its parts.

If you budget $x$ amount of CPU time to password stretching then you have to decide, do you give 100% of $x$ to scrypt? 100% to bcrypt? 50-50?

You can't give both 100% of $x$ to both scrypt and bcrypt because that's the same as doing a 50-50 split with double your initial time budget.

There is one important detail to scrypt that makes it better than bcrypt and PBKDF2. And that is that it is designed to use a lot of RAM. Storage with random access is hard to implement on ASICs in such a way that gives password crackers a significant advantage of the password-defender. The RAM use makes it hard to speed up cracking with GPUs as well.

Scrypt has a cost parameter. If you decrease it then it decreases both the amount of time that it uses and the amount of memory it uses. Bcrypt can be cracked faster than scrypt when scrypt is allowed high memory usage (and an equal amount of password-defender CPU time). So, when you take time (and thus memory) away from scrypt to give to bcrypt, you're letting a password cracker perform more guesses using less of their own resources.


Prove that two MACs with incremendal PRF application are not secure

The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself:

Let $f(k,m)$ be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the key (eg AES-128).

Why are the following MACs not sure?

[ref]
$\tau = c_i \oplus c_2 \dots \oplus c_n$, where $c_i=f(k,m_i)$.
[ref] $c_0=k$, $c_i=f(c_{i-1},m_i)$ for $i=1,\dots,m$ and $\tau=c_n$

To prove something insecure, we provide an explicit adversary. That is, we provide a method for doing what the security model says we shouldn't be able to.

In this case, that means we need are allowed to ask the system to provide us with the tag on some messages $\mathcal{M}=\{M_1,M_2,\dots\}$. Then, we create a valid tag for some message $M'\notin\mathcal{M}$.

So, a more direct hint: If you have the MAC of message $M=(m_1,\dots,m_n)$, can you construct...

Another message with the same tag?
A longer message who's tag you can calculate?


Fully Homomorphic Encryption over the Integers with Shorter Public Keys

If I understood well, you have two issues:

About the $2\beta$ values of $x$ "generating" $\beta^2$ values
About your the bugs in your code.

So, answering (1):   Notice that in the summation (and in your first for loop) for each $x_{i,0}$ you have $\beta$ different values of $x_{1,j}$, which means $\beta^2$ combinations of those $2\beta$ values. You are using the $2\beta$ values you have to perform $\beta^2$ products. Nothing special here.

The point (2) is harder because there are a lot of possible causes to the malfunction of your program. My first guess would be that you are not multiplying $r$ by $2$ in the line

c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x

but it may also be some problem with the intervals each parameter has to belong (are you sure you are respecting them?) or some other restriction imposed on the values. For instance, $x_0$ must be a product of a prime number $p$ with a random odd square free number $q_0$ that does not contain prime factors smaller than $2^\lambda$...

All those restrictions are there to guarantee security or correctness.


Who verifies the trust of certificate authorities?

Maarten Bodewes answer is correct but I think the heart of your question is a major hurdle people face in understanding certificates and CAs.  I think it's worth elaborating on the part of how this works that I think you are missing.

As stated in Maarten's answer, your computer/browser has been preconfigured with a set of trusted CAs.  If you are running Windows you can see what these are by running certmgr.msc (you must type the entire name in search).  In that application, you will see a number of folders.  One of these is named "Trusted Root Certification Authorities".  If you expand "Certificates" under that folder, you will see a long list of certificates for various CAs.

When you go to a website and you get a 'trusted' lock icon, that means that the certificate they are presenting has a parentage that includes a certificate in this store.  I'm oversimplifying slightly here but this is the core idea.  For example, if I look at the certificates at google.com, the grandparent certificate has the friendly name of "Google Trust Services - GlobalSign Root CA-R2".  I look at my store and I see that exact certificate which I can verify by looking at the 'thumbprint'.

So the reason that no one can MiTM the root certificates is that you are not going out to the CA to get your trusted CAs, you already have them on your machine.  If you browse a website with a CA cert that don't have in your trusted CA store, your browser should throw a lot of warnings at you that the site is not trusted.

I hope this helps.  A side note is that this should also help you to understand how much risk there is in importing a new trusted root certificate.  For example, let's say you are doing some experimentation and generate your own 'CA' certificate.  You import this as a trusted CA and voilà! You now can sign certificates that your browser trusts.  But consider what could then happen if someone else gets access to the private key you generated for that root CA.  They now can create a certificate for any  website and unless you check the cert chain on each site you go to, you could become subject to a MiTM attack.


How to use cryptography to protect video from forgery?

Most video formats generate periodic key frames where the entire picture is rendered and then specify subsequent frames which are differences from the previous image.  This is beneficial because this dramatically reduces the amount of data that needs to be transmitted, while still allowing periodic seeking.
It would be possible to embed a cryptographic signature covering the previous or current key frame and its subsequent data, but the video format would have to support it.  This would be the least invasive way of doing the operation because without transcoding, a user cannot efficiently seek to any point in the stream other than a key frame.  Sometimes these offsets are stored in an index at the end of the file, and, assuming the format supported it, you could add an additional index for that purpose.  I cannot speak to the contents of video formats that would support this.
You would want to include as part of the signature some additional metadata, such as a stream ID and a key frame count or timestamp to avoid unexpected out-of-order editing and splicing.  You are also probably going to want to include the full header data and any other structural data as well.  The data included in the MAC of TLS is a good example of protecting the full record appropriately from tampering.
And, of course, all this verifies is that someone with the private key created the signature, not who that was or whether the data is accurate.  If your camera is not sufficiently tamper resistant, malicious parties will be able to extract the private key.  If the camera is tamper resistant but is presented with a false or misleading image to record, it will of course record false or misleading data.  Cryptography and security cannot prevent people from presenting false or misleading data as fact.  You'd definitely want to consult with a suitable expert in tamper-resistant systems to make the system as secure as is practically possible.


Is there a way to make RC4 (ARCFOUR) secure, or is it completely broken?

A few observations:

RC4 suffers from related key attacks. This means your idea of concatenating a 224 bit key and a 32 bit IV is not a good idea. You should rather use $\operatorname{SHA-256}(Key\mathbin\|IV)$
Remember that a (Key, IV) pair must not be reused, ever.
A 32 bit IV can work if it's a counter, but IMO such a scheme is unnecessarily fragile. I'd rather generate a new, random 128 bit value for each encryption.
Even with dropping, RC4 is still a bit biased. This can allow password recovery if an attacker can observe a few billion communications.
You don't protect data integrity. For example an attacker might keep the encrypted password intact, but change the rest of the message. I don't understand your problem well enough to know if that's a problem.
There might be replay attacks, where an attacker repeats an earlier message fully or in part.
Your assumption that RC4 is faster than other ciphers isn't necessarily true. On many modern systems AES is really fast. There are also other modern stream ciphers, such as Salsa20 which are fast and much stronger than RC4.
RC4 has costly initialization. So its only fast if you need to initialize it rarely. In particular if you reinitialize for each packet, its performance will certainly drop below AES.
Do you really need a cipher in the first place? You might be better off with a MAC. It seems like you're interested in authentication, not confidentiality. Universal MACs can be really fast.
User Passwords often have low entropy, so you need to strengthen them before using them as a key. Strengthening them is computationally expensive, and is done using KDFs, like scrypt or PBKDF2.
Consider using a high entropy key instead of a password.
If you use a constant key hardcoded into an executable, those executables may never run on untrusted machines. Else an attacker could simply extract the key out of the executable.

In short:

The weaknesses in your protocol are likely much more severe than the weaknesses in RC4.
There is little reason to use RC4 in a new protocol. There are fast and strong alternatives.


Does RSA - the company - know the $p$ and $q$ used to create $n$ ($p$ and $q$ being prime)

In short , should I trust a private company with my encryption?

In short, no, you shouldn't and you don't have to. That is the beauty of the RSA encryption algorithm (which is completely separate from RSA the company). You can use RSA the algorithm without RSA the company knowing anything about it.

If you want to communicate securely with RSA the company using RSA the algorithm, you tell RSA the company your RSA (the algorithm) public key, which includes $n$ (as well as the encryption exponent $e$). They don't need to know $p$ or $q$ or $p-1$ or $q-1$.


Leading coefficient of a rational function was defined at 5.3
on page 11 of Report 31
as another function (multiplied by (x/y)^d for some d)
evaluated at identity.

Handling the case of point at identity was explained at top of page 8,
namely multiplying numerator and denominator by y^d and x^d
to make them of the same degree,
resulting in another rational function that is finite and not zero at identity.

Degree of a polynomial of canonical form was defined at 3.6 on page 5;
reduction to this form was explained after definition 3.1 on page 3.

Evaluating a rational function at identity is explained at definition 3.9 page on 5
as the ratio of leading terms of numerator and denominator.

I would expect reduction to canonical form to be a likely reason of confusion.

UPD: For explicit example, let's take a look at Proposition 7.6, leading coefficient of $g_n(x)$ evaluated at identity, with $(g(P), h(P))$ defined at the start of Section 7 "Multiplication by $n$" and $g(P)$ depending only on $x$-coordinate of the point (Exercise 7.5). It was proved by induction on page 23. Corollary 7.7 is likely of major interest for such a question.


Confused with 128-bits AES round numbers

So my question is: it says 10 cycles, but does that mean that the initial round is performed once, the normal rounds 9 times, and the final round also once? Because the expanded key is 176-bytes, so the addroundkey function can be used 176/16 = 11 times.

For the 128-bit AES, that is correct.

InitialRound, which consists of AddRoundKey is performed once.

Rounds, which consist of SubBytes, ShiftRows, MixColumns, AddRoundKey is performed nine times.

Final Round, which consists of SubBytes, ShiftRows and AddRoundKey is performed once.

Also, you might want to check out this two flash animations which offer great insight into how 128-bit Rijndael (the cipher AES is based on) works and also allows you to view the intermediate results as the cipher progresses.


RSA key pair generation and FIPS 140-2, 186-4

FIPS 140-2 specifies conditions applicable to the environment of RSA (and other) key generation, and refers to FIPS 186-4 for the generation itself.

Several recent Java Card Smart Cards can internally generate RSA-2048 key pairs per FIPS 186-4, with security policy and FIPS 140-2 level 3 certificate to attest that. Here is the one on top of the list at time of writing. A trivial Java Card applet runnign in that Smart Card's Java Card Virtual Machine can generate such RSA key, and export the private key, in clear if you want that. Such key would be for a FIPS-approved algorithm (certs# 1506-1507), and generated according to FIPS 186-4, as attested by a FIPS 140-2 level 3 certificate. That's not enough to pretend that the key was generated in a FIPS 140-2 compliant environment, because the security policy mentions

"The module is a limited operational environment under the FIPS 140-2 definitions";
accordingly the FIPS 140-2 level 3 certificate does not cover "operation environment";
"firmware loaded into this module (..) requires a separate FIPS 140-2 validation" where my reading is that this sentence applies to Java Card applets.

However a (less trivial) Java Card applet could "securely generate RSA key pair (with) access to private exponent in order to process it further" (as asked), for some definition of process like encryption of the private key under a master public key (a form of key escrow). I do not rule out that a FIPS 140-2 validation of that applet could be obtained, such that it would then be correct to tell that the RSA key pair was generated in a FIPS 140-2 validated environment.


Is changing $H(R\mathbin{\Vert}A\mathbin{\Vert}M)$ to $H(R\mathbin{\Vert}A\mathbin{\Vert}H(M))$ in EdDSA secure?

Assuming this is the paper you're talking about, your modification completely eliminates resilience to collisions in the underlying hash function $H$. The EdDSA scheme (and in the Schnorr scheme on which it is based) is highly resilient against collisions in $H$. Specifically, in the generic group model, the Schnorr scheme has been proven to be secure even if $H$ isn't collision-resistant; all it requires for security is that $H$ be resistant to random-prefix preimage attacks and random-prefix second preimage attacks (essentially, given random $R$: given $h$ it's hard to find $M$ s.t. $H(R||M)=h$, and given $N$ it's hard to find $N^\prime$ s.t. $H(R||N)=H(R||N^\prime)$ and $N\ne N^\prime$).

So EdDSA can be perfectly OK with a not collision-resistant hash; as far as we know, it doesn't need collision resistance, just random-prefix preimage and random-prefix second-preimage resistance.

However, your modification is trivially vulnerable to a collision in $H$: If $H(M)=H(M^\prime)$, then if you hash $M$ before signing, you end up with an EdDSA signature of $H(M)=H(M^\prime)$ which (under your modification) is a signature for $M^\prime$. If you instead do $H(A||M)$, an attacker who finds any chosen-prefix collision can create two messages such that a signature for one is a signature for the other. If you use $H(A||M)$ as the thing to be signed, someone who can find any two messages s.t. $H(A||M)=H(A||N)$ again can take a signature for one and use it as a valid signature for the other. With a good hash function, they can't find said collision, but Schnorr (and so EdDSA) is designed such that it doesn't break if they can do that.

If someone gets a message $M$ signed with $(R,S)$, and finds a second preimage for $H(R||A||M)$ (i.e. $M^\prime$ s.t. $H(R||A||M^\prime)=H(R||A||M)$, then the signature for $M$ is valid for $M^\prime$. However, an attacker with just the ability to find collisions cannot exploit this: they do not control $R$, and $R$ is different for each $M$. So finding a collision in $f(M)=H(R||A||M)$ is useless for the attacker; to exploit the collision, one of the colliding messages must have $H(h||M)B=R$, which is not going to be the case for a generic one of a colliding pair. Collision attacks do not apply, because a colliding pair only helps if they collide when prefixed by a secret function of one of them, which will not generally be the case.


Using GMAC for Authentication without encrypting the message

GMAC is quite simply GCM mode where all data is supplied as AAD (or additional authenticated data), or as NIST SP 800-38D puts it:

  If the GCM input is restricted to data that is not to be encrypted, the resulting specialization of GCM, called GMAC, is simply an authentication mode on the input data.

If you don't have access to a cryptographic provider that supports GMAC directly (e.g. Bouncy Castle provides a AES-GMAC JCE Mac) you can simply use any AES/GCM implementation by providing all data as AAD, and an empty message for encryption.

e.g. adapting your example to do GMAC only:

... as for AES/GCM ...
c.updateAAD(head);
c.updateAAD(data);
byte[] mac = c.doFinal();
System.out.println("GMAC: " + SomeHexEncoder.encode(mac));

If you need to be certain you're getting it right, the GCM/GMAC test vectors from the NIST CAVP page can be used (everything with a PTlen = 0  is a GMAC test vector).


First : Welcome to Crypto.SE.

Even though you are quite young, it should not be a reason for someone to stop you : Alan Turing was 23 (still undergraduate) when he undermined the work of Alonzo Church (on untyped $\lambda$-Calculus). I'm not saying you should always provide your idea, but if you can defend them, have fun.

About your cipher : The first thing you should do, is to analyze your own cipher (Differential Cryptanalysis... Linear Cryptanalysis...) An overkill approach would be in the same way that Joan Daemen and Vincent Rijmen did for Rijndael. If you submit a cipher, one would expect at least a formal analysis of why you think this is a good idea. One is unlikely to spend time to review your work if you did not prove your part at the beginning. However, the same principle apply as writing clever code :

  Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
  - Brian Kernighan

If you can't break a block cipher, it doesn't mean that other won't.

Some hint about how to start :
- How do you test the security of your cipher?
- How do I test my encryption? (absolute amateur)

Most ciphers are published (or at least get known) in competitions such as :

AES in 1997,
CRYPTREC,
NESSIE,
or at the moment CAESAR (Authenticated Encryption).

And if you think your idea is really great, you can also try to submit it as a paper to a workshop, Journal or conference. Here are some examples (and accepted) submissions that you probably never heard of :

SQUARE
SHARK

Good Luck !


Oblivious transfer with trusted third party Trent

Alice computes $C_0$ and $C_1$ as follows:
If $b=0$ (this means $t=m$), Alice computes $$C_i = M_i \oplus R_i.$$
Otherwise (i.e. when $t=1-m$), Alice computes $$C_i = M_i \oplus R_{1-i},$$
where $i \in \{0,1\}$.

Bob computes $M_m$ as
$C_m\oplus R_t$.


I am wondering, why I cannot use a plain one-time signature mechanism to sign an unlimited sequence of messages

You can; your method does exactly that.  However, it assumes that the verifier sees all previous signatures before verifying the next - not all use cases can assume that.


Does SIV mode work for asymmetric encryption?

Taking the hash of the message as IV would not be secure, since, like Ricky Demer mentioned in comments, it would make the hash public and allow guessing. However, that is not what SIV mode does – it uses a MAC as IV.

Doing that with ECIES would be possible, but probably not a good idea:

Normal ECIES has single-use symmetric keys, so it requires no IVs.
For the same reason ECIES+SIV would not be deterministic, if that is the objective.

Unless SIV happens to be the best kind of encryption available for other reasons, there is no advantage over other forms of authenticated encryption, and probably downsides like speed (since it requires two passes over the data).

With other asymmetric systems it may be another matter. E.g. Curve25519 uses static Diffie–Hellman keys for both the receiver and sender, so using SIV would avoid total breakage on nonce reuse.


Embed usually implies the target algebraic structure is of larger cardinality (assuming finite). So, I would say project.


Converting common reference string to common random string

There is no generic conversion, but it is a standard property of dual-mode NIZKs. Here, the CRS comes in two indistinguishable modes, where one is structured, but the other is actually a truly random string. Typically, in group-based construction, the random CRS will be a tuple of random group elements, while the structured CRS will be a DDH tuple - both will then be indistinguishable under the DDH assumption.
At a very high level, the reference string will be used as a parameter of some commitment scheme in which you put the witness in the NIZK. Then, using some appropriate construction of commitments, the commitment can be perfectly hiding as long as the CRS is random, but becomes perfectly binding as soon as the CRS is structured. Think for example about Groth-Sahai-style dual-mode commitments, which have a similar property.
Some recent examples of NIZKs with this property include this work.


how does BearSSL's GCM modular reduction work?

There are three important points here to consider.

1. We work in $\mathbb{F}_2[X]$. This means that we do additions and multiplications of binary polynomials, i.e. polynomials whose coefficients are 0 or 1. The addition of two polynomials is then a bitwise XOR; there is no carry propagation. Similarly, the multiplication is called a "carry-less" multiplication. There are some explanations about that here.

In particular, the "modular reduction" is about divisions of polynomials, not integers. The modulus is the binary polynomial $X^{128} + X^7 + X^2 + X + 1$ (it is an irreducible polynomial over $\mathbb{F}_2$, which implies that when computing stuff modulo that polynomial, we work in a finite field).

2. There is a fair amount of confusion about encoding. This is a problem from the GCM specification. The input bytes are to be interpreted as bits, i.e. the coefficients of a binary polynomial. "Endianness" is about how to map chunks of an element (e.g. bits in a byte) to their mathematical value. For instance, if you consider a byte of numerical value 0xC9 (201 in decimal) and write it down as a sequence of bits, you normally use big-endian notation, i.e. you write it as "11001001": the leftmost bit is the one with the highest value ($2^7 = 128$), the rightmost is the one with the lowest value ($2^0 = 1$). This is what happens with integers; with binary polynomials, the big-endian interpretation of a byte is to map the leftmost bit to the coefficient of $X^7$, and the rightmost to the coefficient of $X^0$; hence, "11001001" would be decoded as $X^7 + X^6 + X^3 + 1$.

The concept of endianness works at all levels; i.e. not only bits within bytes, but also for bytes within a sequence of bytes. The "pure big-endian" interpretation of a sequence of 16 bytes would be to decode each byte in big-endian (as above), then assemble all bytes with the most significant byte coming first, i.e. the first byte in the sequence corresponding to binary coefficients $X^{127}$ to $X^{120}$, the second byte being for coefficients $X^{119}$ to $X^{112}$, and so on. BearSSL decodes input values in pure big-endian interpretation; internally, it stores them not into bytes, but into 32-bit words:

            /*
             * Decode the block. The GHASH standard mandates
             * big-endian encoding.
             */
            yw[3] ^= br_dec32be(src);
            yw[2] ^= br_dec32be(src + 4);
            yw[1] ^= br_dec32be(src + 8);
            yw[0] ^= br_dec32be(src + 12);

Here, yw[0] will contain coefficients $X^0$ to $X^{31}$, yw[1] coefficients $X^{32}$ to $X^{63}$, and so on.

Now there is a lie here. The GHASH standard does not really mandate big-endian encoding. It, in fact, mandates the complete opposite, which is pure little-endian encoding, i.e. not only the first byte should be for coefficients $X^0$ to $X^7$, but the bits within that byte are interpreted in "unnatural" order, i.e. the most significant bit (of numerical value 128) is for coefficient $X^0$, not $X^7$. This little-endian convention of bits within bytes is very inconvenient for computations, especially since BearSSL implements the carryless multiplication by way of multiplications on plain integers (i.e. multiplications with carries, but using masks and holes to remove these carries where necessary). If BearSSL were to use pure little-endian convention, it would then have to swap bits around within bytes, a cumbersome operation which would degrade performance and increase code size.

Instead, BearSSL uses a trick, which works on binary polynomials. Namely, if you define bit reversal:
$$ \mathrm{rev}_n \Big(\sum_{i=0}^{n-1} a_i X^i\Big) = \sum_{i=0}^{n-1} a_{n-1-i} X^i $$
then, when multiplying two polynomials $A$ and $B$ of degree less than $n$ (i.e. that fit on $n$ bits):
$$ \mathrm{rev}_n(A) \times \mathrm{rev}_n(B) = \mathrm{rev}_{2n-1}(A \times B) $$
i.e. if you reverse the two operands, you get the reverse of the product. This does not work at all on plain integers, because additions on plain integers have carries, and carries propagate in a definite direction (right-to-left, in the usual notations), and that does not work "in a mirror". But with carryless multiplication, there are no carries, and everything can be mirrored.

What that means here is that, by decoding 16 bytes with pure big-endian notations, BearSSL does not get the expected polynomial $A$, but $\mathrm{rev}_{128}(A)$. The product is then computed over reversed operands, and yields the reverse of the expected value. If that result is to be reencoded back with pure big-endian notation, then everything works fine! The compatibility of operations with bit reversal ("mirroring") means that you can really choose the encoding convention you want, and you get the right result, provided that you stick to your convention throughout.

... Except for one small detail. If you look at the equation above, the product of two bit-reversed 128-bit polynomials yields the bit-reversed result over 255 bits, not 256. The BearSSL code ends up with a 256-bit result in zw[], and that value is shifted by one bit, because of that reversed convention issue. Thus, the code must include a shifting step to put it back where it should, and this is the first half of the code you reproduce in your question:

           /*
             * GHASH specification has the bits "reversed" (most
             * significant is in fact least significant), which does
             * not matter for a carryless multiplication, except that
             * the 255-bit result must be shifted by 1 bit.
             */
            zw[0] = c0 << 1;
            zw[1] = (c1 << 1) | (c0 >> 31);
            zw[2] = (c2 << 1) | (c1 >> 31);
            zw[3] = (c3 << 1) | (c2 >> 31);
            zw[4] = (d0 << 1) | (c3 >> 31);
            zw[5] = (d1 << 1) | (d0 >> 31);
            zw[6] = (d2 << 1) | (d1 >> 31);
            zw[7] = (d3 << 1) | (d2 >> 31);

Thus, these lines are really about making it as if everything had been done in pure little-endian convention, whereas it was done in pure big-endian convention.

3. Modular reduction is over binary polynomials. We work modulo polynomial $M = X^{128} + X^7 + X^2 + X + 1$. This means that for any polynomial $P$, we can add (or subtract, but in $\mathbb{F}_2[X]$, addition and subtraction are the same thing, i.e. a XOR) arbitrary multiples of $M$. The "modular reduction" of the 255-bit result $P$ really is an addition of multiples of $M$ until we get something that fits on 128 bits.

Write the polynomial to reduce $P = \sum_{i=0}^{254} p_i X^i$. Take one coefficient $p_i$ for some $i \ge 128$; we want to "cancel that bit", in case it as value $1$; the trick is to add $M\times X^{i-128}$. In other words, we add:
$$ p_i M \times X^{i-128} = p_i X^i + p_i X^{i-121} + p_i X^{i-126} + p_i X^{i-127} + p_i X^{i-128} $$

The first part ($p_i X^i$) merely clears the bit at position $i$ (it's a XOR of $p_i$ with itself), but the other parts "inject" (XOR) bit $p_i$ at other places down the sequence of coefficients. Crucially, these are relatively far (121 or more bits down the sequence), which allows us to process bits by large chunks (this is the reason the modulus was chosen with that value). Consider the first iteration of that loop:

            /*
             * We now do the reduction modulo the field polynomial
             * to get back to 128 bits.
             */
            for (i = 0; i < 4; i ++) {
                    uint32_t lw;

                    lw = zw[i];
                    zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
                    zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
            }

The word zw[0] contains the coefficients $X^{255}$ to $X^{224}$. Since the coefficients for $X^i$ must be injected at positions $X^{i-121}$, $X^{i-126}$, $X^{i-127}$ and $X^{i-128}$, these 32 bits end up being injected in various positions in zw[3] and zw[4]. In the line that updates zw[i+4] (i.e. zw[4] during the first iteration), we see the XOR with lw, which is the injection of bits at positions $X^{i-128}$; the lw >> 1 is the injection of bits at positions $X^{i-127}$; and so on.

Nominally, we should clear the high bits (zw[0] to zw[3]) but this is optimized out, since we don't look at these bits again; the useful result, after reduction, is in words zw[4] to zw[7]:

            memcpy(yw, zw + 4, sizeof yw);

And that's the complete modular reduction.


The question is whether someone apart from the TC can find the factorization of $m$.

Yes, however I will first address the easier to answer question of "could the holder of private key $a$ decrypt traffic to the holder of private key $b$"

The answer to that is "yes"; Alice, the holder of the private key $a$ has $e_a$, $d_a$, and $e_b$ (Bob's public key).

We know that $e_a d_a \equiv 1 \pmod {\lambda(n)}$ (where $\lambda(n) = \text{lcm}(p_1 - 1, p_2 - 1, ..., p_k-1)$, that is, $e_a d_a - 1 = m\lambda(n)$ for some integer $m$.  So, what Alice can do is compute $d'_b = e_b^{-1} \bmod{ e_a d_a - 1} = e_b^{-1} \bmod{ m\lambda(n)}$; it is easy to see that $e_b d'_b \equiv 1 \pmod{ \lambda(n)}$, that is, $d_b'$ will work as a decryption key for traffic to Bob.  It likely not to be larger than Bob's key $d_b$, however it is not so large that Alice can't practically use it.

However, to address the question "could Alice factor $n$ (even though the above argument shows she doesn't need to)", the answer is "yes"; the same probabilistic method that works against two factor RSA primes also works in this case (it just may take more iterations to complete the factorization).

To review: Alice computes $e_a d_a - 1 = 2^k z$ for $k$ large enough to make $z$ odd.  Then, she selects a random value $g$ and computes:

\begin{align*}
  h_0 &= g^z \bmod n \\
  h_1 &= h_0^2 \bmod n \\
  h_2 &= h_1^2 \bmod n \\
      &\vdots \\
  h_k &= h_{k-1}^2 \bmod n
\end{align*}

It should be clear that, unless the original $g$ just happened to not be relatively prime to $n$, that the final value $h_{k} = 1$; we look at the largest $i$ where $h_i \ne 1$.  If $i > 0$ and $h_i \ne -1 \pmod n$, that gives us a nontrivial factor $\gcd(n, h_i - 1)$.

It can be shown that at least half the possible initial $g$ values will yield a factor, and that this factor is effectively random over the possible factorizations, hence rerunning this test using different $g$ values will quickly reveal all the factors.


Why does DH-EKE require that public keys be indistinguishable from random?

In DH-EKE, Alice needs to encrypt her chosen public key with the shared password. If the public keys do not look random, an attacker can try to decrypt Alice's first encrypted message to recover a small set of possible passwords, merely by checking if the decrypted message belongs to the public key space or not. Note that this is an offline attack, which is the type of attacks that PAKE protocols aim to prevent.


Should AES.decrypt(ct, wrong_key) return blank or wrong result?

AES is a block cipher and would return wrong data when a wrong key is used. It only works on a single block of data (16 bytes). The default CBC mode of operation enables you to encrypt multiple blocks of data. The padding then enables you to encrypt plaintexts of arbitrary length. The padding has to be removed somehow after the decryption.

You're seeing a blank output, because your data is short and the padding removes more bytes than necessary. Here is how the default PKCS#7 padding is implemented in CryptoJS:

unpad: function (data) {
    // Get number of padding bytes from last byte
    var nPaddingBytes = data.words[(data.sigBytes - 1) >>> 2] & 0xff;

    // Remove padding
    data.sigBytes -= nPaddingBytes;
}

So, it looks at the last byte of the decrypted byte and removes as many bytes from the ciphertext. If data.sigBytes is negative, it would handle it like 0 bytes where decrypted. If your message is longer than 255 bytes, then the decryption is guaranteed to print something, but it won't be as long as the initial plaintext. If you always want to print something then you need to decrypt without padding.

I wouldn't call this implementation wrong, because PKCS#7 padding is specified for up to 256 padding bytes, but rather data.sigBytes -= Math.min(nPaddingBytes, blocksize); would have been probably better.

Zero padding might be better suited in your case, because it's highly unlikely that a decryption with a wrong key results in a plaintext that ends with many zero bytes at the end that have to be removed. But such as padding should not be used when there is a chance that you might encrypt a plaintext which ends in 0x00 bytes.

  So that the result is 'compliant' to the expected result but it's not the expected result, and there is no way to understand if the key was right or wrong depending on the result of the decryption.

This is not generally possible with a block cipher. A decryption with wrong key can result in some arbitrary plaintext bytes that doesn't have to make up a string with valid ASCII or UTF-8 encoding and if you try to force it, you will get errors, which can be used to distinguish the correct key from a wrong key.

If you're always encoding the plaintext to Hex, then you can get away with using arbitrary keys.

Related:

Does AES specify error messages when using the wrong password to decrypt?
Is it possible to find data which makes sense when decrypted with different keys?


Hashing a message with a length that isn't a multiple of 8 bits

Such libraries most certainly do exist; see here and here for two examples.

A hash implementation that can handle odd-sized bit strings is called "bit-oriented"; most implementations don't bother with it (just because the requirement just doesn't come up that often), however, a few do.


Key size and finite fields in ECC (References)

The security level is usually taken to be an estimate of the $\log_2$ of the expected cost in bit operations of the best attack attaining probability near 1 of success.  In the case of well-designed elliptic-curve cryptography for a curve $E/k$ over a field $k$, this is usually determined by the cost of the best algorithm for computing discrete logarithms in a subgroup of $E(k)$, the $k$-rational points of $E/k$, with large prime order $\ell$.

The expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, so, e.g., we estimate a 128-bit security level for breaking X25519, which works in a group whose order $\ell$ is 252 bits; see the discussion at SafeCurves for more on Pollard's $\rho$ cost, and for references to other types of attacks on elliptic-curve cryptography.  The order $\#E(k) = h \ell$ of the group $E(k)$ can't differ from $\#k$, the cardinality of the field $k$, by more than $2\sqrt{\#k}$, by Hasse's theorem; see an earlier answer I wrote for more on the relationship between field $k$, subgroup order $\ell$, and cofactor $h$.

The private key size is usually taken to be the number of bits it takes to encode a secret scalar in $\mathbb Z/\ell\mathbb Z$.  (Again, by Hasse's theorem, $\ell = \#E(k)/h$ can't be much more than $\#k$, and won't be much less unless the group has an unreasonably large cofactor $h$.)  This number of bits can't be less than twice the maximum security size because of the generic Pollard's $\rho$ attack cited above.  In some cryptosystems, though, we don't exactly store an element of $\mathbb Z/\ell\mathbb Z$ but rather a seed that we hash into one as in standard EdDSA, and in others we store $\mathbb Z/\ell\mathbb Z$ alongside other data as in some nonstandard extensions to EdDSA.

The public key size is usually taken to be the number of bits it takes to encode a curve point in $E(k)$.  There are different encoding schemes available.  You could naively encode a pair of elements of $k$, but that's a waste of space with a lot of redundancy that attackers can exploit.  You could encode one coordinate, and transmit the other as a single bit, which requires some work for the receiver to decompress.  You could use fancier compression schemes like Elligator or Decaf, which have better security properties.

Since there are so many different types of cryptosystems and ways to use elliptic curves out there, nothing more specific can be said in general about ‘key size’ unless you have a more specific question.


First of all, a more usual padding scheme would add 5 times the same byte 0x05 (in your example) so the check not just removes 5 bytes, but also checks that the 4 bytes before it have the same value. But let's assume your scheme (which is underspecified: what to put in the bytes before? Zeroes, or random values?) for now.

What if you cannot remove that many bytes? Do you allow for final bytes that exceed the block length (so remove more than one block)? (TLS does do this.) Do you just discard the data? But that's also observable, probably. And if the length of the final output is somehow observable, you leak the final byte of the last block which could also be used for a padding oracle style attack.

In general, use a cryptographic MAC to protect your ciphertext, and verify it first. Emit those errors. Then padding errors should not occur at all.


Layman's explanation of encryption backdoors

There are two somewhat orthogonal concepts in backdooring encryption algorithms:

The backdoor can be explicit or implicit. An explicit backdoor is one that everybody knows it is there. An implicit backdoor strives at remaining undetected by the algorithm owners. Of course, when there is an explicit backdoor, people tend to avoid the algorithm altogether, so explicit backdoors may hope to work only in the presence of a legal framework that forces implementers to use the backdoored system.

An example of an explicit backdoor is the Clipper chip (which was ultimately abandoned). The backdoor is not really in the algorithm, more in the assembly of algorithms into a protocol, and technically it was an automatic key escrowing method. For an implicit backdoor, see the Dual EC DRBG as a famous example: it worked only as long as nobody was aware that it was backdoored.
The backdoor's security may be quantifiable, or not. In the case of Dual EC DRBG, the mechanism uses well-trodden mathematical paths: the NSA knew that exploiting the backdoor required knowledge of an internal secret key, based on discrete logarithm (on elliptic curves).

A non-quantifiable security is what happens when you try to push, for instance, a voluntarily flawed algorithm, or one for which you know of a cryptanalytic method that you did not publish. This is a very dangerous game for a spy agency, because you cannot really know whether third parties could find the flaw or not. Such backdooring tends to backfire in the long term.

Interestingly, the NSA tends not to use non-quantifiable backdoors. A good example is DES. At the time it was designed, the NSA believed that it could tackle an upfront 256 exhaustive search, and that nobody else (in particular the Soviets) had the technology and budget for that. The NSA also knew of a novel cryptanalytic method (differential cryptanalysis). So when the NSA intervened in the design of DES, it insisted on shortening the key from 64 to 56 bits (that's addition of a quantifiable backdoor, and it was rather obvious, so quasi-explicit), and also on strengthening the design against differential cryptanalysis. This is a good example about how NSA consciously refrained from a non-quantifiable backdoor. There is only one thing that spy agencies fear more than not being able to spy: it is the idea that other competing spy agencies may also spy.

So a real, good backdoor is one that uses maths to offer quantifiable security against unauthorized usage of the backdoor. It is extremely difficult to have quantifiable security without making the backdoor explicit. The "best in class" in that area is Dual EC DRBG, and even before the Snowden business, cryptographers were already finding it weird and strongly suspected foul play (see the analyses back in 2007, 6 years before Snowden).


How can I process data within a cloud securely?

In general this seems not possible. To process the data, you need to have it in plaintext, and if you have it in plaintext an admin might read it.

However, if your processing needs to read only some parts of the XML (e.g. tag names), you could encrypt all other parts (e.g. field values, attributes). Information might still leak through the unencrypted parts.


The described method appears to be point decompression. Take care first that what you call "bytes" are actually bits. The value $k$ must be the right bit (hence $0$ or $1$), not the right byte.

Below is the general treatment of the question.

Binary Fields

Everything here happens in a binary field $GF(2^m)$ where things are somewhat different from integers. In a nutshell:

Every element of $GF(2^m)$ can be expressed as a polynomial of degree at most $m-1$, with coefficients in $GF(2)$. I.e. an element $d$ will be:
$$ d = \sum_{i=0}^{m-1} d_i X^i $$
such that each $d_i$ is either $0$ or $1$ (it's a bit).
Addition is done term-by-term in $GF(2)$, with no carry propagation of any sort: if $f = d + e$, then $f_i = d_i + e_i \bmod 2$. It is usually expedient to represent an element of $GF(2^m)$ by a string of bits (i.e. an array of bytes, each byte containing a bit); in that case, addition is really a bitwise XOR. Note that the addition of an element with itself yields $0$ (that's why the field is called "binary").
Multiplication is more complicated: you multiply the polynomials together (again, the coefficients are $0$ or $1$, and there is no carry to propagate anywhere); then the result must be reduced modulo the irreducible polynomial of degree $m$ that defines the field representation.
Every element in $GF(2^m)$ is a square, and has a unique square root.
Squaring in $GF(2^m)$ is actually known as the Frobenius automorphism and preserves both addition and multiplication:
\begin{eqnarray*}
  (ab)^2 &=& a^2 b^2 \\
  (a+b)^2 &=& a^2 + b^2 \\
\end{eqnarray*}
(The latter holds because $(a+b)^2 = a^2 + 2ab + b^2$, but $2 = 0$ in $GF(2^m)$.)
Since the field $GF(2^m)$ has order $2^m$, it follows that for every element $z \in GF(2^m)$, we have $z^{2^m} = z$.

Trace and Half-trace

Let's now consider the equation:
$$ z^2 + z = \beta $$
in $GF(2^m)$. To analyze it, it is convenient to define the trace:
$$ \text{Tr}(z) = \sum_{i=0}^{m-1} z^{2^i} $$
(This is still an addition in $GF(2^m)$. We don't use integers anywhere here.)

Now note that the trace is linear, i.e. $\text{Tr}(z+z') = \text{Tr}(z) + \text{Tr}(z')$ for all $z$ and $z'$ in the field (this is because the trace is really a lot of Frobeniusing). Moreover, the trace is preserved by squaring:
\begin{eqnarray*}
  \text{Tr}(z^2) &=& \sum_{i=0}^{m-1} (z^2)^{2^i} \\
                 &=& \sum_{i=0}^{m-1} z^{2^{i+1}} \\
                 &=& z^{2^m} + \sum_{i=1}^{m-1} z^{2^i} \\
                 &=& z + \sum_{i=1}^{m-1} z^{2^i} \\
                 &=& \text{Tr}(z) \\
\end{eqnarray*}
We used here that $z^{2^m} = z$. The squaring simply "rotates" the term, so we end up on the same value at the end.

Frobenius strikes again: since squaring preserves additions and multiplications, it will also preserve anything built out of additions and multiplications, including the trace. Thus:
$$ \text{Tr}(z^2) = (\text{Tr}(z))^2 $$
Taking the two together, we find that:
$$ \text{Tr}(z) = (\text{Tr}(z))^2 $$
for all elements of $GF(2^m)$. There can be only two elements in a field that are equal to their own square ("$t^2 = t$" is a polynomial equation of degree $2$, and thus can have only two solutions in a field). The values $0$ and $1$ are equal to their own square. This therefore demonstrates that the trace, formally an element of $GF(2^m)$, can only be $0$ or $1$.

Let's come back to our equation:
$$ z^2 + z = \beta $$
If we apply the trace on both side, then we get:
$$ \text{Tr}(z^2 + z) = \text{Tr}(\beta) $$
By linearity, and by equality of $\text{Tr}(z^2)$ with $\text{Tr}(z)$, we get that the left half of this equation can only be $0$. Therefore: if $\text{Tr}(\beta) \neq 0$, then there is no solution.

We will now show that if $\text{Tr}(\beta) = 0$, then there are exactly two solutions, that can be built with the half-trace.

The half-trace is defined as:
$$ \text{H}(z) = \sum_{i=0}^{(m-1)/2} z^{2^{2i}} $$
It really is the sum of half of the terms we used in the trace, hence the name of "half-trace". Also, an important note: I used the fact that we are working in $GF(2^m)$ for an odd integer $m$ (you did not say it, but I am willing to bet on it because $m$ is prime for all standard curves, and there are good reasons for that).

The half-trace, contrary to the trace, is not reduced to $0$ or $1$; however, it is still linear, because Frobenius. Consider now an element $z$, and compute the following:
\begin{eqnarray*}
  (\text{H}(z))^2 + \text{H}(z) &=& \sum_{i=0}^{(m-1)/2} z^{2^{2i+1}} + \sum_{i=0}^{(m-1)/2} z^{2^{2i}} \\
  &=& z^{2^m} + \sum_{i=0}^m z^{2^i} \\
  &=& z + \text{Tr}(z) \\
\end{eqnarray*}
Here, I am relying on the fact that $m$ is odd (I told you it's important), so that the first sum yields an extra $z^{2^m}$; and, of course, it is still a total Frobenius fiesta (you'll get used to it).

This expression gives us a solution to our equation. Indeed:
$$ (\text{H}(\beta))^2 + \text{H}(\beta) = \beta + \text{Tr}(\beta) $$
We saw that our equation can have solutions only if $\text{Tr}(\beta) = 0$. If that is the case, then one solution is $z = \text{H}(\beta)$.

It is easy to see that is $z$ is such that $z^2+z = \beta$, then $z+1$ is also a solution (because $(z+1)^2 + z = z^2 + 1 + z + 1 = z^2 + z$). Our equation is polynomial and of degree $2$, so it cannot have more than two solutions.

To sum up: the solutions to $z^2+z = \beta$ are $\text{H}(\beta)$ and $\text{H}(\beta)+1$. These solutions work only if $\text{Tr}(\beta) = 0$; otherwise, the equation has no solution. Note that "adding $1$" means, in a binary field, XORing the low-order bit with a $1$. In other words, the two solutions, when they exist, differ only by their low-order bit.

Point Decompression

Let $E$ be the elliptic curve of equation $y^2 + xy = x^3 + Ax^2 + B$ over $GF(2^m)$, for two given constants $A$ and $B$. Suppose that I give you the coordinate $x$, and I challenge you to find the coordinate $y$.

If $x = 0$, then the equation becomes $y^2 = B$, so a solution $(0,y)$ must be such that $y$ is a square root of $B$. In a binary field, $B$ has exactly one square root, so this is one solution.

If $x \neq 0$, we can divide both sides of the curve equation with $x^2$. We get this:
$$ \left(\frac{y}{x}\right)^2 + \frac{y}{x} = x + A + \frac{B}{x^2} $$
We recognize here the equation $z^2+z = \beta$, by setting $z = y/x$ and $\beta = x + A + B/x^2$. We know how to solve that: with the half-trace, as described above.

So solve it to get $z$, then multiply by $x$ to get $y$. And you're done.

Note that when $z^2 + z = \beta$ has solutions, it has two solutions, that differ by the last bit. Hence, $y$ will be equal to either $zx$ or $(z+1)x$. The choice of the solution must be conveyed in the encoding.

Extra Subtleties

The method you describe is more or less point decompression. However, there is an extra twist. True point decompression requires $m+1$ bits: $m$ bits for $x$, and the extra bit for the choice of the solution for $y$. However, once can save one bit, in the following way.

A normal (non-supersingular) curve over $GF(2^m)$ has an even order. For cryptographic purposes, we want to work in a subgroup of prime order, hence odd. Standard curves will thus have order $2q$ (or $4q$) for some prime integer $q$. We are thus interested only in half the points at most.

Moreover, the "interesting half" can be distinguished with the trace! It can be shown that for the "interesting" points (those in the subgroup of prime order), the trace of the $x$ coordinate must equal the trace of $A$. Thus, we can use the trace of $x$ and infer its last bit.

So back to your description:

If the provided $x$ coordinate is $0$, then the solution is $(0,\sqrt{B})$. Done.
Separate the rightmost bit of the provided input, and call it $k$; this is the bit that will be used to choose the solution for $y$.
Decode the input as coordinate $x$. Note that the rightmost (least significant) bit is missing, since that slot was used for bit $k$, so just suppose that the missing bit is $0$. However, if the result has the wrong trace (i.e. $\text{Tr}(x) \neq \text{Tr}(A)$, then flip that bit (which has the effect of flipping the trace, thus restoring the equality). Note: in your description, you compare $\text{Tr}(x)$ with $A$ itself; this is because you work with one of the standard curves that have $A$ equal to $0$ or $1$, not any other element of $GF(2^m)$.
Compute $w = x^3+Ax^2+B$. This is the right-hand side of the curve equation. No worry here.
Compute $v = wx^-2$ and solve the equation $z^2+z = v$; this is where the half-trace is used. Take care that there may be no solution, in case the provided $x$ is not actually the $x$ coordinate of a valid curve point; this may happen because the encoded point comes from the outside, where there are evil people who may send you invalid data.
The bit $k$ that you used before tells you which solution $z$ you must keep. The way you describe it appears to be somewhat mangled. One simple way is to say that $k$ and the low bit of $z$ must match, but there can be other conventions, including stating that $\text{Tr}(z)$ must match $k$. In standard point decompression, there is no trace here, bit $k$ is supposed to be equal to the low-order bit of $z$. However, standard (as in "ANSI X9.62") point compression does not use the extra trick of not encoding the low order bit of $x$, so I must assume that you are doing something non-standard here.
This step is trivial.

Now for computing the trace and the half-trace. The expressions above work, but are complicated. Since the trace is linear, and outputs only $0$ or $1$, then it follows that $\text{Tr}(z)$ is just the XOR of a few bits of $z$. Which bits to use depends on the field representation, but usually there won't be many. For the half-trace, the result has length $m$ bits, so it can still be done with linear algebra: for a given input $z$, XOR together some precomputed values $h_i$ for all $i$ such that $z_i = 1$. These $h_i$, again, depend on the field definition; precomputing them is a nice exercise. Take care that table lookups, if not done carefully, are prone to make side-channel leaks.

All of this assumes that you can compute things in $GF(2^m)$. This requires functions to add, multiply, and divide values in that field. Implementing these correctly is not easy. Some guidance can be obtained from the Guide to Elliptic Curve Cryptography, especially section 2.3, which talks about binary fields (and it so happens that the chapter 2 is a free download as a PDF!). Making such code constant-time is possible, but harder (especially for division). For a basic Diffie-Hellman, decoding of points occurs on data which has travelled over the wire, hence non-secret, which helps here. Implementing cryptographic algorithm is a path fraught with perils, in particular side-channel attacks; elliptic curves over binary fields are certainly not the easiest thing to do among cryptographic implementations.


Does changing the random number selected for each message increase security in Schnorr's scheme?

A small message space is no problem and I do not really know what you mean by "signature length is very small".

However, it is not only a good idea to choose independent and fresh randomness for every signature, it is (as Alex mentioned in his comment) necessary. Otherwise anyone who gets two signatures of you computed with same randomness for different messages can extract your private signing key with overwhelming probability.

I'm using the notation from the Wikipedia article of Schnorr signatures.

Assume you have two signatures $(s,e)$ and $(s',e')$ for two messages $M\neq M'$. Using the same randomness means that $r=r'$ (since $k=k'$) and since $M\neq M'$ in practice we will have that $s\neq s'$ ($H$ is a secure cryptographic hash function and would need to collide).

Now, we know that $s\equiv k-xe \pmod q$ and $s'\equiv k-xe' \pmod q$.

Consequently, since $k$ (the randomness) is identical for both signatures, we have that

$s+xe \equiv s'+xe' \pmod q$ and thus $s-s' \equiv x(e'-e) \pmod q$ and thus

$x\equiv (s-s')(e'-e)^{-1} \pmod q$.

Ignoring the very unlikely cases where $s-s'$ and $e'-e$ are $0$, and since $(e'-e)^{-1}$ thus always exists, the attacker can extract $x$, which is the private key.

So, when using Schnorr's signature, it is essential, that the value $k$ is chosen independently and randomly for every signature such that these "randomness collisions" do not happen.

All ElGamal type signatures (such as DSA/ECDSA) suffer from the same problem when re-using the randomness $k$ and actually this is what doomed Sony's private key back in 2010/2011 (i.e., they re-used $k$ over different signatures).