16 ms·

Google AI invents its own cryptographic algorithm

519 points by wallflower 10y ago

jacquesm 10y ago
> While it seems improbable that neural networks would become great at cryptanalysis, they may be quite effective in making sense of metadata and in traffic analysis. How does that square with the fact that the best cryptanalists appear to have nothing but their own neural networks to work with? This reminds me of the genetic algorithm that came up with a tone discriminator that at first glance looked like it could not work (parts connected wrong or not at all, and yet, crucial to functioning). https://www.damninteresting.com/on-the-origin-of-circuits/ https://www.damninteresting.com/on-the-origin-of-circuits/
- dgacmu 10y ago
  Because humans have invented tools - math, notably - that they can use to be more formal and precise when they deal with problems of this sort. To date, neural networks can't -- they're doing very well at the kind of "intuitive" pattern matching that our brains do, but less well on an algorithmic front. It's one of the really interesting frontiers of AI right now. The folks at DeepMind recently showed, for example, that a variant of their "Neural Turing Machine" architecture could learn to do things involving more like what we think of as discrete algorithms (https://deepmind.com/blog/differentiable-neural-computers/ https://deepmind.com/blog/differentiable-neural-computers/ ), but all of this is very early work.
- adrianN 10y ago
  The words "neural network" describe pretty different things, depending on whether a computer scientist or a neuroscientist use them.
widforss 10y ago
This is most probably a rather lousy hack put together by Alice and Bob, but it maps out a very interesting future were we one day maybe can stop worrying about how our algorithms work and make that the job of the computer. It also is totally terrifying to live in a world were computers can hide their messages from their own creators.
- n4ss 10y ago
  It doesn't. As an AI developer you have access to the AI code and memory.. How could you not replay the encryption process used by the AI since you know the state of what it "knows" constantly? Both have a encryption and decryption process that you can reproduce.
  - sdegutis 10y ago
    You can replay it, but you might not necessarily be able to understand it fully. Kind of like how beginner programmers can't necessarily understand advanced algorithms just by reading the code or walking through it in a debugger. They may need someone to help guide them through it and teach them how it works, and they will need the intelligence to be able to comprehend it. If the algorithm is designed by an AI, we may not have either.
    - kybernetikos 10y ago
      We may have AIs that can help guide you through code written by other AIs.
  - mason55 10y ago
    You might be able to follow the steps that the computer takes but you won't necessarily know why. Why is that the magic constant is chose, what is the purpose of those branches, etc. And likely, if it's necessary, the AI can continue to evolve the algorithms faster than you can figure out what it's doing.
    - Cyph0n 10y ago
      Why? That simply depends on how the code was written. The magic constant may be chosen randomly, or based on previous guesses, or generated by another program, etc.
      - pi-err 10y ago
        Could't the source get encrypted as well? Also the cognitive gap between a AI and a human brain has to grow and transform unpredictably in the next decades. We may be puzzled to understand how it "thinks" the same way we still don't get exactly how DNA operates.
trungaczne 10y ago
This is the link to the research paper ("Learning to protect communications with adversarial neural cryptography"): https://arxiv.org/abs/1610.06918 https://arxiv.org/abs/1610.06918
systemfreund 10y ago
It's not clear from the article whether they train the networks with the same shared-key in every iteration, or if they randomize it. Any info on that?
- anotheryou 10y ago
  I thought no key/public key, but it really doesn't say
- dgacmu 10y ago
  It's a random key paired with a random plaintext for each input. In the experiments, the key is the same length as the plaintext. Happy to answer more questions about it. (I'm one of the authors.)
  - rcorin 10y ago
    So basically the NN is learning a one time pad?
    - dgacmu 10y ago
      Kind of. Except that there's no restriction that there has to be a 1:1 correspondence between the key and plaintext bits (or characters) that get mixed, as there would be in a conventional OTP. And, indeed, the DNN doesn't learn that - it mixes multiple key and plaintext bits together. Probably in a way that's worse than a true OTP -- the adversary is more successful than it should be were the encryption scheme a "correct" OTP with XOR.
      - rcorin 10y ago
        Cool! Also, have you tried giving some bits of the key to the adversary?
        dgacmu 10y ago
        I haven't. Interesting - that'd be a nice way to try to probe how strong the encryption is (i.e., "bits recovered vs. key bits supplied to adversary"). I'll have to think about that more - thanks for the idea!
deleted 10y ago
[deleted]
JackFr 10y ago
This seems pretty click-baity to me. Especially "no one knows how it works." Alice generates ciphertext based on plain text and key. Bob generates plaintext based on ciphertext and key. Eve generates plaintext based on only ciphertext. Train the three networks across a variety of plaintetxts, No doubt it's cool, but I would be very surprised if it offered any insight into, or represented an advance for strong cryptography.
- bkin 10y ago
  Jinxed! :-)
