Hypothesis Testing: Permutation Testing Justification Context: Hypothesis test using permutation testing about 2 populations, assuming I sample $k_{1}$ and $k_{2}$ items from population 1 and 2, respectively, where $k_{1}, k_{2} \in \mathbb{Z}^{\geq 1}$:
$H_{o}$: $m_{1} = m_{2}$; $H_{a} : m_{1} \not = m_{2}$ where $m_{x}$ refers to the median of population $x$.
Concern: In permutation testing, we'd compute the test statistic of interest ($\bar{m_{1}} - \bar{m_{2}}$) for each possible permutation (i.e. $(k_{1} + k_{2})!$) and use the histogram from these values as the null distribution (i.e. sampling distribution of the mentioned test statistic under the null hypothesis), using it to come up with a p-value. This seems to imply that by assuming the null hypothesis above, each permutation of our sample is equally likely, and it is this with which I do not agree. It seems to me to make this conclusion, the null hypothesis would have to be much more general (i.e. that the two populations have identical and independent distributions, as mentioned in http://sphweb.bumc.bu.edu/otlt/mph-modules/bs/bs704_nonparametric/bs704_nonparametric2.html), but then this would also mean that rejecting the null hypothesis would be rejecting of a much broader hypothesis and not our desired hypothesis that the medians are the same (i.e. the two populations don't have the identical and independent distributions, which may or may not mean that they have the same median).
Summary of Concern: What justifies using the distribution of the test statistic from permuting our samples to represent the null distribution above?

I am assuming that there is some justification because I think we carried out tests in this manner in my stats course, but I never paused to reflect on the steps of the procedure to make sure I fully understood them.

Also a side question: When the observed test statistic is 0, do you reject the null hypothesis or fail to reject the null hypothesis? (I've read that always assume that data is consistent with the null hypothesis by default, unless your data has an observed test statistic value that aligns with the alternative hypothesis and that is statistically significant.)
 A: Generally hypothesis tests are accompanied by extra assumptions that will need to hold (at least when the null is true), so that the null distribution of the test statistic can be obtained; this is as true for nonparametric tests as for parametric ones. 
So for example, the usual two sample t-test comes with assumptions of equality of variance and independence - which we rely on when finding the null distribution of the test statistic - even though neither condition is in the hypothesis itself. 
For permutation tests you need add at least the assumptions required to obtain exchangeability, though typically we'd use somewhat stronger assumptions (like independence for example).
A: You are right that you are testing much broader assumption that the  group labels are "random" and play no role in your results. As a proxy to test such hypothesis you use some test statistic that is evaluated on the permuted samples. In this case it is median, but it could something else as well. So you test if the labels are exchangeable as tested using median as criterion to assess that. In the end you will learn how "likely" would it be to find different medians in both groups if the group labels played no role in your data.
