What exactly is in YouTube's monkey message?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

What exactly is in YouTube's monkey message?

Postby TheChewanater » Sun Nov 07, 2010 6:15 am UTC

If you've browsed YouTube enough, you've probably encountered an internal server error message once, accompanied by some joke about a team of monkeys and a long string of letters and numbers to show them. My question is, does anyone have any idea what this string means? Could it actally be a message, or is it more likely randomly-generated jibberish? Judging by several posts on Q&A sites, the string is not always the same.

By the way, the ratio of 1s to 0s in its binary representation is about 87:100, which seems too far for a random sequence converted into chars. I could be wrong, though.

Code: Select all

A0gg0svUlocd-cTmY5fHVUYhtPlPA9__5CEM-eGKIOxSAXQqfIs7GtvC2MRm
yCm7ylCUQgwU35xu3aw0MBW3mqGBZAeqUDDuhDIrx9HQVhCxHgiEO9fWTWea
dDEoaOh7m0ZDGsHou5TZ0YxGsahfeks16yQWK8ftiVt4b7Std4aiBN40RWiM
2WjWbgzBCyqavT_mkecoXl0G6TFYU_quF8wWXKlVhuDWPEiUh9nLfLBDDCfp
vss6UjpZmEjKFz8FxX11WySqWuE5YyTrCHv73IYUFl8iQAPiJ2wHGEi6PNji
XjauMdRcOgmolADksHyG_cB-mB2YT6gvsbMZa_G6z1r7cRVI179wxUqY9JKr
c1EHoJlM2IAEYjjg9tHW65EtSyNGWdj4kXx-OitJpA6iMLH5VlW_dH-jSTns
whO2uHeQPU3_Az0bmVI4nrV3bezwU2sEjVX8A6TLhLFOGn4AuDY1JKkp8WY7
Z0jQBpP37zX6kK1IArzWqc9eaZRZaGNCUqD6kJhPfADcvHYTwQbGziHmrGgr
h0-LuOauAGRCF0oMAGki-a_cYqOoNBDDL3iH-VmPTZS1A7yIbsKMwJ8OOAiU
E0bT_HsCnWhl7mJXZPy6RIbpa02vaC1IdLhA6r88cW5KUKHlGYS9_aM8IKLJ
Fi8IelKUG03sp7_DD54cePxxCO5TyLcZ9CJFJeraK9_fxitIQ4EryFp4Z9lU
lqHhltVA6KT9hBkRCUUJSpEdnPMFlrBN5dyx_SIjfCIOLS0aKjzzZacV7nma
7mDG-fo-yWsIBGaQgRTe2x4AGEHx1Ijc2OIzN6lxCx0eiUvJrDAKXTX9le_U
ifybf8EBgDjnJvLzGwxBEm2Q_0AcbsTWvd6YQA2YDN4m6QMgPIDvPrWNr59i
ryhhq4pth7wtLulVF75i0CmK1pisvvOPqro9Px8Mj-Fzyi1qTtfLUY-WWsmR
WaxkXqpH6_2xWKjxaaPLRsZfmHhBOs5K_YaNCHh6y3SLBv2_D6JlVNak8gtv
eP_JVrIbCLuElDCjxqEEoUJEEf5Ax8vaccaN5NBRKs23AK7OnHDMHbm6q2NK
8c1LkPntsQ7LFhLE_Dzu-vbMCZ3fBBKK4DIb4THc1x9r348wqCUCOFPt6W1d
Ogq8gv4e0I8ecxt_OKneFGxN-iTGB8knzkObp6y-mn_7Co01xSBZqY_MaWCB
PAT6Qe8YAMGeysm3Cvnjp5OzvAPlY5sAOThJY9E_dPlEX_6VdfpAnejcv_xw
BPB8iXxbpUJuVWiU4zNqs0qA8uvzL2C3xmFLPoA_hu7K6Qzq1vR9sBCPOkZC
ALGTl9pSxkUrxVtPTxDPbQsYFCQ1Rq1BK6er1d_7vJfNfGAwbKIcwWrU0_gF
q9ynQfGUAgr8dhmw_hN_i8fKUqHfHBkKWLFtVWV3gF7xvECgy7LzoReXBMj-
qnPH52atpamtS7LwPHIysANb1Kv6HUYl1018nIi5lix5HsApL-XlqS4dt6eW
HNaHZIDRmJN64PGezEaPPIoRcKJRMSqj4X0u
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: What exactly is in YouTube's monkey message?