- cheez 10y ago
  This is less about cryptography and very much about neural networks making stuff.
- pohl 10y ago
  I might be reading your comment incorrectly, but it sounds like you're interpreting that phrase to mean that no one knows how training the neural network works. I think, instead, it's in reference to the resulting function not having been analyzed. From the article: The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob...
  - rjbwork 10y ago
    >I think, instead, it's in reference to the resulting function not having been analyzed. I think it may be that it is "unanalyzable" if you will. Thousands of matrices multiplied together seems as if it would be hard to come to an actual understanding of...
    - patrickmn 10y ago
      This right here is why machine learning--although very exciting--is an incredibly frustrating endeavor compared to software engineering. It's statistics at its "worst." At the risk of glorifying AI, a good analogy might be that understanding a complex neural network is similar in nature to trying to understand how neurons in a human brain are wired, and why they cause some things to happen (or not happen) with some probability. It's more like the practice of medicine than it is engineering.
bkin 10y ago
TFA's title is a little clickbaity by adding "noone knows how it works" which apparently means that: The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR. In particular, the output values are often floating-point values other than 0 and 1," they said. Just saying...
- Strilanc 10y ago
  Outputting floats instead of discrete values actually sounds like a very exploitable hole to me. It reminds me of the classic "check if your model corresponds to reality" example where a one-time pad is broken: the standard said "<0.5V volts is OFF" but your machine was outputting 0.1V for OFFs that came from computing 0 xor 0 and 0.2V for OFFs that came from computing 1 xor 1.
pmyjavec 10y ago
Poor taste with the Terminator graphic. A new level of lame fear mongering by Ars Technica?
- dharma1 10y ago
  I was hoping psychedelic dog heads would become the default stock photo for AI news, rather than red eyed robots
chiefalchemist 10y ago
By the time we finally realize we're not as smart as we think we are, it's going to be too late.
chiefalchemist 10y ago
By the time we finally realize we're not as smart as we think we are, it's going to be too late.
Touche 10y ago
I'm not sure what conclusions we're supposed to draw from this. Just because they were able to hide the messages from a 3rd AI doesn't mean the encryption was good. Shouldn't a human examine it and see if they can codebreak it? Isn't the goal better encryption?
- dgacmu 10y ago
  I don't want to tell people what to take away from it, but my own view is that the contribution of the paper is the framing of the problem and a preliminary demonstration that you can achieve the goal of defeating a NN via an adversarial training formulation. In a lot of ways, I view our work as creating a challenge problem for the AI & crypto communities. It shows an intriguing possibility that is far from being practical, and itself represents a stepping stone in work on, e.g., training DNNs to learn to communicate. Can this be extended to generate cryptanalysis-resistant schemes? Can we create a formulation that can learn to use discrete operators such as modular arithmetic? (The latter reflects one of my personal complaints about the state of DNNs -- it's very hard to have discrete "blocks" of functionality if that functionality isn't differentiable). Can we identify mechanisms that can train networks such as these more robustly? (It fails to train roughly half of the time; this is a fairly common problem in adversarial training of DNNs today.)
  - jsprogrammer 10y ago
    NNs/ANNs/DNNs/xNNs have already[0] been framed as easily fooled. [0] https://arxiv.org/pdf/1412.1897.pdf https://arxiv.org/pdf/1412.1897.pdf
ajamesm 10y ago
Hill climber climbs hill, news at 11?
- fooker 10y ago
  Interesting choice of words!
jdimov10 10y ago
Duplicate of https://news.ycombinator.com/item?id=12800228 https://news.ycombinator.com/item?id=12800228
traviswingo 10y ago
I get the sense that many commenters misinterpreted the point of this study. This isn't about show-boating some newfound, great cryptography method, this is about teaching computers to re-write their own code. If you can write software that improved itself better over time, our species as a whole would advance at incredible speeds. Think about all the possibilities that could evolve from self-maintained programs. Obviously the thought is a bit scary, but it's also incredibly exciting!
- FT_intern 10y ago
  and here I was as a programmer bragging about automating people's jobs...
- ape4 10y ago
  Its not their own code. Its code they own.
