No, the universal selector * does not affect pseudo-elements (except indirectly via inheritance, as pseudo-elements are typically generated as children of actual elements).
The universal selector, like other named element selectors such as p and div, is a simple selector:
A simple selector is either a type selector, universal selector, attribute selector, class selector, ID selector, or pseudo-class.
A simple selector, and by extension any complex selector, targets only actual elements.
Although pseudo-elements (which are not the same thing as pseudo-classes mentioned above) can appear in selector notation alongside simple selectors, pseudo-elements are completely separate from simple selectors as they represent abstractions of the DOM that are separate from actual elements, and therefore both represent different things. You cannot match a pseudo-element using a simple selector, nor can you apply styles to an actual element in a CSS rule with a pseudo-element in its selector.
So, in order to match :before and :after pseudo-elements of any element, yes, one will need to include *:before, *:after in the selector. Having just * { box-sizing: border-box; } will not affect them since box-sizing is not normally inherited, and as a result, they will retain the default box-sizing: content-box.
One possible reason why you might never have had any issues with pseudo-elements is that they're displayed inline by default, as box-sizing has no effect on inline elements whatsoever.
Some notes:
As with any other chain of simple selectors, if * is not the only component then you can leave it out, which means *, :before, :after is equivalent to *, *:before, *:after. That being said, the * is usually included for the sake of clarity — most authors are used to leaving the * out when writing ID and class selectors, but not pseudo-classes and pseudo-elements, so the notation may seem strange and even wrong to them (when it is in fact perfectly valid).
The current Selectors specification that I link to above represents pseudo-elements with double colons. This is a new notation introduced in the current spec to distinguish pseudo-elements from pseudo-classes, but most box-sizing resets use the single colon notation to accommodate IE8, which supports box-sizing but not the double colon notation.
Although *:before, *:after applies styles to the respective pseudo-elements of any element, which includes html, head and body, the pseudo-elements will not actually be generated until you apply the content property. You do not have to worry about any performance issues as there are none. For a detailed explanation, see my answer to this related question.