Postby Thesh » Sun Nov 07, 2010 7:00 am UTC

If I had to guess, it's an encrypted message containing the actual error message and possibly the line number and/or stack trace, as well as request headers. Usually you don't want to give that data out freely to end users (well, request headers don't count), as they can possibly used by an attacker.


On a side note I've seen websites in .NET that, when called by a querystring with an unexpected value, printed out the actual SQL statement it tried to run.
Summum ius, summa iniuria.

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: What exactly is in YouTube's monkey message?

Postby TheChewanater » Sun Nov 07, 2010 7:19 am UTC

I thought so, but it seems unlikely that most users would actually send the encrypted data to YouTube.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: What exactly is in YouTube's monkey message?

Postby phlip » Sun Nov 07, 2010 7:47 am UTC

TheChewanater wrote:By the way, the ratio of 1s to 0s in its binary representation is about 87:100, which seems too far for a random sequence converted into chars.

They seem to be about the same to me:

Code: Select all

>>> import base64
>>> s = base64.b64decode(open("/tmp/tmp.txt").read(), altchars="-_")
>>> zero=one=0
>>> for c in s:
...     for i in xrange(8):
...             if ord(c)&(1<<i):
...                     one += 1
...             else:
...                     zero += 1
...
>>> zero,one
(4685, 4531)

Slightly more zeros than ones, but not significantly so...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: What exactly is in YouTube's monkey message?

Postby TheChewanater » Sun Nov 07, 2010 3:06 pm UTC

Does that ignore underscores and dashes?

I'll try to figure out how I arrived at those results.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: What exactly is in YouTube's monkey message?

Postby phlip » Sun Nov 07, 2010 10:06 pm UTC

No, it reads - and _ as 62 and 63 (respectively) in the base-64 decoding. They're a reasonably-common alternative to the usual + and /, especially for uses where the result would be used in a URL (since both + and / would have to be percent-escaped).

[edit] The 87:100 value you came up with for 1's to 0's is of the base-64-encoded text... which is obviously going to be skewed, towards characters that are in the base-64 character set. Mine is for after decoding the base-64, and is around 96:100.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: What exactly is in YouTube's monkey message?

Postby TheChewanater » Sun Nov 07, 2010 10:13 pm UTC

phlip wrote:[edit] The 87:100 value you came up with for 1's to 0's is of the base-64-encoded text... which is obviously going to be skewed, towards characters that are in the base-64 character set. Mine is for after decoding the base-64, and is around 96:100.


Oh, duh. So it's just random?
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

voidPtr
Posts: 140
Joined: Sun Apr 26, 2009 6:53 pm UTC

Re: What exactly is in YouTube's monkey message?

Postby voidPtr » Sun Nov 07, 2010 10:26 pm UTC

I'm guessing the inside joke has something to do with this?

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: What exactly is in YouTube's monkey message?

Postby phlip » Sun Nov 07, 2010 10:29 pm UTC

TheChewanater wrote:Oh, duh. So it's just random?

Well, it resembles randomness at first glance. But then, so does any good encryption method.

I'm pretty sure it's just a joke, though. If there was important information in there for debugging, the site could send it directly to the people who need to see it... maybe give the user a much shorter key to copy, so that if they do send a bug report in, it can be matched up with the crash log.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby Meteorswarm » Mon Nov 08, 2010 1:15 am UTC

TheChewanater wrote:I thought so, but it seems unlikely that most users would actually send the encrypted data to YouTube.


Not necessarily. I know for a fact that encrypted stack traces on other Google products are put up in the same way so that developers can test things without having to ship a different version from the testing version. I would bet it's the same way - there for the QA folks to use, and harmless to everybody else.
The same as the old Meteorswarm, now with fewer posts!

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: What exactly is in YouTube's monkey message?

Postby Patashu » Mon Nov 08, 2010 2:33 am UTC

What might they be encrypted with? AES?

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: What exactly is in YouTube's monkey message?

Postby Thesh » Mon Nov 08, 2010 2:46 am UTC

Patashu wrote:What might they be encrypted with? AES?


If it is indeed encrypted, then it is impossible to tell exactly unless you crack it. However, AES does seem to be the most popular modern cipher. According to phlip's post, the cipher text is 9216 bits long which is a multiple of 128, so a block cipher with a 128 bit block size is possible. Of course, it doesn't rule out older 64 bit block ciphers like des, triple des, or blowfish. I don't know for sure, but I bet most block ciphers have a block size which is a multiple of 32 bits.

Twofish and Serpent are other modern alternatives to AES which also have 128 bit block sizes. Also, any of those ciphers could be operating with a mode of operation which turns it into a stream cipher (e.g. CFB, OFB), or they could be using an actual stream cipher and it just happens to be a multiple of 128 bits long (1/16 chance).

EDIT:

Now that I look at it, it's exactly 1536 base 64 characters (exactly 1.5 KiB or 1152 bytes when encoded to binary), which seems like it could be pretty deliberate. The message could be padded to a specific length just so it doesn't give anything away, such as a 1024 bit message, prepended with a 128 bit initialization vector.
Summum ius, summa iniuria.

CryptWizard
Posts: 3
Joined: Mon Jan 19, 2009 3:34 am UTC

Re: What exactly is in YouTube's monkey message?

Postby CryptWizard » Thu Nov 11, 2010 12:28 pm UTC

If you decrypt it, it'll probably be some information letting you know you can get a job at Google by telling them that you've managed to decrypt the message.

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby Meteorswarm » Thu Nov 11, 2010 10:56 pm UTC

CryptWizard wrote:If you decrypt it, it'll probably be some information letting you know you can get a job at Google by telling them that you've managed to decrypt the message.


Any meaningful encryption scheme relies not on the opponent being incapable of thinking of how to break it, it relies on them not being able to try enough keys in whatever timeframe you care about.
The same as the old Meteorswarm, now with fewer posts!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: What exactly is in YouTube's monkey message?

Postby Yakk » Fri Nov 12, 2010 3:00 pm UTC

Meteorswarm wrote:
CryptWizard wrote:If you decrypt it, it'll probably be some information letting you know you can get a job at Google by telling them that you've managed to decrypt the message.
Any meaningful encryption scheme relies not on the opponent being incapable of thinking of how to break it, it relies on them not being able to try enough keys in whatever timeframe you care about.
There is exactly one provably unbreakable form of encryption, and it isn't physically realizable (you need a perfect random number generator to do perfect encryption).

There are many forms of encryption that there are no known ways to break them, and the functions are believed to be trap-doors. But nobody has managed to prove that a given function used in any encryption algorithm is actually a trap-door function (easy one way, hard the other). Doing so is roughly equivalent (roughly!) to proving P != NP.

So sending out encrypted text that is believed to be uncrackable, and offering a job to the first person who cracks it, is much like saying "if you can prove P = NP, we'll pay you a salary for a year", which is ... a safe bet.

(Most encryption algorithms are not NP-hard as far as I know, so you can crack them without proving P=NP. I'm not aware of an NP-hard encryption algorithm?)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: What exactly is in YouTube's monkey message?

Postby Robert'); DROP TABLE *; » Fri Nov 12, 2010 9:08 pm UTC

It was my understanding that quantum uncertainty was a perfect RNG.
...And that is how we know the Earth to be banana-shaped.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: What exactly is in YouTube's monkey message?

Postby Yakk » Fri Nov 12, 2010 9:16 pm UTC

We don't have access to quantum uncertainty. We have access to devices that detect the behavior of things that seem to behave with quantum uncertainty. These devices generate both false positives and false negatives. Effort is done to strip out the problems with false positive/negatives and other biases in the sensory devices, but this effort is not perfect.

There is, naturally, a limit to how many bits you can get past the one time pad, determined by the actual entropy of the one-time pad. So the better you make your pad, the fewer bits can leak. With low-entropy data hidden by the one-time pad, possibly useful information can leak out.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: What exactly is in YouTube's monkey message?

Postby BlackSails » Sat Nov 13, 2010 4:22 pm UTC

Yakk wrote:We don't have access to quantum uncertainty. We have access to devices that detect the behavior of things that seem to behave with quantum uncertainty. These devices generate both false positives and false negatives. Effort is done to strip out the problems with false positive/negatives and other biases in the sensory devices, but this effort is not perfect.


Couldnt you just use the von neumann coin trick on the radiation sensor to make it perfectly fair?

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby letterX » Sat Nov 13, 2010 5:15 pm UTC

BlackSails wrote:
Yakk wrote:We don't have access to quantum uncertainty. We have access to devices that detect the behavior of things that seem to behave with quantum uncertainty. These devices generate both false positives and false negatives. Effort is done to strip out the problems with false positive/negatives and other biases in the sensory devices, but this effort is not perfect.


Couldnt you just use the von neumann coin trick on the radiation sensor to make it perfectly fair?


There's a difference between perfectly fair and perfectly random. Obviously, a process that spits out 0, 1, 0, 1, 0, 1, ... is perfectly fair, but completely nonrandom.

Anyways, I think Yakk is worried about some unspecified factor in between the quantum randomness and its observation somehow affecting the random stream generated. I guess that's not completely unreasonable. There's no good reason to believe my geiger counter is measuring exactly the decay events of some truly randomly decaying sample. It could be introducing some small deterministic effects into the data generated.

I'm not sure if that's a good reason to say 'we don't have access to quantum uncertainty', though. I don't really know what the loss of entropy in sampling true random data is going to be. If it's the loss of one bit per (say) terabyte? Then, practically we're probably fine. I doubt it's that low, though.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: What exactly is in YouTube's monkey message?

Postby Yakk » Sat Nov 13, 2010 5:55 pm UTC

*nod*, you can do things to attempt to remove the non-entropic bits. The coin trick isn't bad, but it is not perfect.

Imagine if the device has a slightly higher chance of generating a false positive after a negative than not -- or a slightly higher chance of generating a false positive after each positive.

With the xor coin trick, one would show up as an extra chance of 1s, and the other as an extra chance of 0s.

Even larger scale, imagine if the power to the device isn't perfectly uniform, and there is a 60 Hz flux, and we are generating bits at a rate of 1000 Hz, and that 60 Hz flux shows up in strange ways.

Or the unit that smooths out the power heats up and its characteristics change.

All of this is imperfection -- and we do work to remove imperfection. But we don't have pure access to quantum number generation, we have mediated access, and those devices are far from perfect. The theoretical models of perfect single photon detectors are just theoretical -- we don't have such devices. So the entropic density of the quantum generated one time pads is not guaranteed to be maximal.

Given a sufficiently low-entropy message being hidden, the entire message could leak.

Information theoretically, the amount of information you can get through a one-time pad is limited by the difference between the entropy of the one time pad and the maximal entropy of that many bits. So the better you are at boosting the entropy of your one time pad, and the more information you stuff per bit in the signal, the better off you are.

All of this is a discussion of perfection. Practically? I believe our current quantum number generators are good enough. Perfect? Nope. Thus "there is no perfect encryption".
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby letterX » Sat Nov 13, 2010 7:15 pm UTC

Yakk wrote:All of this is a discussion of perfection. Practically? I believe our current quantum number generators are good enough. Perfect? Nope. Thus "there is no perfect encryption".


I basically agree with you, and the main point of 'no encryption scheme is absolutely perfect' is definitely worth repeating. However, we already knew that. This is far from pithy: it's always useful to remember that side-channels very quickly become more feasible than direct attacks against cryptosystems.

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby Meteorswarm » Sun Nov 14, 2010 7:36 pm UTC

Yakk wrote:There is exactly one provably unbreakable form of encryption, and it isn't physically realizable (you need a perfect random number generator to do perfect encryption).

There are many forms of encryption that there are no known ways to break them, and the functions are believed to be trap-doors. But nobody has managed to prove that a given function used in any encryption algorithm is actually a trap-door function (easy one way, hard the other). Doing so is roughly equivalent (roughly!) to proving P != NP.

So sending out encrypted text that is believed to be uncrackable, and offering a job to the first person who cracks it, is much like saying "if you can prove P = NP, we'll pay you a salary for a year", which is ... a safe bet.

(Most encryption algorithms are not NP-hard as far as I know, so you can crack them without proving P=NP. I'm not aware of an NP-hard encryption algorithm?)


I wasn't thinking about side channel attacks, but my point was that if they're using some sort of robust keyed encryption, and why wouldn't they be, breaking it amounts to brute-force finding the key. It's not like they just ran it through a bunch of base-64-hex converters to obfuscate the message, so, side-channel attacks aside, getting the key doesn't require brilliance - it requires patience and resources.
The same as the old Meteorswarm, now with fewer posts!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: What exactly is in YouTube's monkey message?

Postby Yakk » Mon Nov 15, 2010 2:25 pm UTC

It amounts to brute-force finding the key, or figuring out what their encryption algorithm is, and finding a flaw in it.

The word "provably" and "perfect" are rather important to my post being non-nonsense.

Most "strong" encryption algorithms in use are effectively impossible to break, because nobody (that admits it publicly) knows how to break them (this is tautological, because once someone admits they can break an encryption algorithm, we no longer call it strong). But nobody knows how to prove that they are hard. In particular, a class (maybe almost all?) encryption algorithms would be easy to break given a sufficiently fast NP -> P conversion algorithm, and nobody has proven that such an algorithm does not exist.

Encryption algorithms tend not to be in NP-hard as far as I know, so in many cases there can be easier attacks on them than finding that fast NP->P conversion algorithm. As an example, RSA can be attacked by fast factoring into primes of large numbers: I believe fast factoring is in BQP (medium certainty -- I think it is in a quantum computation complexity class, but I am less than certain that the class is BQP), which (as far as we know) does not contain NP-hard. (we don't even know if P contains NP-hard, so that "as far as we know" is a really weak claim! (BQP contains P))

(At least this guy claims it is in BQP -- laugh, it uses quantum FFT! FFT, what can't you do? http://www.cs.nott.ac.uk/~nad/publicati ... -talk.html )

What this means is that every encryption algorithm (with the exception of one-time pads) is not provably strong, let alone perfect. All of them rely on "we think this function is hard to reverse, but we cannot prove it". All it takes is someone to invent novel mathematics that allows those functions to be reversed efficiently, and the hidden data pops out. (the amount of extra entropy in most encrypted documents is not all that high, at least if the encryption algorithm is known)

In the case of a one-time pad, it relies on the pad being perfectly random. To do this, the current best methods I know of (are there better?) involve using either entropy from thermodynamics or from quantum random number generation. The thermodynamics method involves things like pointing a camera at a lava lamp and then munging the resulting pixels a bunch. The quantum random number generation involves sticking a sensor at/near a source of data that comes out of quantum mechanics as directly as possible, then munging the data so it is white noise (instead of, say, pink noise).

Of the two, the quantum one is more theoretically robust I suspect -- and it runs into problems that our sensors at that scale are not perfect. Insofar as they are not perfect, and our post-reading munging isn't perfect, the resulting one-time pad does not have maximum entropy. The theoretical perfection of the one-time pad relies on the one-time pad having maximum entropy (so when you xor it with your plaintext, the resulting data still has maximum entropy, and hence there is no information theoretic room for information to lead back to the plaintext -- hence theoretically perfect.) As such, it isn't perfect -- damn near close, I'll admit, but not perfect. :)

The short answer is -- if they used strong encryption (probably not OTP, that is awkward to use), then someone decrypting it either has an "in" or has broken a strong encryption method used (or they failed to successfully use the strong encryption method, which is pretty common)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Meteorswarm
Posts: 979
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: What exactly is in YouTube's monkey message?

Postby Meteorswarm » Tue Nov 16, 2010 1:38 pm UTC

Yakk wrote:It amounts to brute-force finding the key, or figuring out what their encryption algorithm is, and finding a flaw in it.

The word "provably" and "perfect" are rather important to my post being non-nonsense.

Most "strong" encryption algorithms in use are effectively impossible to break, because nobody (that admits it publicly) knows how to break them (this is tautological, because once someone admits they can break an encryption algorithm, we no longer call it strong). But nobody knows how to prove that they are hard. In particular, a class (maybe almost all?) encryption algorithms would be easy to break given a sufficiently fast NP -> P conversion algorithm, and nobody has proven that such an algorithm does not exist.

Encryption algorithms tend not to be in NP-hard as far as I know, so in many cases there can be easier attacks on them than finding that fast NP->P conversion algorithm. As an example, RSA can be attacked by fast factoring into primes of large numbers: I believe fast factoring is in BQP (medium certainty -- I think it is in a quantum computation complexity class, but I am less than certain that the class is BQP), which (as far as we know) does not contain NP-hard. (we don't even know if P contains NP-hard, so that "as far as we know" is a really weak claim! (BQP contains P))

(At least this guy claims it is in BQP -- laugh, it uses quantum FFT! FFT, what can't you do? http://www.cs.nott.ac.uk/~nad/publicati ... -talk.html )

What this means is that every encryption algorithm (with the exception of one-time pads) is not provably strong, let alone perfect. All of them rely on "we think this function is hard to reverse, but we cannot prove it". All it takes is someone to invent novel mathematics that allows those functions to be reversed efficiently, and the hidden data pops out. (the amount of extra entropy in most encrypted documents is not all that high, at least if the encryption algorithm is known)

In the case of a one-time pad, it relies on the pad being perfectly random. To do this, the current best methods I know of (are there better?) involve using either entropy from thermodynamics or from quantum random number generation. The thermodynamics method involves things like pointing a camera at a lava lamp and then munging the resulting pixels a bunch. The quantum random number generation involves sticking a sensor at/near a source of data that comes out of quantum mechanics as directly as possible, then munging the data so it is white noise (instead of, say, pink noise).

Of the two, the quantum one is more theoretically robust I suspect -- and it runs into problems that our sensors at that scale are not perfect. Insofar as they are not perfect, and our post-reading munging isn't perfect, the resulting one-time pad does not have maximum entropy. The theoretical perfection of the one-time pad relies on the one-time pad having maximum entropy (so when you xor it with your plaintext, the resulting data still has maximum entropy, and hence there is no information theoretic room for information to lead back to the plaintext -- hence theoretically perfect.) As such, it isn't perfect -- damn near close, I'll admit, but not perfect. :)

The short answer is -- if they used strong encryption (probably not OTP, that is awkward to use), then someone decrypting it either has an "in" or has broken a strong encryption method used (or they failed to successfully use the strong encryption method, which is pretty common)


Ok, I see your point; coming up with fast factoring would probably make you eligible for a job pretty instantly, although you'd have to avoid being murdered by distraught cryptologists.
The same as the old Meteorswarm, now with fewer posts!

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: What exactly is in YouTube's monkey message?

Postby quintopia » Wed Nov 17, 2010 11:34 am UTC

Meteorswarm wrote:Ok, I see your point; coming up with fast factoring would probably make you eligible for a job pretty instantly, although you'd have to avoid being murdered by distraught cryptologists.

Peter Shor is still alive. If he dies as soon as a large stable quantum circuit is built, we'll know to suspect murder.

In actual fact, if that happened, we could switch to, say, probabilistic crypto schemes based on NP-complete problems (thus making the problems NPP-complete iirc, and therefore also unknown as to whether they are polynomially solvable with high enough probability). And if these are broken, we'll surely have something else worked out by then. I think cryptographers rather like having their schemes being broken. If there were to be a proof guaranteeing RSA was unbreakable (say, a proof that NP!=P and a proof that integer factorization is NP-complete), then cryptographers would be out of a job.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: What exactly is in YouTube's monkey message?

Postby Yakk » Wed Nov 17, 2010 5:24 pm UTC

RSA is only one particular kind of Public Key Cryptography. I think (low certainty) that there are others based on discrete logarithms.

NP-complete cryptography is hard because it is difficult to figure out what NP-hard instances are actually fundamentally hard. We can show that there is at least one instance of an NP-hard problem that is as hard as another problem via polynomial time mapping: but because we don't know why NP-hard problems are hard, we don't have a difficulty-o-meter for them.

Now, last I checked, this was an area of current research (what kinds of NP problem instances are hard): so researchers probably know more about this than my current rather limited knowledge. However, in at least some cases an NP-hard problem has the property that "most" instances are easy, and cryptography is about having every instance being hard, this is problematic.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 7 guests