- gcr 10y ago
  Please don't editorialize. Finding the best parameters that optimize an objective function can hardly be called "re-writing its own code." Granted, the article is just as guilty. (Edit: The article also doesn't mention self-modifying code so I'm not sure where you're getting that idea from.) For the curious, here is the preprint: https://arxiv.org/pdf/1610.06918v1.pdf https://arxiv.org/pdf/1610.06918v1.pdf The technique is an off-the-shelf GAN that attempts to learn a transformation (not arbitrary code!) from input to encrypted output. The learned model is not Turing complete, and most importantly, is _not_ self-modifying. The optimization procedure is what modifies the network, not the network itself. GANs have been used before to create realistic pictures. They're not new here -- the application is. It's a cool application, sure, but doesn't involve self-modifying code.
  - Houshalter 10y ago
    I don't think it's entirely inaccurate to call neural networks "rewriting their own code". For a long time people experimented with algorithms that could actually rewrite human programming languages, like genetic programming. And it's mostly a failure, because most mutations to most programs just break them. Neural networks fix this problem by being sort of 'continuous programming language' where any small change to the net results in a small change to the output. And because of that we have algorithms that can find good changes to make much easier than with code. They are theoretically turing complete under some circumstances. But even when they aren't completely recurrent as in this case, they can still learn very sophisticated functions. Theoretically a neural net can learn anything a fixed number of logic gates can learn, which is still pretty powerful. I don't think parent comment meant by computers that can "re-write their own code" was that the programs are self modifying. But the computer itself is self modifying, as one program can change another on that computer, so the computer has modified itself.
asveikau 10y ago
> this is about teaching computers to re-write their own code. Maybe I've seen too many movies, but I hope we can make sure they don't rewrite the "protect the humans" part.
- tener 10y ago
  It would be very hard to ensure that.
  - asveikau 10y ago
    Especially when they decide that the most logical way to protect them is to destroy them.
    - tener 10y ago
      I have yet to write down a o longer post on this, but honestly I think AI have little chance to operate on purely logical terms. This thinking about paradoxes comes from the time when people approached AI with Prolog etc. They didn't get really far.
- treehau5 10y ago
  but don't we then just unleash the huge EMP bomb?
  - TeMPOraL 10y ago
    Not if any stage of the unleashing process is connected to the Internet.
  - nkozyra 10y ago
    Sounds good. Sadly, six months ago the bot brain predicted the day we were planning with .98 confidence.
    - idlewords 10y ago
      But then it got sucked in to TVTropes, and the world is saved.
excalliburbd 10y ago
Am I the only one wondering about this and Ethereum...
- drdeca 10y ago
  Do you mind elaborating? If you are talking about a smart-contract being able to do stuff with encrypted data without other people being able to access the data, I don't think this would help with that, because whatever system the contract would use would be available to whoever is trying to get the data from the contract. Though, things may be enough to make it hard for other contracts to get stuff from a particular contract? I'm somewhat skeptical of that, but maybe. Also, in any case, the "attacker" contract could just make an incentive for people to give it the information, which I think would work. (and that might be necessary for it to get the info from the defending contract anyway? I don't remember. I don't think it is, but I'm not sure.) However, I'm not sure that is what you meant, and also I'm not sure of what I'm saying. edit: well, there are other systems that have been designed to let contracts keep information secret but I think those are still too expensive to be used, and relied on a secret sharing scheme iirc, so would require that not all the info be on chain.
madenine 10y ago
Really interesting that for the first ~6500 steps Eve was better at decrpyting the messages than Bob, which had access to the key. Would be cool to see a setup like this in which Eve is a cohort of decryption tools, otherwise your Alice network will just overfit against its mechanics. Ie, if Eve uses lockpicks to open a door, an Alice solution would eventually replace the key-lock with a number pad - not necessarily any more secure, but will foil Eve every time.
- timvdalen 10y ago
  >Really interesting that for the first ~6500 steps Eve was better at decrpyting the messages than Bob, which had access to the key. This is probably because Alice wasn't good at encrypting yet.
  - madenine 10y ago
    On a second look, seems like a combination of Alice not being good at encrypting (in a sense that it had to encrypt in a way that makes decrpytion possible), and Bob needed to get up to speed on decrypting (even with the key). As soon as that relationship clicks, Bob get better very quickly, while Eve improves at a slower rate for a while, before Alice adjusts (causing bob to get worse for a bit, until it catches up) Would be interesting to see a set up where Alice / Bob get trained first, then Eve is activated and see how they adjust.
sly010 10y ago
"The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR." I think this says it all.
wideem 10y ago
Next: Google AI encrypts google's servers and demand Ransom
wideem 10y ago
Next: Google AI encrypts google's servers and demand Ransom
martin-adams 10y ago
At an open day for an animation course they showed an AI derived walk cycle of a character. The results were amusing. The condition was that if it feel over that would be no good. The end walk cycle was a character doing forward flips in the air and landing on its feet. Very unexpected results.
strictnein 10y ago
Interestingly, Eve maintained a better than random chance at guessing the message. Consistently stayed a little better than 50%.
1_2__3 10y ago
Given I saw this as top on /r/futurology I figured it was clickbait BS. But since it was posted to HN I thought I'd give it a read. It's clickbait BS.
- benmcnelly 10y ago
  Its interesting, but needs someone to re-submit with a proper write up about it without the fearmongerng titles.
biot 10y ago
Schneier's Law: "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break."
israrkhan 10y ago
maybe another AI system do crypt-analysis and break it. and nobody will know how it was broken.
pzh 10y ago
Isn't that a bit like "security through obscurity"? Unless I'm misunderstanding something, the cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. It would also be very hard to reason about, inspect, and prove correct. Please note that I'm in no way dissing the researchers' work. What they did is pretty cool, but I can't see an obvious way to use these AI-generated algorithms in production systems where you may need to certify their correctness.
- paradite 10y ago
  You may be right. It was mentioned in the paper: Our chosen network structure is not sufficient to learn general implementations of many of the mathematical concepts underlying modern asymmetric cryptography, such as integer modular arithmetic. We therefore believe that the most likely explanation for this successful training run was that Alice and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric schemes from symmetric schemes by obfuscation (Barak et al., 2012)). This belief is somewhat reinforced by the fact that the training result was fragile: upon further training of Alice and Bob, Eve was able to decrypt the messages. However, we cannot rule out that the networks trained into some set of hard-to-invert matrix operations resulting in “public-key-like” behavior. Our results suggest that this issue deserves more exploration.
  - dgacmu 10y ago
    Note that this was for the public-key formulation. For the secret key formulation, it is mixing in the key, so it's not pure security through obscurity. It may be -- probably is -- relatively poor cryptography, but it's not just doing a transformation of the plaintext without using the key. The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future. But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?
