Suppose that I have an AES key $K$, and I'm instructed to find a plaintext such that the first 32 bits of the plaintext are some string of bits $S_1$, and the last 32 bits of the ciphertext once the plaintext has been encrypted with $K$ are another string of bits $S_2$.
Is this difficult? Is there a known attack against this that's faster than just fixing one of the $S$'s and brute-force searching for a text with the other $S$?
NO! AES is rated to withstand cryptanalysis so long as it remains a black box to the attacker (IE:round keys are unknown variables). Up until the SHA3 competition no one had done cryptanalysis on AES with known internal state. This is the relevant paper, specifically section 3.5 which solves the exact problem you are proposing. Given AES with a fixed key K acting as a pseudorandom permutation, find a solution to C=AESenc(P,K) with restrictions on C and P
There are also attacks on AES when used as a typical hash compression function (IE:state[i]=AES(state[i-1],K=data[i]). These allow for collisions and generally for breaking the pseudorandom permutation property of AES to find specific solutions for equations involving it.
There are probably some problems that remain hard, like reversing a one way function composed from AES (IE:F(X)=AES(X,Kfixed)⊕X , Y=F(X) , Find X given Y). Even here I'd be nervous but much less so. This is the ideal case. No degrees of freedom for the attacker to work with.
When you see "secure pseudorandom permutation" thrown around in the context of AES remember the fine print attached to all that analysis: "for unknown K"
Well, it's moderately difficult; you couldn't use that as a security assumption; however, it would be too difficult to expect someone to solve during an active protocol. There's no nonobvious trick to it; the two methods at your disposal would be:
Select random plaintexts with the first 32 bits as $S_1$; encrypt them with key $K$, and check to see if the last 32 bits of the ciphertext happen to be $S_2$
Select random ciphertexts with the last 32 bits as $S_2$; decrypt them with key $K$, and check to see if the first 32 bits of the plaintext happen to be $S_1$
Either approach will take an expected $2^{32}$ random trials before success; at 1 $\mu$sec per AES operation (quite conservative; modern CPUs typically can do several times as fast as that), we're looking at perhaps an hour or two.
Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out. For example, you might be hoping to translate the AES cipher into a large series of boolean operations (with the known key, and known 32 bits of plaintext and ciphertexts), and solve the resulting set of equations. However, AES has a fairly quick 'avalanche'; very quickly (within two rounds), all the internal bits will depend on all the unknown bits in subtle ways; the resulting set of equations will not have an easier solution than just trying various combinations of the 96 bits on one side (which is effectively what the straight-forward solutions do)
For an ideal 128-bit block cipher (a family of random permutations on the set of 128-bit blocks), there's no better way to find such pairs than the brute force method described by poncho. If a significantly more efficient method did exist for AES, that would allow efficiently distinguishing AES from an ideal block cipher, which would contradict the security assumptions of AES.
As no such attack has been published, despite the considerable amount of cryptanalytic research on AES, we can be fairly confident that there's no easily discoverable method to find such pairs that would be more efficient than brute force.
