11 ms·

> As the KRACK paper points out, there is no formal description of the 802.11i handshake state machine. This, to me, is one of the biggest problems facing our

> As the KRACK paper points out, there is no formal description of the 802.11i handshake state machine. This, to me, is one of the biggest problems facing our industry. In first year undergraduate in engineering we learn how to design a state machine. We learn to design one before we learned OOP and circuits and assembly. Yet, how many APIs or Protocols have you come across or has your organization developed where there isn't a state machine described somewhere. It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. We programmers sometimes spend far too much time juggling stuff in our heads and communicating with coworkers in a wonderful game of workplace telephone. If the state machine has become too complex, then we have lost all hope to fully manage it and must accept the risks. Some things just shouldn't be risked!

eradicatethots 9y ago
It is tedious. It’s inefficient. Quality software usually is less important than working software.
- maldeh 9y ago
  Unless I'm misinterpreting the meaning of "usually" or "important", I find this comment a little bewildering in the context of the article.
  - katastic 9y ago
    In the working world, what matters is you ship. The most beautiful code and best "game ever designed" means nothing if it doesn't ship. Additionally, in my years of working as a contractor, I can tell you that nearly 1 in 1,000 companies (+ or - 1) care about security. Management simply does not value it, and everyone already thinks your product "should have been done yesterday." The entire world runs on insecure products. From banks, to healthcare, to universities. I can list every one of those who has put admin credentials in a publicly, internet accessible text file. (But they'll do silly things like insanely unmemorizable passwords like 23ix2n5 that get written down as postit notes and as files on desktops, and disable RDP copy-and-paste but leave RDP hard drive support.) We're going to continue seeing these blunders day after day until people start going to jail for losing data.
    - digi_owl 9y ago
      Or stop treating programming like some grand joust...
      - TeMPOraL 9y ago
        We won't. Worse is better, remember? Especially when a typical company wants to be the first to quickly sell some shit product and then, maybe, they'll patch it for a while as they go along. Competitive pressures (and management fads, IMO - software market ain't that efficient yet) turned "good solution today > perfect solution next week" into "steaming pile of garbage today > good solution tomorrow". I guess this is fine for throwaway acquihire SaaS stuff, but it's becoming a serious problem for stuff that's meant to be widely used.
  - emmelaich 9y ago
    Consider it descriptive rather than prescriptive.
- InclinedPlane 9y ago
  Can you think of any particular circumstances where quality would be of paramount importance? I'll wait.
  - jdhendrickson 9y ago
    Pacemaker firmware comes to mind.
    - colejohnson66 9y ago
      You’d think: https://arstechnica.com/information-technology/2017/08/465k-patients-need-a-firmware-update-to-prevent-serious-pacemaker-hacks/ https://arstechnica.com/information-technology/2017/08/465k-...
- criddell 9y ago
  I've been working in the same code base one way or another for more than 20 years now. Quality is underrated.
userbinator 9y ago
This, to me, is one of the biggest problems facing our industry. In first year undergraduate in engineering we learn how to design a state machine. We learn to design one before we learned OOP and circuits and assembly. I think one of the causes is that a lot of CS is taught top-down and not bottom-up, so things like flowcharts, state diagrams, and other similar visual aids are completely skipped in preference to more abstract thinking. I wonder if at least some of this aversion is directly related to the "gotophobia" that started with Dijkstra's famous paper. It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. As someone who learned the "old school" way of planning out your code --- yes, even drawing flowcharts and state diagrams --- before writing a single line of it, I can assuredly say that it should be a natural and completely pleasant process; what's "difficult and tedious" is trying to debug and coerce something you (or someone else) wrote without planning into working correctly. Over the years coworkers have been puzzled at why I spend "so much time" flowcharting and just thinking before writing even a single line of code --- only to try adopting the same method once they realise how much time it saves in total, since all the cases have already been accounted for and the only thing left to do is test out any of the few remaining and often trivial bugs introduced during the design->code process.
- digi_owl 9y ago
  It also takes all the "fun" out of programming, as so many seems to approach it like some grand display of mental prowess. Never mind the whole "agile" thing...
  - reitanqild 9y ago
    You can look at this both ways actually: For some people (like me) thinking through problems with pen and paper is a tool. For others I guess it is annoying: look at him, now he's doing this wannabe software architect stuff again. Same might go the other way: here he goes again, trying to prove his programming super skills by jumping into it without even the smalles amount of planning.
    - Swizec 9y ago
foobarian 9y ago
I find it interesting how in a large codebase or project there is a temptation to mutate an object here, decorate some intermediate object there, and before you know it you have an ugly state machine hiding in your code. As you know the number of possible states grows very fast and when people don't know this is happening things soon get out of control. Having things immutable by default helps somewhat, but it's still easy to add various decorators.
technion 9y ago
I guess a related question would be, is anyone aware of a common protocol that does have a formally defined state machine to review?
- scott_karana 9y ago
  TCP's might not be formally defined (unsure), but it's pretty well understood to the point of having de facto ones, at least.
  - userbinator 9y ago
    There are state diagrams in the TCP RFC --- in ASCII art, so the authors clearly really wanted to have one.
    - scott_karana 9y ago
      Nice! Good to know. That must be the origin of all the useful but unofficial SVG ones I'd seen :)
- lsh123 9y ago
  SSL
  - tom_mellior 9y ago
    Here is really cool work on state machines in TLS: https://www.smacktls.com/smack.pdf https://www.smacktls.com/smack.pdf Beurdouche et al., "A Messy State of the Union: Taming the Composite State Machines of TLS" From the abstract: "mplementations of the Transport Layer Security (TLS) protocol must handle a variety of protocol versions and extensions, authentication modes and key exchange methods, where each combination may prescribe a different message sequence between the client and the server. We address the problem of designing a robust composite state machine that can correctly multiplex between these different protocol modes. We systematically test popular open-source TLS implementations for state machine bugs and discover several critical security vulnerabilities that have lain hidden in these libraries for years ..." Based on this work you might say that there are formal state machines for TLS, but they aren't in the standard.
bdcravens 9y ago
> It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. Don't agile approaches encourage this, focusing on features and things that can cleanly be assigned story points at the expense of a bigger picture, with velocity being the focus?
- maskedSlacker 9y ago
  It seems to me that agile approaches are a response to the phenomena of the spec often being wrong. If the spec is wrong and going to need substantial revision, iteration is better than planning. If the spec is not wrong, careful planning is probably better than high velocity iteration. I think cryptography is a good example of this--would you develop a cryptographic API on which people's lives might depend iteratively through a release early and fail often method? I hope not.
  - taneq 9y ago
    Exactly, and this is why Agile (while grand for things like "The customer wants a web site. They don't know what they want or how they want it to look, but we need to start on Tuesday.") isn't the be-all and end-all that it's advertised to be by people who only work on websites for tech-illiterate customers. In a lot of software development, especially large scale enterprise software (where you're trying to map a complex set of existing business practices and workflows into software) and embedded software (where you have to write something that provides fixed, well-understood functionality running on hardware with a months- or years-long iteration time) you do have a complete and correct spec (or at least the means to generate one). In these cases a less ad-hoc approach than Agile can be beneficial.
  - arohner 9y ago
    I upvoted this, but agile and "release early and fail often" aren't necessarily the same thing. For example, they could have iterated quickly during the draft phase, come up with a proposed implementation, have the security researchers review it, and iterate.
NamTaf 9y ago
Compare front-end [1] design philosophies (such as used in waterfall development) vs iterative design philosophies (such as in agile development). As a non-software, 'real world' engineer (mechanical, heavy industry design) looking in from the periphy of computing as a hobby/amateur interest, it appears to me like software engineering as a discipline has sort of forgotten about why and when FEED is appropriate and, critically, how to implement it when it is. Let's reflect: iterative design is popular in software engineering because software usually suits it. Changes are easily iterable, you can often roll changes back, there's relatively low cost to cloning changes across millions of instances, code's design lifetime is relatively short, etc. In contrast, 'real world' engineering (civil, heavy mechanical) favours FEED because the cost of change rapidly and prohibitively rises with time, so nailing down the scope and structure early is critical, there's long procurement times for changes, the design lifetime of the finished product is measured in decades, etc. The rub is that there's a small niche of software design, such as protocol design like this, or certain firmware scenarios, which far more closely resembles the latter even though it's usually done by a community used to and trained in the former. Although it's for different reasons, all the things that make FEED appropriate for 'real world' engineering also apply to these sorts of software tasks, but software engineering as a whole doesn't appear to[2] focus on teaching and supporting the necessary tools and techniques for performing that process well. Flip that on its head, and it's why software companies quickly begin to run rings around companies traditionally focused on hardware once software starts to play a bigger part and the limitations stopping iterative design from working begin to disappear. Software engineering largely biases towards iteration (understandably) and when it works it allows for good advantages. But in embracing those advantages, software engineering as a discipline has begun to lose an understanding of FEED and the careful methodology it delivers. [1]: https://en.wikipedia.org/wiki/Front-end_engineering https://en.wikipedia.org/wiki/Front-end_engineering & https://en.wikipedia.org/wiki/Front-end_loading https://en.wikipedia.org/wiki/Front-end_loading [2] I admit I've not done a CS/SE degree, but I've gone through a couple of subjects run online and I talk to friends who did do it and that's the feel I get. Besides, just look at HN's generally trending articles. edit: With all I wrote, I don't mean to undermine the extremely good work that the devs designing these protocols, etc. almost always perform. It's far beyond my ability. I am speaking more in a general sense about how Soft. Eng. seems to have thrown out the baby with the bathwater in declaring agile philosophies as 'the best way'. My feel is that the pendulum seems to have swung too far past 'best' towards becoming 'only'.
pfortuny 9y ago
Either engineering and its tools (eg state machines) or just craftmanship. Totally right.
pron 9y ago
> there is no formal description of the 802.11i handshake state machine. Here is what the paper actually says: The 802.11i amendment does not contain a formal state machine describing how the supplicant must implement the 4-way handshake. ... Fortunately, 802.11r ... does provide a detailed state machine of the supplicant. The problem, as I understand it, was that when the protocol was formally verified, the properties checked were only the escape of the private key and identity related issues. The property of the nonce never being reset was simply not considered. The missing piece, then, wasn't a precise description of how the system works, but rather a precise list of what it's supposed to guarantee. Without a clear and concise description of the requirements, it's hard to verify that the system satisfies them. Alternatively, it's possible that the list of guarantees was complete, in which case reviewers should have noticed that no nonce reset isn't one of them, yet it's required for the security of certain communication protocols used over the channel.

eradicatethots 9y ago

It is tedious. It’s inefficient. Quality software usually is less important than working software.

maldeh 9y ago
Unless I'm misinterpreting the meaning of "usually" or "important", I find this comment a little bewildering in the context of the article.
- katastic 9y ago
  In the working world, what matters is you ship. The most beautiful code and best "game ever designed" means nothing if it doesn't ship. Additionally, in my years of working as a contractor, I can tell you that nearly 1 in 1,000 companies (+ or - 1) care about security. Management simply does not value it, and everyone already thinks your product "should have been done yesterday." The entire world runs on insecure products. From banks, to healthcare, to universities. I can list every one of those who has put admin credentials in a publicly, internet accessible text file. (But they'll do silly things like insanely unmemorizable passwords like 23ix2n5 that get written down as postit notes and as files on desktops, and disable RDP copy-and-paste but leave RDP hard drive support.) We're going to continue seeing these blunders day after day until people start going to jail for losing data.
  - digi_owl 9y ago
    Or stop treating programming like some grand joust...
    - TeMPOraL 9y ago
      We won't. Worse is better, remember? Especially when a typical company wants to be the first to quickly sell some shit product and then, maybe, they'll patch it for a while as they go along. Competitive pressures (and management fads, IMO - software market ain't that efficient yet) turned "good solution today > perfect solution next week" into "steaming pile of garbage today > good solution tomorrow". I guess this is fine for throwaway acquihire SaaS stuff, but it's becoming a serious problem for stuff that's meant to be widely used.
- emmelaich 9y ago
  Consider it descriptive rather than prescriptive.
InclinedPlane 9y ago
Can you think of any particular circumstances where quality would be of paramount importance? I'll wait.
- jdhendrickson 9y ago
  Pacemaker firmware comes to mind.
  - colejohnson66 9y ago
    You’d think: https://arstechnica.com/information-technology/2017/08/465k-patients-need-a-firmware-update-to-prevent-serious-pacemaker-hacks/ https://arstechnica.com/information-technology/2017/08/465k-...
criddell 9y ago
I've been working in the same code base one way or another for more than 20 years now. Quality is underrated.

userbinator 9y ago

This, to me, is one of the biggest problems facing our industry. In first year undergraduate in engineering we learn how to design a state machine. We learn to design one before we learned OOP and circuits and assembly. I think one of the causes is that a lot of CS is taught top-down and not bottom-up, so things like flowcharts, state diagrams, and other similar visual aids are completely skipped in preference to more abstract thinking. I wonder if at least some of this aversion is directly related to the "gotophobia" that started with Dijkstra's famous paper. It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. As someone who learned the "old school" way of planning out your code --- yes, even drawing flowcharts and state diagrams --- before writing a single line of it, I can assuredly say that it should be a natural and completely pleasant process; what's "difficult and tedious" is trying to debug and coerce something you (or someone else) wrote without planning into working correctly. Over the years coworkers have been puzzled at why I spend "so much time" flowcharting and just thinking before writing even a single line of code --- only to try adopting the same method once they realise how much time it saves in total, since all the cases have already been accounted for and the only thing left to do is test out any of the few remaining and often trivial bugs introduced during the design->code process.

digi_owl 9y ago
It also takes all the "fun" out of programming, as so many seems to approach it like some grand display of mental prowess. Never mind the whole "agile" thing...
- reitanqild 9y ago
  You can look at this both ways actually: For some people (like me) thinking through problems with pen and paper is a tool. For others I guess it is annoying: look at him, now he's doing this wannabe software architect stuff again. Same might go the other way: here he goes again, trying to prove his programming super skills by jumping into it without even the smalles amount of planning.
  - Swizec 9y ago

foobarian 9y ago

I find it interesting how in a large codebase or project there is a temptation to mutate an object here, decorate some intermediate object there, and before you know it you have an ugly state machine hiding in your code. As you know the number of possible states grows very fast and when people don't know this is happening things soon get out of control. Having things immutable by default helps somewhat, but it's still easy to add various decorators.

technion 9y ago

I guess a related question would be, is anyone aware of a common protocol that does have a formally defined state machine to review?

scott_karana 9y ago
TCP's might not be formally defined (unsure), but it's pretty well understood to the point of having de facto ones, at least.
- userbinator 9y ago
  There are state diagrams in the TCP RFC --- in ASCII art, so the authors clearly really wanted to have one.
  - scott_karana 9y ago
    Nice! Good to know. That must be the origin of all the useful but unofficial SVG ones I'd seen :)
lsh123 9y ago
SSL
- tom_mellior 9y ago
  Here is really cool work on state machines in TLS: https://www.smacktls.com/smack.pdf https://www.smacktls.com/smack.pdf Beurdouche et al., "A Messy State of the Union: Taming the Composite State Machines of TLS" From the abstract: "mplementations of the Transport Layer Security (TLS) protocol must handle a variety of protocol versions and extensions, authentication modes and key exchange methods, where each combination may prescribe a different message sequence between the client and the server. We address the problem of designing a robust composite state machine that can correctly multiplex between these different protocol modes. We systematically test popular open-source TLS implementations for state machine bugs and discover several critical security vulnerabilities that have lain hidden in these libraries for years ..." Based on this work you might say that there are formal state machines for TLS, but they aren't in the standard.

bdcravens 9y ago

> It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. Don't agile approaches encourage this, focusing on features and things that can cleanly be assigned story points at the expense of a bigger picture, with velocity being the focus?

maskedSlacker 9y ago
It seems to me that agile approaches are a response to the phenomena of the spec often being wrong. If the spec is wrong and going to need substantial revision, iteration is better than planning. If the spec is not wrong, careful planning is probably better than high velocity iteration. I think cryptography is a good example of this--would you develop a cryptographic API on which people's lives might depend iteratively through a release early and fail often method? I hope not.
- taneq 9y ago
  Exactly, and this is why Agile (while grand for things like "The customer wants a web site. They don't know what they want or how they want it to look, but we need to start on Tuesday.") isn't the be-all and end-all that it's advertised to be by people who only work on websites for tech-illiterate customers. In a lot of software development, especially large scale enterprise software (where you're trying to map a complex set of existing business practices and workflows into software) and embedded software (where you have to write something that provides fixed, well-understood functionality running on hardware with a months- or years-long iteration time) you do have a complete and correct spec (or at least the means to generate one). In these cases a less ad-hoc approach than Agile can be beneficial.
- arohner 9y ago
  I upvoted this, but agile and "release early and fail often" aren't necessarily the same thing. For example, they could have iterated quickly during the draft phase, come up with a proposed implementation, have the security researchers review it, and iterate.

NamTaf 9y ago

Compare front-end [1] design philosophies (such as used in waterfall development) vs iterative design philosophies (such as in agile development). As a non-software, 'real world' engineer (mechanical, heavy industry design) looking in from the periphy of computing as a hobby/amateur interest, it appears to me like software engineering as a discipline has sort of forgotten about why and when FEED is appropriate and, critically, how to implement it when it is. Let's reflect: iterative design is popular in software engineering because software usually suits it. Changes are easily iterable, you can often roll changes back, there's relatively low cost to cloning changes across millions of instances, code's design lifetime is relatively short, etc. In contrast, 'real world' engineering (civil, heavy mechanical) favours FEED because the cost of change rapidly and prohibitively rises with time, so nailing down the scope and structure early is critical, there's long procurement times for changes, the design lifetime of the finished product is measured in decades, etc. The rub is that there's a small niche of software design, such as protocol design like this, or certain firmware scenarios, which far more closely resembles the latter even though it's usually done by a community used to and trained in the former. Although it's for different reasons, all the things that make FEED appropriate for 'real world' engineering also apply to these sorts of software tasks, but software engineering as a whole doesn't appear to[2] focus on teaching and supporting the necessary tools and techniques for performing that process well. Flip that on its head, and it's why software companies quickly begin to run rings around companies traditionally focused on hardware once software starts to play a bigger part and the limitations stopping iterative design from working begin to disappear. Software engineering largely biases towards iteration (understandably) and when it works it allows for good advantages. But in embracing those advantages, software engineering as a discipline has begun to lose an understanding of FEED and the careful methodology it delivers. [1]: https://en.wikipedia.org/wiki/Front-end_engineering https://en.wikipedia.org/wiki/Front-end_engineering & https://en.wikipedia.org/wiki/Front-end_loading https://en.wikipedia.org/wiki/Front-end_loading [2] I admit I've not done a CS/SE degree, but I've gone through a couple of subjects run online and I talk to friends who did do it and that's the feel I get. Besides, just look at HN's generally trending articles. edit: With all I wrote, I don't mean to undermine the extremely good work that the devs designing these protocols, etc. almost always perform. It's far beyond my ability. I am speaking more in a general sense about how Soft. Eng. seems to have thrown out the baby with the bathwater in declaring agile philosophies as 'the best way'. My feel is that the pendulum seems to have swung too far past 'best' towards becoming 'only'.

pfortuny 9y ago

Either engineering and its tools (eg state machines) or just craftmanship. Totally right.

pron 9y ago

> there is no formal description of the 802.11i handshake state machine. Here is what the paper actually says: The 802.11i amendment does not contain a formal state machine describing how the supplicant must implement the 4-way handshake. ... Fortunately, 802.11r ... does provide a detailed state machine of the supplicant. The problem, as I understand it, was that when the protocol was formally verified, the properties checked were only the escape of the private key and identity related issues. The property of the nonce never being reset was simply not considered. The missing piece, then, wasn't a precise description of how the system works, but rather a precise list of what it's supposed to guarantee. Without a clear and concise description of the requirements, it's hard to verify that the system satisfies them. Alternatively, it's possible that the list of guarantees was complete, in which case reviewers should have noticed that no nonce reset isn't one of them, yet it's required for the security of certain communication protocols used over the channel.