deleted 10y ago
[deleted]
anupshinde 10y ago
"no one knows how it works" - That caught my attention, having seen computer evolved ASTs. Probably no one knows because no one has put effort to reverse engineer the internals - most of which would be unnecessary complexity that is very likely with neural nets. Many years back, I had once experimented with PyEvolve to develop a custom trading strategy which was kind-of code with a custom instruction set. The output of a strategy was a string (program AST) that was uglier than most obfuscation outputs with many unnecessary statements. For example "a=1;b=2;c=a+b;d=c/3;if(d==1).." - expand that to many more variables. The program evolved strategies that made small profit and therefore the output was worth analysing. But decompiling that output used to take me hours - and few of those were tweaks of well documented strategies. Others I never understood because it was too much effort for a relatively small profit (and other trading parameters).
- dflock 10y ago
  Could you not automate that too? Have another stage of evolution where you just randomly delete statements from the 'code' and the fitness function is that the performance doesn't get worse. This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.
  - fbonetti 10y ago
    Deleting random lines of code? That's like the bogosort of machine learning.
    - timtadh 10y ago
      It is actually called Delta Debugging and was pioneered by Andreas Zeller (https://www.st.cs.uni-saarland.de/dd/ https://www.st.cs.uni-saarland.de/dd/). His first paper on it ("Yesterday, my program worked. Today, it does not. Why?") used essentially the technique above to isolate the failure inducing change. Surprisingly, techniques like this work very well and doing better is sometimes very difficult especially for large programs. For instance, in theory, using "Concolic Execution" which combines symbolic execution, constraint solving, and concrete execution one can do better. However, such systems have their own limitations with respect to program complexity. See also the tremendous effectiveness of AFL (American Fuzzy Lop) http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ . AFL uses a straight forward technique to mutate code. It doesn't use any fancy program analysis and has been able to find lots of bugs in real programs.
msh 10y ago
What could ever go wrong with this....
rfreytag 10y ago
It must be the time for Cryptography + Machine Learning. I had an O'Reilly Security 2016 talk "Machine Learning to Improve Random Number Generators" accepted this June 2016: http://conferences.oreilly.com/security/network-data-security-eu/public/schedule/detail/53732 http://conferences.oreilly.com/security/network-data-securit... EDIT: I thought the reference was relevant but please do critique/comment if you feel I've broken some convention.
deegles 10y ago
Google should teach an AI to do prime factorization instead.
- rak00n 10y ago
  Why?
JulianMorrison 10y ago
Isn't this just the automated version of "anybody can invent crypto they can't break themselves"? It doesn't sound like the neural nets were provided with any high level cryptanalytic primitives. Just basic math and left to bodge something together. I can't imagine it would be easy to hill-climb towards an understanding of the why behind crypto. Algorithms that work look a lot like ones that have glaring flaws - but those flaws only glare if you know the right way to come at them.
greggman 10y ago
For those that can handle old pre CG movies there's a great old movie where computers make their own language. Highly recommended Colossus: The Forbin Project (1970) http://www.imdb.com/title/tt0064177/combined http://www.imdb.com/title/tt0064177/combined
rubyfan 10y ago
Teach the AI to communicate with each other in a way humans can't eavesdrop on... What could go wrong with that?!?
nullc 10y ago
"No one knows how it works" Yea, someone might also have said that about the GOST sboxes: https://eprint.iacr.org/2015/812 https://eprint.iacr.org/2015/812
akfish 10y ago
This reminds me of Peter Watts's novel <Blindsight>. Two captured "Scramblers" (the highly intelligent alien without self-consciousness) managed to communicate with each other in a way defying all human analysis, even with human knowing what they are saying (the plain text).

519 points by wallflower 10y ago

> While it seems improbable that neural networks would become great at cryptanalysis, they may be quite effective in making sense of metadata and in traffic analysis. How does that square with the fact that the best cryptanalists appear to have nothing but their own neural networks to work with? This reminds me of the genetic algorithm that came up with a tone discriminator that at first glance looked like it could not work (parts connected wrong or not at all, and yet, crucial to functioning). https://www.damninteresting.com/on-the-origin-of-circuits/ https://www.damninteresting.com/on-the-origin-of-circuits/

dgacmu 10y ago
Because humans have invented tools - math, notably - that they can use to be more formal and precise when they deal with problems of this sort. To date, neural networks can't -- they're doing very well at the kind of "intuitive" pattern matching that our brains do, but less well on an algorithmic front. It's one of the really interesting frontiers of AI right now. The folks at DeepMind recently showed, for example, that a variant of their "Neural Turing Machine" architecture could learn to do things involving more like what we think of as discrete algorithms (https://deepmind.com/blog/differentiable-neural-computers/ https://deepmind.com/blog/differentiable-neural-computers/ ), but all of this is very early work.
adrianN 10y ago
The words "neural network" describe pretty different things, depending on whether a computer scientist or a neuroscientist use them.

widforss 10y ago

This is most probably a rather lousy hack put together by Alice and Bob, but it maps out a very interesting future were we one day maybe can stop worrying about how our algorithms work and make that the job of the computer. It also is totally terrifying to live in a world were computers can hide their messages from their own creators.

n4ss 10y ago
It doesn't. As an AI developer you have access to the AI code and memory.. How could you not replay the encryption process used by the AI since you know the state of what it "knows" constantly? Both have a encryption and decryption process that you can reproduce.
- sdegutis 10y ago
  You can replay it, but you might not necessarily be able to understand it fully. Kind of like how beginner programmers can't necessarily understand advanced algorithms just by reading the code or walking through it in a debugger. They may need someone to help guide them through it and teach them how it works, and they will need the intelligence to be able to comprehend it. If the algorithm is designed by an AI, we may not have either.
  - kybernetikos 10y ago
    We may have AIs that can help guide you through code written by other AIs.
- mason55 10y ago
  You might be able to follow the steps that the computer takes but you won't necessarily know why. Why is that the magic constant is chose, what is the purpose of those branches, etc. And likely, if it's necessary, the AI can continue to evolve the algorithms faster than you can figure out what it's doing.
  - Cyph0n 10y ago
    Why? That simply depends on how the code was written. The magic constant may be chosen randomly, or based on previous guesses, or generated by another program, etc.
    - pi-err 10y ago
      Could't the source get encrypted as well? Also the cognitive gap between a AI and a human brain has to grow and transform unpredictably in the next decades. We may be puzzled to understand how it "thinks" the same way we still don't get exactly how DNA operates.

trungaczne 10y ago

This is the link to the research paper ("Learning to protect communications with adversarial neural cryptography"): https://arxiv.org/abs/1610.06918 https://arxiv.org/abs/1610.06918

systemfreund 10y ago

It's not clear from the article whether they train the networks with the same shared-key in every iteration, or if they randomize it. Any info on that?

anotheryou 10y ago
I thought no key/public key, but it really doesn't say
dgacmu 10y ago
It's a random key paired with a random plaintext for each input. In the experiments, the key is the same length as the plaintext. Happy to answer more questions about it. (I'm one of the authors.)
- rcorin 10y ago
  So basically the NN is learning a one time pad?
  - dgacmu 10y ago
    Kind of. Except that there's no restriction that there has to be a 1:1 correspondence between the key and plaintext bits (or characters) that get mixed, as there would be in a conventional OTP. And, indeed, the DNN doesn't learn that - it mixes multiple key and plaintext bits together. Probably in a way that's worse than a true OTP -- the adversary is more successful than it should be were the encryption scheme a "correct" OTP with XOR.
    - rcorin 10y ago
      Cool! Also, have you tried giving some bits of the key to the adversary?
      - dgacmu 10y ago
        I haven't. Interesting - that'd be a nice way to try to probe how strong the encryption is (i.e., "bits recovered vs. key bits supplied to adversary"). I'll have to think about that more - thanks for the idea!

deleted 10y ago

[deleted]

JackFr 10y ago

This seems pretty click-baity to me. Especially "no one knows how it works." Alice generates ciphertext based on plain text and key. Bob generates plaintext based on ciphertext and key. Eve generates plaintext based on only ciphertext. Train the three networks across a variety of plaintetxts, No doubt it's cool, but I would be very surprised if it offered any insight into, or represented an advance for strong cryptography.

bkin 10y ago
Jinxed! :-)
cheez 10y ago
This is less about cryptography and very much about neural networks making stuff.
pohl 10y ago
I might be reading your comment incorrectly, but it sounds like you're interpreting that phrase to mean that no one knows how training the neural network works. I think, instead, it's in reference to the resulting function not having been analyzed. From the article: The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob...
- rjbwork 10y ago
  >I think, instead, it's in reference to the resulting function not having been analyzed. I think it may be that it is "unanalyzable" if you will. Thousands of matrices multiplied together seems as if it would be hard to come to an actual understanding of...
  - patrickmn 10y ago
    This right here is why machine learning--although very exciting--is an incredibly frustrating endeavor compared to software engineering. It's statistics at its "worst." At the risk of glorifying AI, a good analogy might be that understanding a complex neural network is similar in nature to trying to understand how neurons in a human brain are wired, and why they cause some things to happen (or not happen) with some probability. It's more like the practice of medicine than it is engineering.

bkin 10y ago

TFA's title is a little clickbaity by adding "noone knows how it works" which apparently means that: The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR. In particular, the output values are often floating-point values other than 0 and 1," they said. Just saying...

Strilanc 10y ago
Outputting floats instead of discrete values actually sounds like a very exploitable hole to me. It reminds me of the classic "check if your model corresponds to reality" example where a one-time pad is broken: the standard said "<0.5V volts is OFF" but your machine was outputting 0.1V for OFFs that came from computing 0 xor 0 and 0.2V for OFFs that came from computing 1 xor 1.

pmyjavec 10y ago

Poor taste with the Terminator graphic. A new level of lame fear mongering by Ars Technica?

dharma1 10y ago
I was hoping psychedelic dog heads would become the default stock photo for AI news, rather than red eyed robots

chiefalchemist 10y ago

By the time we finally realize we're not as smart as we think we are, it's going to be too late.

chiefalchemist 10y ago

By the time we finally realize we're not as smart as we think we are, it's going to be too late.

Touche 10y ago

I'm not sure what conclusions we're supposed to draw from this. Just because they were able to hide the messages from a 3rd AI doesn't mean the encryption was good. Shouldn't a human examine it and see if they can codebreak it? Isn't the goal better encryption?

dgacmu 10y ago
I don't want to tell people what to take away from it, but my own view is that the contribution of the paper is the framing of the problem and a preliminary demonstration that you can achieve the goal of defeating a NN via an adversarial training formulation. In a lot of ways, I view our work as creating a challenge problem for the AI & crypto communities. It shows an intriguing possibility that is far from being practical, and itself represents a stepping stone in work on, e.g., training DNNs to learn to communicate. Can this be extended to generate cryptanalysis-resistant schemes? Can we create a formulation that can learn to use discrete operators such as modular arithmetic? (The latter reflects one of my personal complaints about the state of DNNs -- it's very hard to have discrete "blocks" of functionality if that functionality isn't differentiable). Can we identify mechanisms that can train networks such as these more robustly? (It fails to train roughly half of the time; this is a fairly common problem in adversarial training of DNNs today.)
- jsprogrammer 10y ago
  NNs/ANNs/DNNs/xNNs have already[0] been framed as easily fooled. [0] https://arxiv.org/pdf/1412.1897.pdf https://arxiv.org/pdf/1412.1897.pdf

ajamesm 10y ago

Hill climber climbs hill, news at 11?

fooker 10y ago
Interesting choice of words!

jdimov10 10y ago

Duplicate of https://news.ycombinator.com/item?id=12800228 https://news.ycombinator.com/item?id=12800228

traviswingo 10y ago

I get the sense that many commenters misinterpreted the point of this study. This isn't about show-boating some newfound, great cryptography method, this is about teaching computers to re-write their own code. If you can write software that improved itself better over time, our species as a whole would advance at incredible speeds. Think about all the possibilities that could evolve from self-maintained programs. Obviously the thought is a bit scary, but it's also incredibly exciting!

FT_intern 10y ago
and here I was as a programmer bragging about automating people's jobs...
ape4 10y ago
Its not their own code. Its code they own.
gcr 10y ago
Please don't editorialize. Finding the best parameters that optimize an objective function can hardly be called "re-writing its own code." Granted, the article is just as guilty. (Edit: The article also doesn't mention self-modifying code so I'm not sure where you're getting that idea from.) For the curious, here is the preprint: https://arxiv.org/pdf/1610.06918v1.pdf https://arxiv.org/pdf/1610.06918v1.pdf The technique is an off-the-shelf GAN that attempts to learn a transformation (not arbitrary code!) from input to encrypted output. The learned model is not Turing complete, and most importantly, is _not_ self-modifying. The optimization procedure is what modifies the network, not the network itself. GANs have been used before to create realistic pictures. They're not new here -- the application is. It's a cool application, sure, but doesn't involve self-modifying code.
- Houshalter 10y ago
  I don't think it's entirely inaccurate to call neural networks "rewriting their own code". For a long time people experimented with algorithms that could actually rewrite human programming languages, like genetic programming. And it's mostly a failure, because most mutations to most programs just break them. Neural networks fix this problem by being sort of 'continuous programming language' where any small change to the net results in a small change to the output. And because of that we have algorithms that can find good changes to make much easier than with code. They are theoretically turing complete under some circumstances. But even when they aren't completely recurrent as in this case, they can still learn very sophisticated functions. Theoretically a neural net can learn anything a fixed number of logic gates can learn, which is still pretty powerful. I don't think parent comment meant by computers that can "re-write their own code" was that the programs are self modifying. But the computer itself is self modifying, as one program can change another on that computer, so the computer has modified itself.

asveikau 10y ago

> this is about teaching computers to re-write their own code. Maybe I've seen too many movies, but I hope we can make sure they don't rewrite the "protect the humans" part.

tener 10y ago
It would be very hard to ensure that.
- asveikau 10y ago
  Especially when they decide that the most logical way to protect them is to destroy them.
  - tener 10y ago
    I have yet to write down a o longer post on this, but honestly I think AI have little chance to operate on purely logical terms. This thinking about paradoxes comes from the time when people approached AI with Prolog etc. They didn't get really far.
treehau5 10y ago
but don't we then just unleash the huge EMP bomb?
- TeMPOraL 10y ago
  Not if any stage of the unleashing process is connected to the Internet.
- nkozyra 10y ago
  Sounds good. Sadly, six months ago the bot brain predicted the day we were planning with .98 confidence.
  - idlewords 10y ago
    But then it got sucked in to TVTropes, and the world is saved.

excalliburbd 10y ago

Am I the only one wondering about this and Ethereum...

drdeca 10y ago
Do you mind elaborating? If you are talking about a smart-contract being able to do stuff with encrypted data without other people being able to access the data, I don't think this would help with that, because whatever system the contract would use would be available to whoever is trying to get the data from the contract. Though, things may be enough to make it hard for other contracts to get stuff from a particular contract? I'm somewhat skeptical of that, but maybe. Also, in any case, the "attacker" contract could just make an incentive for people to give it the information, which I think would work. (and that might be necessary for it to get the info from the defending contract anyway? I don't remember. I don't think it is, but I'm not sure.) However, I'm not sure that is what you meant, and also I'm not sure of what I'm saying. edit: well, there are other systems that have been designed to let contracts keep information secret but I think those are still too expensive to be used, and relied on a secret sharing scheme iirc, so would require that not all the info be on chain.

madenine 10y ago

Really interesting that for the first ~6500 steps Eve was better at decrpyting the messages than Bob, which had access to the key. Would be cool to see a setup like this in which Eve is a cohort of decryption tools, otherwise your Alice network will just overfit against its mechanics. Ie, if Eve uses lockpicks to open a door, an Alice solution would eventually replace the key-lock with a number pad - not necessarily any more secure, but will foil Eve every time.

timvdalen 10y ago
>Really interesting that for the first ~6500 steps Eve was better at decrpyting the messages than Bob, which had access to the key. This is probably because Alice wasn't good at encrypting yet.
- madenine 10y ago
  On a second look, seems like a combination of Alice not being good at encrypting (in a sense that it had to encrypt in a way that makes decrpytion possible), and Bob needed to get up to speed on decrypting (even with the key). As soon as that relationship clicks, Bob get better very quickly, while Eve improves at a slower rate for a while, before Alice adjusts (causing bob to get worse for a bit, until it catches up) Would be interesting to see a set up where Alice / Bob get trained first, then Eve is activated and see how they adjust.

sly010 10y ago

"The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR." I think this says it all.

wideem 10y ago

Next: Google AI encrypts google's servers and demand Ransom

wideem 10y ago

Next: Google AI encrypts google's servers and demand Ransom

martin-adams 10y ago

At an open day for an animation course they showed an AI derived walk cycle of a character. The results were amusing. The condition was that if it feel over that would be no good. The end walk cycle was a character doing forward flips in the air and landing on its feet. Very unexpected results.

strictnein 10y ago

Interestingly, Eve maintained a better than random chance at guessing the message. Consistently stayed a little better than 50%.

1_2__3 10y ago

Given I saw this as top on /r/futurology I figured it was clickbait BS. But since it was posted to HN I thought I'd give it a read. It's clickbait BS.

benmcnelly 10y ago
Its interesting, but needs someone to re-submit with a proper write up about it without the fearmongerng titles.

biot 10y ago

Schneier's Law: "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break."

israrkhan 10y ago

maybe another AI system do crypt-analysis and break it. and nobody will know how it was broken.

pzh 10y ago

Isn't that a bit like "security through obscurity"? Unless I'm misunderstanding something, the cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. It would also be very hard to reason about, inspect, and prove correct. Please note that I'm in no way dissing the researchers' work. What they did is pretty cool, but I can't see an obvious way to use these AI-generated algorithms in production systems where you may need to certify their correctness.

paradite 10y ago
You may be right. It was mentioned in the paper: Our chosen network structure is not sufficient to learn general implementations of many of the mathematical concepts underlying modern asymmetric cryptography, such as integer modular arithmetic. We therefore believe that the most likely explanation for this successful training run was that Alice and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric schemes from symmetric schemes by obfuscation (Barak et al., 2012)). This belief is somewhat reinforced by the fact that the training result was fragile: upon further training of Alice and Bob, Eve was able to decrypt the messages. However, we cannot rule out that the networks trained into some set of hard-to-invert matrix operations resulting in “public-key-like” behavior. Our results suggest that this issue deserves more exploration.
- dgacmu 10y ago
  Note that this was for the public-key formulation. For the secret key formulation, it is mixing in the key, so it's not pure security through obscurity. It may be -- probably is -- relatively poor cryptography, but it's not just doing a transformation of the plaintext without using the key. The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future. But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?

deleted 10y ago

[deleted]

anupshinde 10y ago

"no one knows how it works" - That caught my attention, having seen computer evolved ASTs. Probably no one knows because no one has put effort to reverse engineer the internals - most of which would be unnecessary complexity that is very likely with neural nets. Many years back, I had once experimented with PyEvolve to develop a custom trading strategy which was kind-of code with a custom instruction set. The output of a strategy was a string (program AST) that was uglier than most obfuscation outputs with many unnecessary statements. For example "a=1;b=2;c=a+b;d=c/3;if(d==1).." - expand that to many more variables. The program evolved strategies that made small profit and therefore the output was worth analysing. But decompiling that output used to take me hours - and few of those were tweaks of well documented strategies. Others I never understood because it was too much effort for a relatively small profit (and other trading parameters).

dflock 10y ago
Could you not automate that too? Have another stage of evolution where you just randomly delete statements from the 'code' and the fitness function is that the performance doesn't get worse. This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.
- fbonetti 10y ago
  Deleting random lines of code? That's like the bogosort of machine learning.
  - timtadh 10y ago
    It is actually called Delta Debugging and was pioneered by Andreas Zeller (https://www.st.cs.uni-saarland.de/dd/ https://www.st.cs.uni-saarland.de/dd/). His first paper on it ("Yesterday, my program worked. Today, it does not. Why?") used essentially the technique above to isolate the failure inducing change. Surprisingly, techniques like this work very well and doing better is sometimes very difficult especially for large programs. For instance, in theory, using "Concolic Execution" which combines symbolic execution, constraint solving, and concrete execution one can do better. However, such systems have their own limitations with respect to program complexity. See also the tremendous effectiveness of AFL (American Fuzzy Lop) http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ . AFL uses a straight forward technique to mutate code. It doesn't use any fancy program analysis and has been able to find lots of bugs in real programs.

msh 10y ago

What could ever go wrong with this....

rfreytag 10y ago

It must be the time for Cryptography + Machine Learning. I had an O'Reilly Security 2016 talk "Machine Learning to Improve Random Number Generators" accepted this June 2016: http://conferences.oreilly.com/security/network-data-security-eu/public/schedule/detail/53732 http://conferences.oreilly.com/security/network-data-securit... EDIT: I thought the reference was relevant but please do critique/comment if you feel I've broken some convention.

deegles 10y ago

Google should teach an AI to do prime factorization instead.

rak00n 10y ago
Why?

JulianMorrison 10y ago

Isn't this just the automated version of "anybody can invent crypto they can't break themselves"? It doesn't sound like the neural nets were provided with any high level cryptanalytic primitives. Just basic math and left to bodge something together. I can't imagine it would be easy to hill-climb towards an understanding of the why behind crypto. Algorithms that work look a lot like ones that have glaring flaws - but those flaws only glare if you know the right way to come at them.

greggman 10y ago

For those that can handle old pre CG movies there's a great old movie where computers make their own language. Highly recommended Colossus: The Forbin Project (1970) http://www.imdb.com/title/tt0064177/combined http://www.imdb.com/title/tt0064177/combined

rubyfan 10y ago

Teach the AI to communicate with each other in a way humans can't eavesdrop on... What could go wrong with that?!?

nullc 10y ago

"No one knows how it works" Yea, someone might also have said that about the GOST sboxes: https://eprint.iacr.org/2015/812 https://eprint.iacr.org/2015/812

akfish 10y ago

This reminds me of Peter Watts's novel <Blindsight>. Two captured "Scramblers" (the highly intelligent alien without self-consciousness) managed to communicate with each other in a way defying all human analysis, even with human knowing what they are saying (the plain text).